A tree is a non-linear data structure that is used to store the data in a hierarchical form. The data will be maintained in the nodes that are linked in hierarchical order.
1. Introduction to Tree Data Structure
The linear data structures such as Array, Linked List, Stack, and Queue store the data sequentially. So the time complexity increases when performing the operation with a large amount of data. The hierarchical order of Trees helps to perform the operations faster than linear data structures.
Representation
- Root: The topmost node.
- Node: Node consists of data, a pointer to the left child, and a pointer to the right child.
- Parent: A node directly above is called its parent.
- Children: All the nodes directly under it are called children.
- Leaves: All the nodes that have no children are called leaves.
2. Types of Trees in Data Structure
| Binary Tree | A tree with a maximum of two children is allowed for every node. |
| Binary Search Tree | A Binary Tree with a particular ordering of nodes. |
| AVL Tree | A self-balanced Binary Search Tree. |
| Red Black Tree | A self-balanced Binary Search Tree with nodes colored in red or black. |
| Splay Tree | A self-balanced Binary Search Tree to keep the most recently accessed items on top. |
| Heap | A self-balanced Binary Tree with a particular ordering of nodes. |
| B Tree | A self-balanced m-way Binary Search Tree to maintain the sorted stream of data. |
| B+ Tree | B Tree extended for efficient search, insert and delete operations. |
| Spanning Tree | A subset of a Graph that has all vertices connected with the minimum number of edges. |
3. Time & Space Complexity of Trees
| Type | Search | Insertion | Deletion | Space Complexity |
|---|---|---|---|---|
| Binary Search Tree | O (n) | O (n) | O (n) | O (n) |
| AVL Tree | O (log n) | O (log n) | O (log n) | O (n) |
| Red Black Tree | O (log n) | O (log n) | O (log n) | O (n) |
| Splay Tree | O (log n) | O (log n) | O (log n) | O (n) |
| Heap | O (log n) | O (log n) | O (log n) | O (n) |
| B Tree | O (log n) | O (log n) | O (log n) | O (n) |
| B+ Tree | O (log n) | O (log n) | O (log n) | O (n) |
4. Applications of Tree in Data Structure
- A tree is generally used to represent hierarchical data such as File System.
- B Tree is widely used for Database indexes and File systems.
- Heaps are used in Dijkstra’s Algorithm to find the shortest path, implement the priority queues, etc.,
- Spanning Tree helps in designing any network such as computer networks, telecommunication networks, transportation networks, water supply networks, electrical grids, etc.
- Splay Tree plays a major role in caching data and is used by GNU compiler, sed stream editor, Unix malloc, etc.