From TheBestLinks.com
An example of a non-AVL tree
In computer science, an AVL tree is a self-balancing binary search tree where the height of the two child subtrees of any node differ by at most one, also known as height-balanced. Look-up, insertion and deletion are all O(log(n)) in both the average and worst cases. Additions and deletions may require the tree to be rebalanced by one or more tree rotations. The AVL tree is named after its inventors, Adelson-Velskii and Landis (1962).
Each node in the tree has a balance factor stored in the node. This balance factor is the maximum height of its right subtree minus the maximum height of its left subtree. A node with balance factor -1,0, or 1 is considered balanced. A node with balance factor -2 or 2 is considered unbalanced and requires rebalancing the tree.
The same tree after being height-balanced
Inserts require at most one single or double rotation. Tree height is bounded to 144% of optimal.
See also: B-tree, red-black tree, splay tree
de:AVL-Baum
fr:Arbre Andelson-Velskii et Landis
pl:Drzewo AVL
Related links
Top visited
0 of
0 links
[no links posted yet]
>> place link >>
Discussion
Last posted
0 of
0 messages
[no messages posted yet]
>> post message >>
Watch
You can
add this article to your own "watchlist" and receive e-mail notification about all changes in this page.
