AVL tree

In 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 1, 0, or -1 is considered balanced. A node with balance factor -2 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.

Contents

1 Operations 1.1 Insertion 1.2 Deletion 1.3 Lookup 2 See also 3 Reference 4 External links

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.

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

• Tree rotation
• Splay tree
• Red-black tree
• B-tree

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

• Description from the Dictionary of Algorithms and Data Structures (http://www.nist.gov/dads/HTML/avltree.html)
• AVL Tree Traversal (http://www.auto.tuwien.ac.at/~blieb/woop/avl.html)
• Linked AVL tree (http://www.elude.ca/aapl/doc/classAvliTree.html)
• C++ AVL Tree Template (http://geocities.com/wkaras/gen_cpp/avl_tree.html) and C AVL TREE "Generic Package" (http://geocities.com/wkaras/gen_c/cavl_tree.html) by Walt Karas
• A Visual Basic AVL Tree Container Class (http://vbwm.com/art_2001/avltree08/) by Jim Harris
• AVL Trees: Tutorial and C++ Implementation (http://cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html) by Brad Appleton
• Ulm's Oberon Library: AVLTrees (http://www.mathematik.uni-ulm.de/oberon/0.5/lib/man/AVLTrees.html)
• The AVL TREE Data Type (http://www-old.physik.fu-berlin.de/edv_docu/documentation/xemacs-21.1.4/elib_toc.html#SEC21)
• CNAVLTree Class Reference (http://www.comnets.rwth-aachen.de/doc/cncl/classCNAVLTree.html)
• GNU libavl (http://www.stanford.edu/~blp/avl/)
• AVL-trees - balanced binary trees (http://home.earthlink.net/~akonshin/delphi_components.htm) by Alex Konshin
• Simulation of AVL Trees (http://www.informatik.uni-mannheim.de/~cjk/publications/ed-media98/node11.html)
• AVL tree applet (http://www.csi.uottawa.ca/~stan/csi2514/applets/avl/BT.html)
• Simulation of AVL Trees (DYNAMIC) (http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm)

da:AVL-træ de:AVL-Baum es:Árbol AVL fr:Arbre Andelson-Velskii et Landis pl:Drzewo AVL