Written Assignment #6 Answers
Assignment Questions
1.
a) 12
b) 8
c) 6
d) 12
2.
a) 1 4 5 7 8 9 10 13 16 18 24 30
b) 2
c) 1
d) 12
e) 12
3. index : 0 1 2 3 4 5 6 7 8 9 10 11
array : 1 4 5 7 8 9 10 13 16 18 24 30
a) step 1. low=0, high=11, mid=5, array[m]=9 > 16
step 2. low=6, high=11, mid=8, array[m]=16 == 16 FOUND in 2 steps
b) step 1. low=0, high=11, mid=5, array[m]=9 < 30
step 2. low=6, high=11, mid=8, array[m]=16 < 30
step 3. low=9, high=11, mid=10, array[m]=24 < 30
step 4. low=11, high=11, mid=11, array[m]=30 < 30 FOUND in 4 steps
c) Ceiling(lg 12) = 4
4.
a) 4
/ \
1 7
/ \
5 10
/ \
8 18
\ / \
9 13 30
\ /
16 24
b) 6
c) 5
d) 6
e) 17 would be the right son of 16
f) 4
/ \
1 7
/ \
5 9
/ \
8 18
/ \
13 30
\ /
16 24
5. Proof by contradiction
Assume that the node p has two children, left(p) and right(p).
By the definition of a binary search tree:
value(left(p)) < value(p), and
value(right(p)) > value(p).
We found p as the maximum (or minimum in right subtree), which implies that
this is impossible. Contradiction!
Hence, p can have at most one child.
6. 4 7 10 8 18 30 5 1 24 13 9 16
a) 10
/ \
7 24
/ \ / \
4 8 16 30
/ \ \ / \
1 5 9 13 18
Rotations occurred when we 10, 30, 24, and 16 are inserted.
AVL tree can be a little different by the last rotation.
b) 3
c) 4
d) 9
/ \
7 24
/ \ / \
4 8 16 30
/ \ / \
1 5 13 18
7.
a) 16
/ \
13 18
/ \
10 24
/ \
9 30
/
8
/
7
/
5
/
1
\
4
b) 9
c) 9
/ \
8 13
/ \
7 16
/ \
5 18
/ \
1 24
\ \
4 30
8.
Since x was successfully found, x becomes the root.
One rotation operation changes locations of nodes at most depth 2.
For single rotation, at most 1, for double one, 2.
case 1) if (x == y) or
(y is not in the tree and predecessor[y] == x)
Don't have to do anything, x is still the root.
case 2) Otherwise, (y or pred[y] will be moved to root)
Only the last rotation will affect the location of x (= root of the tree).
If the last rotation is one of the first two cases of double rotation
(listed on slide SC14), x will be the grandchild of the new root
(which is either y or pred[y]).
If it is the third or fourth case of double rotation, x will be child of
the root. Also, if it's a single rotation, x will be child of the root.
9.
a)
+-----+------+
|LEVEL|HEADER|
+-----+------+ +--+ +---+
| 3 | o----------------------------------------------->| o-------------------------->| |
+-----+------+ +--+ +--+ +--+ | |
| 2 | o----------------------->| o-------------------->| o-------------------->| o-->| |
+-----+------+ +--+ +--+ +--+ +--+ +--+ +--+ |NIL|
| 1 | o----------->| o-------->| o-------->| o-------->| o-------->| o-------->| o-->| |
+-----+------+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ | |
| 0 | o----->| o-->| o-->| o-->| o-->| o-->| o-->| o-->| o-->| o-->| o-->| o-->| o-->| |
+-----+------+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +---+
| 1| | 4| | 5| | 7| | 8| | 9| |10| |13| |16| |18| |24| |30| |INF|
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +---+
b) 4
c) 4
10.
a) 10
/ \
/ \
/ \
5,8 18
/ | \ / \
1,4 7 9 13,16 24,30
You can get a different tree by using only split.
b) 4
c)
10
/ \
/ \
/ \
5 18
/ \ / \
1,4 7,9 13,16 24,30
d)
10
b/ \b
5 18
b/ \b b/ \b
1 7 13 24
r\ r\ r\ \r
4 9 16 30
11.
Observation:
Longest path from the root a leaf in red-black tree (rb-tree) consists of
n nodes connected by black edges, for the original nodes, and up
to n nodes connected by red edges, where n is the depth of the 2-3
tree. Each node could have at most two values, so 2 nodes in the
red-black tree connected by a red edge. Thus the maximum depth is 2n.
Proof by induction on n.
base case:
n = 1
There can be only one node in B-tree and it can have at most 2 key
values So the corresponding rb-tree has depth 2.
induction step:
assume that for n<=k, rb-tree's depth is at most 2n.
prove for n = k+1:
Adding one to the depth of an rb-tree means adding at most one
more node along the path from root to leaf.
We know from the induction step that a path from the root to a
node of depth k has length of at most (2k).
Adding the new node adds one black edge, and, if it has the 2
values, also one red edge.
So the maximum total length <= (2k) + 2 = 2(k+1). Thus true for
all values of n.
Solutions by Kyongil Yoon, May 9, 1997