For all internal nodes in the tree (assuming node elements are Comparable):
( left.isExternal() || left.element().compareTo(this.element()) <= 0 ) &&(right.isExternal() ||right.element().compareTo(this.element()) >= 0 )
height().
invariant for a BST node above
&& // height balanced
( isExternal() || Math.abs(left.height() - right.height()) <= 1 )
&& // check on height
( isExternal() ? height() == 0
: height() == 1 + Math.max(left.height() - right.height())
5, 2, 1, 6, 8, 3, 4
5* 2
/ => / \
2 (single) 1 5
/
1
2 2
/ \ / \
1 5* 1 6
\ => / \
6 (single) 5 8
\
8
2* 2* 5
/ \ / \ / \
1 6 => 1 5 => 2 6
/ \ (double 1) / \ (double 2) / \ \
5 8 3 6 1 3 8
/ \
3 8
Final Tree: 5
/ \
2 6
/ \ \
1 3 8
\
4
5 6* 6* 3
/ \ / \ / \ / \
2 6 => 2 8 => 3 8 => 2 6
/ \ \ (remove) / \ (double 1) / \ (double 2) / / \
1 3 8 1 3 2 4 1 4 8
\ \ /
4 4 1
3 6
\ / \
6 3 8
/ \ => \
4 8 (single) 4
Note: by convention, when the left-right and right-right grandchildren
have equal height, we choose a single rotation (See G&T, page 399).
8 4
/ => / \
3 (double) 3 8
\
4
3. Insertion and Removal in (2,4) Trees
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
+-----+
| 3 |
+---------+ +-----+
| 1 2 3 4 | => / \
+---------+ +-----+ +-----+
| 1 2 | | 4 |
+-----+ +-----+
+-----+ +---------+
| 3 | | 3 6 |
+-----+ +---------+
/ \ => / | \
+-----+ +---------+ +-----+ +-----+ +-----+
| 1 2 | | 4 5 6 7 | | 1 2 | | 4 5 | | 7 |
+-----+ +---------+ +-----+ +-----+ +-----+
+---------+ +-------------+
| 3 6 | | 3 6 9 |
+---------+ +-------------+
/ | \ => / | | \
+-----+ +-----+ +----------+ +-----+ +-----+ +-----+ +----+
| 1 2 | | 4 5 | | 7 8 9 10 | | 1 2 | | 4 5 | | 7 8 | | 10 |
+-----+ +-----+ +----------+ +-----+ +-----+ +-----+ +----+
+-------------+ +----------------------+
| 3 6 9 | | 3 6 9 12 |
+-------------+ => +----------------------+
/ | | \ / | | | \
+---+ +---+ +---+ +-------------+ +---+ +---+ +---+ +-----+ +----+
|1 2| |4 5| |7 8| |9 10 11 12 13| |1 2| |4 5| |7 8| |10 11| | 13 |
+---+ +---+ +---+ +-------------+ +---+ +---+ +---+ +-----+ +----+
+-------+
| 9 |
+-------+
/ \
+---------+ +------+
=> | 3 6 | | 12 |
+---------+ +------+
/ | \ / \
+---+ +---+ +---+ +-----+ +----+
|1 2| |4 5| |7 8| |10 11| | 13 |
+---+ +---+ +---+ +-----+ +----+
+-------+ +-------+
| 9 | | 9 |
+-------+ +-------+
/ \ / \
+-----+ +----+ +-----+ +----+
| 3 6 | | 12 | => | 4 6 | | 12 |
+-----+ +----+ +-----+ +----+
/ | \ / \ / | \ / \
+--+ +---+ +---+ +-----+ +-----+ +---+ +---+ +---+ +-----+ +-----+
| | |4 5| |7 8| |10 11| |13 14| | 3 | | 5 | |7 8| |10 11| |13 14|
+--+ +---+ +---+ +-----+ +-----+ +---+ +---+ +---+ +-----+ +-----+
+-------+ +-------+
| 9 | | 9 |
+-------+ +-------+
/ \ / \
+------+ +------+ +-----+ +------+
| 4 6 | | 12 | => | 6 | | 12 |
+------+ +------+ +-----+ +------+
/ | \ / \ / \ / \
+--+ +---+ +---+ +-----+ +-----+ +---+ +---+ +-----+ +-----+
| | | 5 | |7 8| |10 11| |13 14| |4 5| |7 8| |10 11| |13 14|
+--+ +---+ +---+ +-----+ +-----+ +---+ +---+ +-----+ +-----+
+-------+ +-------+
| 9 | | 9 |
+-------+ +-------+
/ \ / \
+-----+ +------+ +-----+ +------+
| 6 | | 12 | => | 7 | | 12 |
+-----+ +------+ +-----+ +------+
/ \ / \ / \ / \
+---+ +-----+ +-------+ +-------+ +---+ +---+ +-------+ +-------+
| | | 7 8 | | 10 11 | | 13 14 | | 6 | | 8 | | 10 11 | | 13 14 |
+---+ +-----+ +-------+ +-------+ +---+ +---+ +-------+ +-------+
+-------+ +-------+
| 9 | | 9 |
+-------+ +-------+
/ \ / \
+-----+ +------+ +---+ +------+
| 7 | | 12 | => | | | 12 |
+-----+ +------+ +---+ +------+
/ \ / \ | / \
+---+ +-----+ +-------+ +-------+ +--------+ +-------+ +-------+
| | | 8 | | 10 11 | | 13 14 | | 7 8 | | 10 11 | | 13 14 |
+---+ +-----+ +-------+ +-------+ +--------+ +-------+ +-------+
+---------+
| 9 12 |
=> +---------+
/ | \
+-----+ +-------+ +-------+
| 7 8 | | 10 11 | | 13 14 |
+-----+ +-------+ +-------+
+---------+ +----------+
| 9 12 | | 10 12 |
+---------+ +----------+
/ | \ => / | \
+---+ +-------+ +-------+ +-----+ +----+ +-------+
| | | 10 11 | | 13 14 | | 9 | | 11 | | 13 14 |
+---+ +-------+ +-------+ +-----+ +----+ +-------+
+----------+ +------+
| 10 12 | | 12 |
+----------+ +------+
/ | \ => / \
+---+ +----+ +-------+ +-------+ +-------+
| | | 11 | | 13 14 | | 10 11 | | 13 14 |
+---+ +----+ +-------+ +-------+ +-------+
+------+ +------+
| 12 | | 13 |
+------+ +------+
/ \ => / \
+---+ +-------+ +----+ +----+
| | | 13 14 | | 12 | | 14 |
+---+ +-------+ +----+ +----+
+------+
| 13 |
+------+ +-------+
/ \ => | 13 14 |
+---+ +----+ +-------+
| | | 14 |
+---+ +----+
4. Height of AVL Trees
N of items in an AVL tree
of height H is Fib(H+3)-1
The recurrence relation (see lecture slides or text book) is:
N(0) = 1
N(1) = 2
N(H) = 1 + N(H-1) + N(H-2) if H > 1
Compare this with Fib(H+3):
H : 0 1 2 3 4 5 ..
N(H) : 1 2 4 7 12 20 ..
K : 0 1 2 3 4 5 6 7 8 ..
Fib(K): 0 1 1 2 3 5 8 13 21 ..
Required to prove: N(H) = Fib(H+3) - 1
Proof by induction:
When H=0, N(0) = 1 = Fib(3) - 1
When H=1, N(1) = 2 = Fib(4) - 1
Inductive assumption: assume result for values up to H > 1:
Then
N(H) = 1 + N(H-1) + N(H-2) [given recurrence]
= 1 + ( Fib(H+2) - 1 ) + ( Fib(H+1) - 1 ) [inductive assumption]
= Fib(H+3) - 1 [defn of Fib]
as required
N for a given H?
2^(h+1) - 1
The minimum possible height is h = 10.
fib(16) = 987 and fib(17) = 1597. It follows that for a tree of height h = 15, n >= 1596. So with n =1023, the maximum height is h = 14.
Minimum: h = 20.
fib(30) = 832040, fib(31) = 1346269, so maximum height is: h = 28.
CHALLENGE Questions (for the mathematically inclined)
N items are there?N=0, show that successive values are:
1,1,2,5,14... by enumerating the possible tree shapes.
These numbers are called Catalan numbers.
n=0: 1 tree:
the empty tree
n=1: 1 tree
with a single root
n=2: 2 trees
x x
/ \
x x
n=3: 5 trees
x x x x x
/ / / \ \ \
x x x x x x
/ \ / \
x x x x
n=4: 14 trees
x x x x x
/ / / / /
x x x x x
/ / / \ \ \
x x x x x x
/ \ / \
x x x x
x x
/ \ / \
x x x x
/ \
x x
x x
/ \ / \
x x x x
/ \
x x
x x x x x
\ \ \ \ \
x x x x x
/ / / \ \ \
x x x x x x
/ \ / \
x x x x
Derive a recurrence relation for the Catalan numbers, and an explicit formula in terms of N.
Let t(n) be the number of different binary trees shapes with n items.
We have:
t(0) = 1, [there is 1 empty tree]
With n+1 nodes, we can count the number of trees of different shapes,
by allocating 1 position at the root, and then allocating k nodes to the left
and n - k nodes to the right subtree, for each value of k = 0 .. n.
So we get the following recurrence relation:
t(n+1) = t(0)*t(n) + t(1)*t(n-1) + t(2)*t(n-2) + .. + t(n) * t(0)
The solution to this is (you can verify this using a proof by induction) is:
t(n) = (2n)! / ( n! * (n+1)! )
Here is a tabulation:
n : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
t(n) : 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670
Asymptotically, as the number of items increases by 1, the number of trees quadruples.
N pairs of parentheses?
For example: ()()()() and (())() are valid expressions, whereas (()))( is not.P ::= empty expression
| '(' P ')' P
Hint: think about binary trees representing parenthesised expressions.
For n = O: 1 valid expression
the empty expression
For n = 1: 1 valid expression
()
For n = 2: 2 valid expressions
(()) ()()
For n = 3: 5 valid expressions
((())) (()()) (())() ()(()) ()()()
For n = 4: 14 valid expressions
(((()))) ((()())) ((())()) (()(())) (()()())
((()))() (()())()
(())(()) (())()()
()((())) ()(()()) ()(())() ()()(()) ()()()()
The number of valid expressions with n pairs of parentheses is the same as the number
of binary trees with n items. The correspondence can be seen from the grammar if you
interpret it as a binary tree generator: the '(' P ')' is an instruction to make a left sub-tree,
and the following P is an instruction to make a right sub-tree.
Also note that this grammar corresponds to valid sequences of stack operations, where
P represents sequences of pushes and pops, with no pops on an empty stack,
'(' represents the pushes, and
')' represents the pops.
H are there?
Let c(h) be the number of AVL trees with height h.
For h = 0, c = 1; h = 1, c = 1; h = 2, c = 3;
Recurrence for h+1:
to get an AVL tree of height (h+1), both sub-trees must have height (h-1) or h,
and at least one of them must have height h, so
c(h+1) = c(h) * c(h) + c(h-1) * c(h) + c(h) * c(h-1)
= c(h) * ( c(h) + 2*c(h-1) )
This recurrence has no simple closed form solution that I am aware of. Here
are the first few terms (I used Haskell to generate these values):
h c
0 1
1 1
2 3
3 15
4 315
5 108675
6 11878720875
7 141106591466142946875
8 19911070158545297149037891328865229296875
9 39645071485851304455281818836461083701971963604987697945684203361075660
0341796875
10 15717316931182601571960181064602210498576956361668877698434766859653851
16930439741446186333028489448438308850843238872672700842128674239678896
45644664764404296875
This grows very very quickly. It is easy to derive a lower bound for this sequence:
c(h) > c(h-1) for h > 1
So, using the recurrence above:
c(h+1) > c(h) * (c(h) + 2*c(h)) = 3 * c(h)^2
The recurrence:
c(2) >= 1
c(h+1) >= 3 * c(h)^2
has the solution (provable by induction):
c(h) >= 3 ^ (2 ^ (h-1))
This double exponential provides a (very conservative) lower bound on the number
of AVL trees of height h.
How may differently shaped AVL trees with N items are there?
Because AVL tree construction is constrained to be be balanced, to
derive a recurrence for this, we need to factor the constraint in, by
including the height h as a parameter of the recursive construction.
Otherwise the construction is similar to that for binary trees considered
above.
Let b(n,h) be the number of AVL trees with n items and height h, and
a(n) the number with n items.
Then:
a(n) = sum [ b(n, h) | h <- [0 .. ] ]
and
b(n, 0) | n == 0 = 1
| otherwise = 0
b(n, 1) | n == 1 = 1
| otherwise = 0
b(n, h) = sum [ b(k, h-1) * b(n-k-1, h-1) | k <- [0..n-1] ]
+ 2 * sum [ b(k, h-2) * b(n-k-1, h-1) | k <- [0..n-1] ]
Here is the first part of the table for b:
n\h | 0 1 2 3 4 5 6 7
----|-------------------------------------------
0 | 1 0 0 0 0 0 0 0
1 | 0 1 0 0 0 0 0 0
2 | 0 0 2 0 0 0 0 0
3 | 0 0 1 0 0 0 0 0
4 | 0 0 0 4 0 0 0 0
5 | 0 0 0 6 0 0 0 0
6 | 0 0 0 4 0 0 0 0
7 | 0 0 0 1 16 0 0 0
8 | 0 0 0 0 32 0 0 0
9 | 0 0 0 0 44 0 0 0
10 | 0 0 0 0 60 0 0 0
11 | 0 0 0 0 70 0 0 0
12 | 0 0 0 0 56 128 0 0
13 | 0 0 0 0 28 448 0 0
14 | 0 0 0 0 8 864 0 0
15 | 0 0 0 0 1 1552 0 0
16 | 0 0 0 0 0 2720 0 0
17 | 0 0 0 0 0 4288 0 0
18 | 0 0 0 0 0 6312 0 0
19 | 0 0 0 0 0 9004 0 0
20 | 0 0 0 0 0 11992 4096 0
21 | 0 0 0 0 0 14372 22528 0
22 | 0 0 0 0 0 15400 67584 0
23 | 0 0 0 0 0 14630 159744 0
24 | 0 0 0 0 0 11968 334080 0
25 | 0 0 0 0 0 8104 644992 0
26 | 0 0 0 0 0 4376 1195008 0
27 | 0 0 0 0 0 1820 2158912 0
28 | 0 0 0 0 0 560 3811904 0
29 | 0 0 0 0 0 120 6617184 0
30 | 0 0 0 0 0 16 11307904 0
31 | 0 0 0 0 0 1 18978576 0
32 | 0 0 0 0 0 0 31327104 0
and some values for a(n) (the row sums):
n : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
a(n): 1 1 2 1 4 6 4 17 32 44 60 70 184 476 872 1553 2720 4288 6312 9004 16088
n : 21 22 23 24 25 26 27 28 29 30 31 32
a(n): 36900 82984 174374 346048 653096 1199384 2160732 3812464 6617304 11307920 18978577 31327104
By looking at the trend asymptotically, as the number of items increases by 1,
the number of AVL trees approximately doubles (actually it seems closer to a factor of 1.9).
Note that the number of trees c(h) for a given height h, as previously determined,
also appears here as the column sums.
See Haskell implementations for these AVL tree
counting functions if you wish.