|
|
|
|
|
Avl TreeIn computer science, an AVL tree is the first invented self-balancing binary search tree. In an AVL tree the height of the two child subtrees of any node differ by at most one, therefore it is also known as height-balanced. Lookup, 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, G.M. Adelson-Velsky and E.M. Landis, who published it in their 1962 paper "An algorithm for the organization of information." The balance factor of a node is the height of its right subtree minus the height of its left subtree. A node with balance factor , 0, or 1 is considered balanced. A node with balance factor or 2 is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees, possibly stored at nodes. Inserts require at most one single or double rotation. Operations The basic operations of an AVL tree generally involve carrying out the same algorithms as would be carried out on an unbalanced binary search tree, but preceded or followed by one or more of the so-called "AVL rotations." Insertion Insertion into an AVL tree may be carried out by inserting the given value into the tree as if it were an unbalanced binary search tree, and then retracing one's steps toward the root, rotating about any nodes which have become unbalanced during the insertion. Since at most 1.5 times lg n nodes are retraced on the journey back to the root, and each AVL rotation takes constant time, the insertion process in total takes O(log n) time. correct Deletion Deletion from an AVL tree may be carried out by rotating the node to be deleted down into a leaf node, and then pruning off that leaf node directly. Since at most lg n nodes are rotated during the rotation into the leaf, and each AVL rotation takes constant time, the deletion process in total takes O(log n) time. Lookup Lookup in an AVL tree is performed exactly as in an unbalanced binary search tree, and thus takes O(log n) time, since an AVL tree is always kept balanced. No special provisions need to be taken, and the tree's structure is not modified by lookups. (This is in contrast to splay tree lookups, which do modify their tree's structure.) See also Reference - G. Adelson-Velskii and E.M. Landis, "An algorithm for the organization of information." Doklady Akademii Nauk SSSR, 146:263–266, 1962 (Russian). English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259–1263, 1962.
External links
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|