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.
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.