This content originally appeared on DEV Community and was authored by Aya Bouchiha
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 less than or equal to 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!
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
This content originally appeared on DEV Community and was authored by Aya Bouchiha
Aya Bouchiha | Sciencx (2021-07-01T00:15:38+00:00) Introduction to AVL tree. Retrieved from https://www.scien.cx/2021/07/01/introduction-to-avl-tree/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.