Hello, today, we're going to talk about AVL tree.
#day_19
why we need to use AVL trees.
Sometimes, the Binary search tree's operations become O(n) instead of O(log n) due to being a skewed binary search tree, that's why Adelson, Velskii and Landis. so what's an AVL tree ?
if you're not familiar with binary search tree, this post will help you :)
Definition of AVL tree
AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.
Time and Space complexity
The space complexity of the avl tree is O(n)
| insert | search | delete |
|---|---|---|
| O(log n) | O(log n) | O(log n) |
Balance factor
the difference between the height of left and right subtrees can be calculated using this formula below:
BalanceFactor = height(left-sutree) − height(right-sutree)
if the balance factor was 1 or 0 or -1, the tree is balanced, if not, we use the rotation to make it balanced. There are four types of rotation:
- Right rotation
- Left rotation
- Right-Left rotation
- Left-Right rotation
in the next post, we'll cover rotation types with the implementation, see you tomorrow, have a great day!
Top comments (0)