A tree is a type of non-linear data structure in which data is stored in the hierarchical form. In a tree, data is stored in nodes at multiple levels. The nodes are connected together to each other on the basis of their hierarchy. In a tree, each node contains two things: a data value and a pointer that links to other nodes.
Why do we use Trees in Data Structure?
Trees are used to perform operations for large amounts and complex data. Whenever we have a large number of data, the search operations in linear data structures become more complex and expensive. In such cases, non-linear data structures like Trees save a large amount of time to perform any particular operation. A tree data structure can reduce the cost of some operations, instead of linear structures.
Properties of trees in Data Structure
Let’s have a look at the properties of trees in Data Structure.
Recursive Data Structure – Recursive data structures derive themselves from their structure. A tree has multiple subtrees associated recursively with it. Each subtree has its own root node and children nodes.
Height of a Node – Height is the length of the path from a specific node to the farthest leaf node. The height of a node is always measured from bottom to top. That is why the height of every each node is zero.
Level of a Node – The level of a node is measured with respect to the root node. It is defined as a step from top to bottom.
Number of Edges – The number of edges will be n-1, in a tree having n nodes. Every other node in the tree will have at least one incoming edge.
Degree of a Node – The degree of any node describes the number of children, that node has. Thus, leaf nodes have zero degrees.
Depth of a Node – The depth of a node is the reverse of height. The depth of the root node is zero. The depth of every other node is the number of edges it has from the root node.
Types of Trees in Data Structure
General Tree – A general tree is that which can have any degree. There are no restrictions on the number of children nodes in the Data Structure.
Binary Tree – A binary tree is that in which there is a maximum of two children. The node in a binary tree consists of three things- a data item, a pointer to the left child, and a pointer to the right child. Binary trees are of different types which include full binary tree, complete binary tree, perfect binary tree, skewed binary tree, etc.
Binary Search Tree – A binary search tree is a type of binary tree in which the left child node is always smaller than the root node and the right child is always greater than the root node.
AVL Tree – An AVL tree is a type of binary tree that is height-balanced. In this type of tree, the difference between the height of the left sub-tree and the height of the right sub-tree is either 0, 1, or -1. This difference in the height of trees is termed the balancing factor.
In terms of complexity, the AVL tree is more efficient as compared to a simple binary tree. This is because of the balancing property of an AVL tree.
Red-black Tree – A red-black tree is a type of binary search tree that is self-balancing. A red-black tree balances itself in two rotations whereas an AVL tree could take any number of rotations for balancing. In a red-black tree, each node is either red or black and uses an extra bit to store this information for every node. A red-black tree is very efficient than a simple binary search tree because of its balancing properties.
Splay Tree – Splay tree is also a type of self-balancing binary tree. In the splay tree, the root node is that which is accessed most recently, by performing some rotations. The term splaying is used for the most recently accessed node. Although a Splay tree is balanced it may not be height-balanced. In a splay tree, it takes O(log n) time to perform an operation.
Treap – Treap is a combination of tree and heap. It has the properties of both binary search trees and heap data structures. Each node in the treap data structure includes a key and a priority. The key in a tree comes from the binary search tree whereas, priority comes from the heap data structure.
As we know that, in a binary search tree, the value of the left child is always smaller than the root and the value of the right child node is always greater than the root. So, in a treap, the children of any sub-tree have a greater value than the root node of that subtree (property of heap data structure).
B-Tree – B-trees have a degree m, just like binary trees have degree 2. In a B tree, m could be any value greater than or equal to 2. A B-tree is an m-way tree in which a key in each node and every node can have a maximum of m children.
Tree Traversal
Tree traversal means visiting each node of the tree. There are mainly three types of tree traversals.
- Inorder Traversal
- Pre-order Traversal
- Post-order Traversal
If you want to learn more about types of trees in data structure and types of searching in data structure, visit Help me study Bro. Help me study Bro is one of the best educational platforms where you can learn data structure in an easy way.
Help me study bro is a leading e-learning platform that provides all the study materials of data structures. Whether you want to learn arrays, trees, or other topics of data structure, you can visit the website of Help me study bro. It is the best website, from where you can learn from basics to advanced level of data structure topics.
