Introduction to AVL tree

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.

• www.geeksforgeeks.org

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:

1. Right rotation
2. Left rotation
3. Right-Left rotation
4. Left-Right rotation

in the next post, we'll cover rotation types with the implementation, see you tomorrow, have a great day!

References and useful resources

• https://en.wikipedia.org/wiki/AVL_tree
• https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
• https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm
• https://www.javatpoint.com/avl-tree