22
loading...
Introduction to AVL tree
Hello, today, we're going to talk about AVL tree.
#day_19
#day_19
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 :)
if you're not familiar with binary search tree, this post will help you :)
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.
The space complexity of the avl tree is O(n)
| insert | search | delete |
|---|---|---|
| O(log n) | O(log n) | O(log n) |
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:
in the next post, we'll cover rotation types with the implementation, see you tomorrow, have a great day!
22