There are various varieties of trees that are often used in the context of Data Structures and Algorithms (DSA). Here are a few of the most important:
Binary Tree:
- A binary tree is a type of tree data structure in which each node can only have two children.
- The left child is the left subtree, while the right child is the right subtree.
- Binary trees are commonly utilized as the foundation for more complicated tree topologies.
Properties of a binary tree:
- The maximum number of nodes at each level of i is 2 i.
- At height h, the maximum number of nodes possible is 2h+1 -1.
- At height h, the minimum number of nodes possible is equal to h+1.
- A minimum number of nodes will represent a tree with maximum height and vice versa.
Time Complexity:
| Operation | Worst-Case Time Complexity | Best-Case Time Complexity | Average Time Complexity |
|---|---|---|---|
| Search | O(n) | O(1) | O(n) |
| Insertion | O(n) | O(1) | O(n) |
| Deletion | O(n) | O(1) | O(n) |
| Finding Minimum/Maximum Value | O(n) | O(1) | O(n) |
| Inorder Traversal | O(n) | O(n) | O(n) |
| Preorder Traversal | O(n) | O(n) | O(n) |
| Postorder Traversal | O(n) | O(n) | O(n) |
| Height Calculation | O(n) | O(1) | O(n) |
Space Complexity: O(n)
Binary Search Tree (BST):
- A binary search tree is a binary tree in which the left child of a node has a value that is less than the node’s value and the right child has a value that is larger than the node’s value.
- This attribute allows for quick searching, insertion, and deletion operations, making it suitable for jobs like keeping a sorted collection of objects.
Properties of Binary Search Tree:
- BST maintains the order of its nodes.
- For any given node, all the values in its left subtree are less than its value, and all the values in its right subtree are greater than its value.
- Searching, insertion, and deletion operations can be performed efficiently in O(log n) time on average, where n is the number of nodes in the tree. However, in the worst case (a skewed tree), these operations can take O(n) time.
Time Complexity:
| Operation | Worst-Case Time Complexity | Best-Case Time Complexity | Average Time Complexity |
|---|---|---|---|
| Search | O(n) | O(1) | O(log n) |
| Insertion | O(n) | O(1) | O(log n) |
| Deletion | O(n) | O(1) | O(log n) |
| Finding Minimum/Maximum Value | O(n) | O(1) | O(log n) |
| Inorder Traversal | O(n) | O(n) | O(n) |
| Preorder Traversal | O(n) | O(n) | O(n) |
| Postorder Traversal | O(n) | O(n) | O(n) |
| Height Calculation | O(n) | O(1) | O(n) |
Space Complexity: O(n)
AVL Tree:
- A self-balancing binary search tree is an AVL tree.
- It differs from other forms of tree data structures in that it was the first tree to be dynamically balanced.
- A balancing factor is applied to each node in the AVL tree. This method is dependent on whether the tree is balanced.
- The balancing factor is a major property of the tree in the AVL Tree data structure.
Balancing factor:
- It is the difference between the left subtree and the right subtree.
- The value of a balancing factor must be 0, -1, or 1. Therefore, each node of an AVL tree should consist of a balancing factor value i.e. 0, -1, or 1.
- Balance Factor = (Height of Left Subtree – Height of Right Subtree)
- An AVL tree is said to be a balanced tree if the balance factor of each node is between -1 to 1.
Values of nodes other than -1, to 1 in an AVL tree will represent an unbalanced tree that needs to be balanced.
- If a node has a balance factor of 1, it means that the left subtree is one level higher than the right subtree.
- If a node has a balance factor of 0, it means that the height of the left subtree and the right subtree is equal.
- If a node has a balance factor of -1, it means that the right subtree is one level higher than the left subtree or the left subtree is one level lower than the right subtree.
Time Complexity:
| Operation | Worst-Case Time Complexity | Best-Case Time Complexity | Average Time Complexity |
|---|---|---|---|
| Search | O(log n) | O(1) | O(log n) |
| Insertion | O(log n) | O(1) | O(log n) |
| Deletion | O(log n) | O(1) | O(log n) |
| Finding Minimum/Maximum Value | O(log n) | O(1) | O(log n) |
| Inorder Traversal | O(n) | O(n) | O(n) |
| Preorder Traversal | O(n) | O(n) | O(n) |
| Postorder Traversal | O(n) | O(n) | O(n) |
| Height Calculation | O(1) | O(1) | O(1) |
Space Complexity: O(n)
B-Tree:
- A B-tree is a self-balancing search tree optimized for disc or other direct-access storage systems.
- It can manage massive quantities of data since each node can have numerous keys and child pointers.
- B-trees are commonly used in file systems and databases because they allow for fast search, insertion, and deletion operations with a specified maximum height.
- They are designed to minimize disc I/O operations.
Properties of a B-tree:
- Keys are stored in increasing order for each node x.
- A Boolean value “x.leaf” exists in each node, which is true if x is a leaf.
- The internal nodes should have at most “n-1” keys, where n is the order of the tree. It should also have a pointer for each child.
- All the nodes will have at most n children and at least n/2 children, except the root node.
- The leaf nodes of the tree have the same depth.
- The root node will have a minimum of 1 key and at least two children.
- If n ≥ 1, then for any n-key B-tree of height h and minimum degree t ≥ 2, h ≥ logt (n+1)/2.
Time Complexity:
| Operation | Worst-Case Time Complexity | Best-Case Time Complexity | Average Time Complexity |
|---|---|---|---|
| Search | O(log n) | O(1) | O(log n) |
| Insertion | O(log n) | O(1) | O(log n) |
| Deletion | O(log n) | O(1) | O(log n) |
| Finding Minimum/Maximum Value | O(log n) | O(1) | O(log n) |
| Inorder Traversal | O(n) | O(n) | O(n) |
| Preorder Traversal | O(n) | O(n) | O(n) |
| Postorder Traversal | O(n) | O(n) | O(n) |
| Height Calculation | O(1) | O(1) | O(1) |
Space Complexity: O(n)
Note: also read about DSA: Trees
Follow Me
If you like my post please follow me to read my latest post on programming and technology.
https://www.instagram.com/coderz.py/
https://www.facebook.com/coderz.py
Staying up to the mark is what defines me. Hi all! I’m Rabecca Fatima a keen learner, great enthusiast, ready to take new challenges as stepping stones towards flying colors.