Balanced search trees are trees whose height in the worst case is and for which the operations INSERT, DELETE, and SEARCH can be implemented in time. Complete binary trees, if used as search trees, cannot be updated after an insertion or deletion in time less than . They are too rigid. The key to the design of balanced search trees is the introduction of glue, or degrees of freedom. This glue takes the form of red nodes in a red-black tree, nodes with 2 children (instead of three) in 2-3 trees, and nodes with a height-imbalance of one in AVL trees.
Binary search trees (see Figure 1) work well for many applications
but they are limiting because of their bad worst-case performance (height =
A binary search tree with this worst-case structure is no more efficient than
a regular linked list.
There exist over one hundred types of balanced search trees. Some of the more common types are: AVL trees, B-trees, and red-black trees. B-trees are a category of tree designed to work well on magnetic disks and other direct-access secondary storage devices (Cormen et al., 1996, p:381).Heights of balanced search trees
AVL trees were invented by two computer chess specialists in Russia, Adelson-Velskii and Landis in 1962 (hence the acronym AVL). See next section for detailed information regarding AVL trees.
A B-tree of order m is a tree exhibiting the following properties:
B-trees of order 4 are known as 2-3-4 trees, and a B-tree of order 3 is known as a 2-3 tree. The accompanying Java applet demonstrates insert operations on a 2-3 tree. In fact, 2-3 trees were "invented" by J.E. Hopcroft in 1970 (Cormen et al., 1996, p:399), prior to B-trees in 1972 by Bayer and McCreight.
Red-black trees are standard binary trees that satisfy the following conditions:
AVL trees are identical to standard binary search trees except that for
every node in an AVL tree, the height of the left and right subtrees can differ
by at most 1 (Weiss, 1993, p:108). AVL trees are HB-k trees (height balanced
trees of order k) of order HB-1. The following is the height differential
When storing an AVL tree, a field must be added to each node with one of three values: 1, 0, or -1. A value of 1 in this field means that the left subtree has a height one more than the right subtree. A value of -1 denotes the opposite. A value of 0 indicates that the heights of both subtrees are the same.
Updates of AVL trees require up to rotations, whereas updating red-black trees can be done using only one or two rotations (up to color changes). For this reason, they (AVL trees) are considered a bit obsolete by some.
Sparse AVL trees are defined as AVL trees of height h with the fewest possible nodes. Figure 3 shows sparse AVL trees of heights 0, 1, 2, and 3.
We first analyze the number of nodes in a sparse AVL tree of height k.
From Figure 3, we can deduce the following recurrence relation:
which looks like the Fibonacci sequence given by:
Adding 1 on both sides of the equalities we obtain:
Taking to be , we rewrite the recurrence relation as:
which is the usual Fibonacci recurrence relation.
By inspecting the Fibonacci sequence, one suspects that it grows somehow "exponentially" i.e. that it is of the form: , for some suitable constants A and c that we have to find.
Replacing by in the Fibonacci recurrence relation, we get:
After cancelling A, dividing by on both sides, the following quadratic equation:
is solved with the usual method, and:
The theory for linear homogeneous recurrence relations (cf: Rosen, K. "Discrete Mathematics and its Applications", third edition.) says that the general solution of such a recurrence relation is given by:
Note that: is an integer. Also:
since , we have fast.
We still have to find the two unknowns and . Using the initial conditions in the recurrence relation, we know that and , so the constants are extracted from:
Solving we get: and,
Hence, a sparse AVL tree of height k has:
If an AVL tree in general has height k, and n nodes, then:
and therefore, after trivial operations,
Note: is known under the name golden ratio and powers of it are very close to be integers.
In the worst case, a 2-3 tree is a complete binary tree.
Complete binary tree of height h has:
1 + 2 + 4 + ... + 2^h
= (2^(h+1) - 1)/(2 - 1)
= 2^(h+1) - 1 nodes.
Therefore, the height of such a tree with n nodes can be computed as:
n = 2^(h+1) - 1,
2^(h+1) = n + 1,
h + 1 = (n+1),
h = (n+1) - 1 ~= . (n >>)
The best case of a 2-3 tree is a complete ternary tree. A complete ternary tree of height h has:
1 + 3 + 9 + ... + 3^h
= (3^(h+1) - 1)/(3 - 1)
= (3^(h+1) - 1)/2 nodes.
Thus, the height of such a tree with n node can be calculated in the same way.
n = (3^(h+1) - 1)/2,
3^(h+1) = 2n + 1,
h + 1 = (2n+1) (base 3),
h = (2n+1) - 1 ~= . (n>>)
Therefore, the height of a 2-3 tree is sandwiched between and , thus, always beats a complete binary tree which has a height ~= .
Although searching operations on a 2-3 balanced search tree are guaranteed a very good worst case, this property comes at the expense of sometimes costly insertions. Figure 6 illustrates such a situation and the Java applet below performs the insertion.
Java applet source code.
Introduction to AVL trees. Explanation of construction and insertion. Rhys Price Jones, Fritz Ruehr, Richard Salter, Oberlin College.
Brief survey of some of the many kinds of balanced search trees. Chris Riesbeck, Northwestern University.
3D view illustrates the mapping between a 2-3-4 tree and a red-black tree. Marc H. Brown, Marc A. Najork, Digital Equipment Corporation.
Lecture slides covering various balanced searc tree types: 2-3 trees, 2-3-4 trees, red-black trees, AVL trees. Jack Hodges Ph.D., San Francisco State University.
AVL and Threaded AVL Balanced Binary Trees with source code in C and C++. Windbase Software Inc..
Java Applet. Construction of AVL Tree. Stepped or continuous Animation. Dr. Glenn W. Rowe, University of Dundee.
Java Applet. Insertion and deletion in a 2-3 Tree. Woo Han Sang, University of Florida.
Bell, Jim. An Evaluation of Self-Adjusting Binary Search Tree Technics. Software -Practice and Experience, v23. p369-82. 1993.
Author introduces self-adjusting binary trees and shows the results of testing done also with BST and AVL tree and compares the results.
Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. The MIT Press. 1996.
Chapter 14 covers red-black trees: their properties, rotations, insertions, and deletion.
Horowitz, Ellis. Sahni, Sartaj. Fundamentals of of Data Structures. Computer Science Press. p: 442-456. 1976.
AVL implementation in Sparks(insersion). Time analysis of operations with comparison with sequential list and linked list.
Gotlieb, C. Data Types and Structures. Prentice-Hall. p:223. 1978.
Lists and explains different ways of achieving completeness of the tree. M-ary trees(including 2-3 Tree). Visual representaton of insertion methods. Deletion algorithm and analysis.
Koster, C.H.A. Van der Weide, Th.P. Hairy Search Trees. Computer Journal, v.38, no8. p:691-4. 1995.
Maintaining efficiency is very complex in balanced trees such as AVL Tree and 2-3 Tree. Thus we can consider such class of trees (that the author refers to as "Hairy Tree") whose insersion algoriths perform local balancing around newly inserted node, without any backtrackings of the search path. Author performs time analysis of the algorithm and it's comparison with AVL, and 2-3 Trees.
Reingold, Edward M. Data Structures. Boston: Little Brown. 1983.
Rebalancing, deletion alogrithms and their time analysis.
Robert Sedgewick. Algorithms in C. Addison-Wesley Publishing Company. 1990.
Chapter 15 covers Balanced Trees: Top-Down 2-3-4 trees, red-black trees, and other algorithms.
Sorenson, Trembly. An Introduction to Data Structures with Applications. McGraw Hill Inc. p: 585. 1986.
Different search trees. Search, intersion, rebalancing, and deletion algorithms.
Weiss, Mark Allen. Data Structures and Algorithm Analysis in C. The Benjamin/Cummings Publishing Company Inc. 1993.
Section 4.4 covers single and double rotation of AVL trees.
This web page was created by: