Python DSALesson 101Free preview

AVL Trees

This lesson is part of Python · All levels

Summary

This lesson discusses the AVL Tree, a binary search tree that is kept in constant balance by rotating. Balance is measured by the balance factor, which is the difference in height between the left and right subtrees of a node. Thanks to this balance, the insert, search, and delete operations remain running even though the data is entered in random order.

Key points

Balance factor = tinggi(subtree left) - tinggi(subtree right) and should always be -1, 0, or 1.
When a node is unbalanced, a single rotation (left or right) or double rotation is performed.
The right rotation is used when the left subtree is too high, the left rotation is used when the right subtree is too high.
AVL Tree is called self-balancing because it balances itself every time the structure changes.
The price of this balance is that the insert and delete code is a little more complicated than the regular BST.

Full lesson

Code examples and quizzes

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