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.
In a full binary tree, every node has either zero or two children. This means that no node has just one child. Full binary trees often lead to efficient data processing and retrieval.
A complete binary tree is one in which all levels are fully filled except possibly for the last level, which is filled from left to right. This structure is beneficial for implementing binary heaps, which are used in priority queue implementations.
In a skewed binary tree, every node has only one child, either on the left or the right. This creates an unbalanced structure that resembles a linked list. While easy to build, skewed trees can lead to inefficient operations as they do not utilize the properties of binary trees effectively.
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.
When it comes to complexity, AVL trees demonstrate a clear advantage over simple binary trees. In an unbalanced binary tree, operations can degrade to O(n) time complexity, particularly if the tree resembles a linked list. This scenario typically occurs when values are inserted in sorted order, causing the tree to grow skewed. On the other hand, AVL trees enforce balance, which ensures that operations can perform in O(log n) time complexity—where “n” represents the number of nodes in the tree. This efficiency is especially significant in applications where performance is critical, such as in database indexing and memory management.
Maintaining balance in an AVL tree is achieved through rotations. There are four possible rotations that can occur when the tree becomes unbalanced:
1. **Left Rotation**: Applied when a node is added to the right subtree of the right child.
2. **Right Rotation**: Utilized when a node is added to the left subtree of the left child.
3. **Left-Right Rotation**: Enacted when a node is added to the right subtree of the left child.
4. **Right-Left Rotation**: Used when a node is added to the left subtree of the right child.
These rotations ensure that the AVL tree restores its balance after operations that may alter the structure.
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).
The insertion process begins with assigning a random priority to the new node being inserted. After the priority is assigned, the treap behaves like a binary search tree for that key. This approach not only allows for a unique structure but also plays a critical role in keeping the treap balanced. By leveraging randomization, treaps largely avoid the degenerative cases that can lead to unchecked growth in standard binary search trees.
When deleting a node, the treap ensures that both the binary search tree property and the heap property are preserved. If a node has no children, it simply gets removed. If a node has one child, the child takes its place. In the case of a node with two children, one can either choose to replace it with the highest priority child or the lowest, depending on specific implementations, followed by a rebalancing step if necessary.
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
Inorder Traversal is a depth-first traversal method where nodes are visited in the following order:
- Traverse the left subtree.
- Visit the root node.
- Traverse the right subtree.
This method is primarily used with binary search trees (BSTs), where it retrieves nodes in ascending order. For example, consider the following BST:
4 / \ 2 6 / \ / \ 1 3 5 7
An inorder traversal would yield: 1, 2, 3, 4, 5, 6, 7.
Pre-order Traversal
Pre-order Traversal follows the sequence:
- Visit the root node.
- Traverse the left subtree.
- Traverse the right subtree.
Using the same BST example, a pre-order traversal would produce: 4, 2, 1, 3, 6, 5, 7.
Post-order Traversal
Post-order Traversal follows the sequence:
- Traverse the left subtree.
- Traverse the right subtree.
- Visit the root node.
For the given BST, a post-order traversal would result in: 1, 3, 2, 5, 7, 6, 4.
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.