{{Citations missing|article|date=October 2007}}
[[Image:Unbalanced binary tree.svg|thumb|right|251px|An example of an unbalanced '''non-AVL''' tree]]
In [[computer science]], an '''AVL tree''' is a [[self-balancing binary search tree]], and the first such data structure to be invented{{Fact|date=May 2007}}. In an AVL tree the [[tree height|heights]] of the two [[child node|child]] subtrees of any node differ by at most one, therefore it is also called [[height-balanced tree|height-balanced]]. Lookup, insertion, and deletion all take [[big O notation|O]](log ''n'') time in both the average and worst cases. Additions and deletions may require the tree to be rebalanced by one or more [[tree rotation]]s.
The AVL tree is named after its two inventors, [[Georgii Adelson-Velsky|G.M. Adelson-Velsky]] and [[Yevgeniy Landis|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 any other balance factor 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.
AVL trees are often compared with [[red-black trees]] because they support the same set of operations and because red-black trees also take [[big O notation|O]](log ''n'') time for the basic operations. AVL trees perform better than red-black trees for lookup-intensive applications.<ref>{{cite web|last = Pfaff|first = Ben|title = Performance Analysis of BSTs in System Software| publisher = [[Stanford university|Stanford University]]|year = 2004|month = June|url = http://www.stanford.edu/~blp/papers/libavl.pdf|format = PDF}}</ref> The AVL tree balancing algorithm appears in many computer science curricula.
[[Image:AVLtreef.svg|thumb|right|251px|The same tree after being height-balanced]]
==Operations==
The basic operations of an AVL tree generally involve carrying out the same actions as would be carried out on an unbalanced [[binary search tree]], but preceded or followed by one or more operations called [[tree rotation]]s, which help to restore the height balance of the subtrees.
===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 updating the balance factor of the nodes.
If the balance factor becomes -1, 0, or 1 then the tree is still in AVL form, and no rotations are necessary.
If the balance factor becomes 2 or -2 then the tree rooted at this node is unbalanced, and a tree rotation is needed. At most a single or double rotation will be needed to balance the tree.
[[Image:Tree Rebalancing.gif|thumb|Pictorial description of how rotations cause rebalancing in an AVL tree.]]
There are basically four cases which need to be accounted for, of which two are symmetric to the other two. For simplicity, the root of the unbalanced subtree will be called P, the right child of that node will be called Q, and the left child will be called O. If the balance factor of P is 2, it means that the right subtree outweighs the left subtree of the given node, and the balance factor of the right child (Q) must then be checked. If the balance factor of the Q is 1, it means the insertion occurred on the (external) right side of that node and a left rotation is needed ([[tree rotation]]) with P as the root. If the balance factor of Q is -1, this means the insertion happened on the (internal) left side of that node. This requires a double rotation. The first rotation is a right rotation with Q as the root. The second is a left rotation with P as the root.
The other two cases are identical to the previous two, but with the original balance factor of -2 and the left subtree outweighing the right subtree.[http://www.eli.sdsu.edu/courses/fall96/cs660/notes/avl/avl.html] [http://www.cs.purdue.edu/homes/ayg/CS251/slides/chap7b.pdf]
[http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch10.html]
Only the nodes traversed from the insertion point to the root of the tree need be checked, and rotations are a constant time operation, and because the height is limited to O(log(n)), the execution time for an insertion is O(log(n)).
===Deletion===
If the node is a leaf, remove it.
If the node is not a leaf, replace it with either the largest in its left subtree or the smallest in its right subtree, and remove that node.
Thus the node that is removed has at most one leaf.
After deletion retrace the path back up the tree to the root, adjusting the balance factors as needed.
The retracing can stop if the balance factor becomes -1 or 1 indicating that the height of that subtree has remained unchanged.
If the balance factor becomes 0 then the height of the subtree has decreased by one and the retracing needs to continue.
If the balance factor becomes -2 or 2 then the subtree is unbalanced and needs to be rotated to fix it.
If the rotation leaves the subtree's balance factor at 0 then the retracing towards the root must continue since the height of this subtree has decreased by one.
This is in contrast to an insertion where a rotation resulting in a balance factor of 0 indicated that the subtree's height has remained unchanged.
The time required is O(h) for lookup plus maximum O(log(h)) rotations on the way back to the root; so the operation can be completed in O(log ''n'') time.
===Lookup===
Lookup in an AVL tree is performed exactly as in an unbalanced binary search tree, except because of the height-balancing of the tree, a lookup takes O(log ''n'') time. 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.)
If each node additionally records the size of its subtree (including itself and its descendants), then the nodes can be retrieved by index in O(log ''n'') time as well.
Once a node has been found in a balanced tree, the ''next'' or ''previous'' node can be obtained in [[amortized complexity|amortized]] constant time. (In a few cases, about 2*log(n) links will need to be traversed. In most cases, only a single link need be traversed. On the average, about two links need to be traversed.){{Fact|date=August 2007}}
==Comparison to other structures==
Both AVL trees and red-black trees are self-balancing binary search trees, so they are very similar mathematically. The operations to balance the trees are different, but both occur in constant time. The real difference between the two is the limiting height. For a tree of size <math>n</math>:
*an AVL tree's height is limited to <math>1.44 \cdot \lg n</math>
*a red-black tree's height is limited to <math>2 \cdot \lg n</math>
So while insertions, deletions, and lookups in both types of trees would be <math>O(\log n)</math>, an AVL tree is shorter in the worst case, so will generally require less time for each of those operations.
==See also==
*[[Tree rotation]]
*[[Splay tree]]
*[[Red-black tree]]
*[[B-tree]]
*[[T-tree]]
==References==
*{{cite journal|last=Adelson-Velskii|first=G.|coauthors=E. M. Landis|year=1962|title=An algorithm for the organization of information|journal=[[Proceedings of the USSR Academy of Sciences]]|volume=146|pages=263-266}} {{ru icon}} [[English language|English]] translation by Myron J. Ricci in ''Soviet Math. Doklady'', 3:1259–1263, 1962.
* [[Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 458–475 of section 6.2.3: Balanced Trees. Note that Knuth calls AVL trees simply "balanced trees".
<references/>
==External links==
*[http://users.aber.ac.uk/smg/Modules/CO21120-April-2003/NOTES/23-MoreAVLTrees.ppt Presentation of AVL, including double rotation]
*[http://www.nist.gov/dads/HTML/avltree.html Description from the Dictionary of Algorithms and Data Structures]
*[http://www-old.physik.fu-berlin.de/edv_docu/documentation/xemacs-21.1.4/elib_toc.html#SEC21 The AVL TREE Data Type]
*[http://www.eli.sdsu.edu/courses/fall96/cs660/notes/avl/avl.html Visual Tutorial of AVL Tree operations]
===Implementations===
*[http://www.goletas.com/solutions/collections/ Iterative Implementation of AVL Trees in C#]
*[http://herbert.gandraxa.com/herbert/avl.asp Heavily documented fast Implementation] in [[Linoleum programming language|Linoleum]] (a cross-platform [[Assembly language|Assembler]])
*[http://geocities.com/wkaras/gen_cpp/avl_tree.html C++ AVL Tree Template]
*[http://www.mathematik.uni-ulm.de/oberon/0.5/lib/man/AVLTrees.html Ulm's Oberon Library: AVLTrees]
*[http://www.csi.uottawa.ca/~stan/csi2514/applets/avl/BT.html AVL tree applet]
*[http://src.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/common/avl/avl.c OpenSolaris AVL Tree C source]
*[http://www.stanford.edu/~blp/avl/ GNU libavl]
[[Category:Trees (structure)]]
[[cs:AVL-strom]]
[[da:AVL-træ]]
[[de:AVL-Baum]]
[[es:Árbol AVL]]
[[fr:Arbre AVL]]
[[id:Pohon AVL]]
[[it:Albero AVL]]
[[he:עץ AVL]]
[[lt:AVL medis]]
[[hu:AVL-fa]]
[[ja:AVL木]]
[[pl:Drzewo AVL]]
[[pt:Árvore AVL]]
[[ru:АВЛ-дерево]]
[[sk:AVL strom]]
[[sl:AVL-drevo]]
[[fi:AVL-puu]]
[[sv:AVL-träd]]
[[vi:Cây AVL]]
[[zh:AVL树]]