AVL tree
This article needs additional citations for verification. (July 2016) |
AVL tree | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | tree | |||||||||||||||||||||||
Invented | 1962 | |||||||||||||||||||||||
Invented by | Georgy Adelson-Velsky and Evgenii Landis | |||||||||||||||||||||||
|
In
The AVL tree is named after its two Soviet inventors, Georgy Adelson-Velsky and Evgenii Landis, who published it in their 1962 paper "An algorithm for the organization of information".[3]
AVL trees are often compared with red–black trees because both support the same set of operations and take O(log n) time for the basic operations. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more rigidly balanced.[4] Similar to red–black trees, AVL trees are height-balanced. Both are in general not weight-balanced nor μ-balanced for any μ≤1⁄2;[5] that is, sibling nodes can have hugely differing numbers of descendants.
Languages
Definition
Balance factor
In a binary tree the balance factor of a node N is defined to be the height difference
- BalanceFactor(N) := –Height(LeftSubtree(N)) + Height(RightSubtree(N)) [6]
of its two child subtrees. A binary tree is called AVL tree if the
- BalanceFactor(N) ∈ {–1,0,+1}
holds for every node N in the tree.
A node N with BalanceFactor(N) < 0 is called "left-heavy", one with BalanceFactor(N) > 0 is called "right-heavy", and one with BalanceFactor(N) = 0 is sometimes simply called "balanced".
- Remark
In the sequel, because there is a one-to-one correspondence between nodes and the subtrees rooted by them, we sometimes let it to the context whether the name of an object stands for the node or the subtree.
Properties
Balance factors can be kept up-to-date by knowing the previous balance factors and the change in height – it is not necessary to know the absolute height. For holding the AVL balance information, two bits per node are sufficient.[7]
The height h of an AVL tree with n nodes lies in the interval:[8]
- log2(n+1) ≤ h < c log2(n+2)+b
with the golden ratio φ := (1+√5) ⁄2 ≈ 1.618, c := 1⁄ log2 φ ≈ 1.44, and b := c⁄2 log2 5 – 2 ≈ –0.328. This is because an AVL tree of height h contains at least Fh+2 – 1 nodes where {Fh} is the
Data structure
According to the original paper "An algorithm for the organization of information" AVL trees have been invented as binary search trees. In that sense they are a data structure together with its major associated operations, namely search, insert, delete, which rely on and maintain the AVL property. In that sense, the AVL tree is a "self-balancing binary search tree".
Operations
This section needs additional citations for verification. (July 2016) |
Read-only operations of an AVL tree involve carrying out the same actions as would be carried out on an unbalanced binary search tree, but modifications have to observe and restore the height balance of the subtrees.
Searching
Searching for a specific key in an AVL tree can be done the same way as that of a normal unbalanced binary search tree. In order for search to work effectively it has to employ a comparison function which establishes a total order (or at least a total preorder) on the set of keys. The number of comparisons required for successful search is limited by the height h and for unsuccessful search is very close to h, so both are in O(log n).
Traversal
Once a node has been found in an AVL tree, the next or previous node can be accessed in
Comparison to other structures
Both AVL trees and red–black trees are self-balancing binary search trees and they are very similar mathematically.[9] The operations to balance the trees are different, but both occur on the average in O(1) with maximum in O(log n). The real difference between the two is the limiting height.
For a tree of size n ≥ 1
- an AVL tree’s height is at most
- where the golden ratio, and .
- a red–black tree’s height is at most
AVL trees are more rigidly balanced than red–black trees, leading to faster retrieval but slower insertion and deletion.
See also
References
- ^ a b c d e f Eric Alexander. "AVL Trees".
- ^ Robert Sedgewick, Algorithms, Addison-Wesley, 1983, ISBN 0-201-06672-6, page 199, chapter 15: Balanced Trees.
- ^ Georgy Adelson-Velsky, G.; Evgenii Landis (1962). "An algorithm for the organization of information". Proceedings of the USSR Academy of Sciences (in Russian). 146: 263–266. English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259–1263, 1962.
- Stanford University.
- ^ AVL trees are not weight-balanced? (meaning: AVL trees are not μ-balanced?)
Thereby: A Binary Tree is called -balanced, with , if for every node , the inequality - ISBN 0-201-89685-0.
- ^ More precisely: if the AVL balance information is kept in the child nodes – with meaning "when going upward there is an additional increment in height", this can be done with one bit. Nevertheless, the modifying operations can be programmed more efficiently if the balance information can be checked with one test.
- ISBN 0-201-89685-0.
- ^ In fact, every AVL tree can be colored red–black.
- ^ Red–black tree#Proof of asymptotic bounds
Further reading
- 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.
External links
- This article incorporates NIST.
- AVL tree demonstration (requires Flash)
- AVL tree demonstration (requires Java)