coderz.py

Keep Coding Keep Cheering!

DSA: Types of Tree

Trie in DSA

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:

OperationWorst-Case Time ComplexityBest-Case Time ComplexityAverage Time Complexity
SearchO(n)O(1)O(n)
InsertionO(n)O(1)O(n)
DeletionO(n)O(1)O(n)
Finding Minimum/Maximum ValueO(n)O(1)O(n)
Inorder TraversalO(n)O(n)O(n)
Preorder TraversalO(n)O(n)O(n)
Postorder TraversalO(n)O(n)O(n)
Height CalculationO(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:

OperationWorst-Case Time ComplexityBest-Case Time ComplexityAverage Time Complexity
SearchO(n)O(1)O(log n)
InsertionO(n)O(1)O(log n)
DeletionO(n)O(1)O(log n)
Finding Minimum/Maximum ValueO(n)O(1)O(log n)
Inorder TraversalO(n)O(n)O(n)
Preorder TraversalO(n)O(n)O(n)
Postorder TraversalO(n)O(n)O(n)
Height CalculationO(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:

OperationWorst-Case Time ComplexityBest-Case Time ComplexityAverage Time Complexity
SearchO(log n)O(1)O(log n)
InsertionO(log n)O(1)O(log n)
DeletionO(log n)O(1)O(log n)
Finding Minimum/Maximum ValueO(log n)O(1)O(log n)
Inorder TraversalO(n)O(n)O(n)
Preorder TraversalO(n)O(n)O(n)
Postorder TraversalO(n)O(n)O(n)
Height CalculationO(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:

OperationWorst-Case Time ComplexityBest-Case Time ComplexityAverage Time Complexity
SearchO(log n)O(1)O(log n)
InsertionO(log n)O(1)O(log n)
DeletionO(log n)O(1)O(log n)
Finding Minimum/Maximum ValueO(log n)O(1)O(log n)
Inorder TraversalO(n)O(n)O(n)
Preorder TraversalO(n)O(n)O(n)
Postorder TraversalO(n)O(n)O(n)
Height CalculationO(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

Leave a Comment

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

Advertisement