27-08-2014, 11:11 AM
AVL TreesData StructuresFall 2006 Evan Korth
AVL.ppt (Size: 181.5 KB / Downloads: 11)
AVL (Adelson-Velskii and Landis) tree
A balanced binary search tree where the height of the two subtrees (children) of a node differs by at most one. Look-up, insertion, and deletion are O( log n), where n is the number of nodes in the tree.
The insertion problem
Unless keys appear in just the right order, imbalance will occur
It can be shown that there are only two possible types of imbalance (see next slide):
Left-left (or right-right) imbalance
Left-right (or right-left) imbalance
The right-hand imbalances are the same, by symmetry
Localising the problem
Two principles:
Imbalance will only occur on the path from the inserted node to the root (only these nodes have had their subtrees altered - local problem)
Rebalancing should occur at the deepest unbalanced node (local solution too)