Tree Data Structure

Free Data Structures and Algorithms courses with real-time projects Start Now!!

Tree, just like graph, is also a nonlinear data structure. The elements are not arranged in a sequential manner. In this article, we will learn about trees, different terminologies, types of trees, and their applications.

Tree Data Structure

A tree is a nonlinear and hierarchical data structure. A tree consists of nodes and edges. Tree data structures, just like graphs are nonlinear data structures. The computation complexity increases exponentially while working with large data stored in a linear data structure like an array or linked list. But the use of trees makes it highly efficient, fast, and time-efficient.

  • Different tree structures perform faster and allow quicker access to data
  • Each tree has one root node and each node can have only one parent.
  • A tree is not a sequential data structure. It is a hierarchical structure as elements in a Tree are arranged in multiple levels

data structure tree

Tree Terminologies

1. Node: Entity containing a key / Value and pointer to its children nodes.

2. Edge: the connection between any two nodes.

3. Root: root is the topmost node of the tree. Each tree has only one root node.

4. Height of a node: height is the number of edges in the longest path from the node to the leaf node.

5. Depth of a node: Number of edges from the root node to the node.

6. Height of a tree: number of edges from the root to the leaf node.

7. Degree of a node: total number of branches a node is having

8. Forest: Collection of disjoint trees

9. Traversal: Visiting any node in the tree from the root node is called traversal.

Tree Terminologies

Properties of Tree

1. A tree with n nodes will have n-1 edges. Each edge represents the path from one node to another.

2. Each node except the root node will have at least one incoming edge and each node except the leaf nodes will have at least one outgoing edge. Each edge will represent the parent-child relationship

3. The root node has zero depth. The depth of each node is defined as the length of the path from the root to that node

4. Each leaf node has a height of 0. The height of each node is defined as the path from that node to the leaf node.

Types of tree in Data Structure

1. Binary tree: in the binary tree, as the name suggests, each node can have at most two child nodes. A node can have zero, one, or two child nodes

2. General tree: general tree is one of the types of tree data structure in which a node can have any number of nodes. No restrictions on the degree of a node.

3. Binary search tree: binary search tree is a type of binary tree where each left node should have a value of less than the root node and each right node should have a value greater than the root node.

4. AVL tree: AVL tree is a variant of the binary search tree. It satisfies the property of both binary tree and binary search tree. Invented by Adelson Velsky Lindas, the AVL tree is a self-balancing binary search tree that balances the height of the left subtree and right subtrees. The balancing is measured in terms of the balancing factors.

5. Red Black tree: red-black tree is an improvement of the AVL tree. In the AVL tree, the Number of rotations required to balance the tree is not known but in a red-black tree, we can balance the tree in a maximum of two rotations. A red-black tree has one extra bit representing the red or black color of the node which ensures the balancing of the tree.

6. Splay tree: splay tree is a kind of binary search tree where the most recently accessed node is put at the root position by performing rotations. Just like the AVL tree, it is also a self-balancing binary search tree.

7. Treap: it is a combination of tree and heap data structure and satisfies the properties of both. Entry status structure each node has both key and priority associated with it. Key is derived from the binary search tree and priority is derived from the heap data structure.

8. B-Tree: B-tree is a balanced ‘m’ way tree where ‘m’ is the order of the tree. In the B tree, each node can have more than one key and more than two children. Each node can have maximum ‘m’ children and maximum and m-1 keys.

Implementation of tree

Each node in a tree has a pointer to each child node and data.

Implementation of Tree in Data Structure

A node can be created as:

struct node  
{  
  int data;  
struct node *leftchild;  
struct node *rightchild;   
}

Applications of tree

1. Heap data structure is useful in sorting

2. Binary search trees are useful to check if the element present is or not. BST has a complexity of log n.

3. Most popular databases use B trees and B+ trees

4. Compilers use a syntax tree to validate the syntax of a program

5. A modified version of trees called tries is used in modern routers to store routing information

6. File stored in any folder on any drive on a hard disk is stored in a hierarchical form which uses a tree to store data.

Conclusion

Trees are non-linear data structures that are very efficient while dealing with large data. In this article, we briefly learned about different types of trees. We also witnessed some real-life applications of trees. In future articles, we will learn about each type in detail with their implementations in different languages.

We work very hard to provide you quality material
Could you take 15 seconds and share your happy experience on Google

follow dataflair on YouTube

Leave a Reply

Your email address will not be published. Required fields are marked *