TreesLesson 30Free preview

DSA AVL Trees

This lesson is part of DSA · All levels

Summary

AVL tree is a binary search tree that balances itself by keeping the high difference between the left and right subtrees of each node at no more than one. When inserting or removing a tree causes an imbalance, a single or double rotation is performed to restore balance. As a result, the search was secured.

Key points

The left-right height difference of each node (balance factor) is 1
Balance restored with single and double rotation
Guaranteed searches are different from regular BST
The insertion can trigger a rotation of the chain to the root.

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.