CS计算机代考程序代写 AVL algorithm Problem Set 4 Solutions

Problem Set 4 Solutions

Problem Set 4

Problem 1 Consider a tree storing 100,000 entries. What is the worst-case height of T

in the following cases?

a. T is an AVL tree.
b. T is a (2,4) tree.
c. T is a binary search tree.
d. T is a splay tree.

Solution:

a. Let n(h) be the minimum number of nodes of an AVL tree with height h.
We have:

n(h)=n(h-1)+n(h-2)+1 (h2), where n(0)=1 and n(1)=2.

The first 6 n(h)’s (h=0, 1, …, 5) are: 1, 2, 4, 7, 12, 20.

Recall that the first 9 Fibonacci numbers Fi (i=0, 1, … 8) are: 0, 1, 1, 2, 3, 5,

8, 13, 21.

Notice that n(h) = Fh+3 – 1, where Fh+3 is a Fibonacci number with Fh+3 =

Fh+2 + Fh+1.

It is known that Fh = 
h/51/2, where =(1+51/2)/2 is the golden ratio.

Therefore, we have n(h) = h+3/51/2 – 1, and h = log(51/2(n(h)+1))/log  – 3.

By applying the above formula, we get h = 22 for an AVL tree storing

100,000 entries.

b. In the worst-case height, a (2, 3) tree is a complete binary search tree, where
there are 2i nodes at depth i. Let n be the number of nodes, the height h

satisfies the following constraint:

n=20 + 21 +22+ … + 2h (1)

Multiplying both sides by 2, we have

2n=21 + 22 +23+ … + 2h + 2h+1 (2)

So, we have n=2h+1 -1. Therefore, h=log (n+1)-1.

Hence, the height of a (2,4) tree storing n entries is at most floor(log(n+1)-

1), where floor(x) is the largest integer that is no larger than x. Therefore,

the worst-case height of T is floor(log(100,001)-1) =15.

c. The worst-case height of T is 99,999.

d. The worst-case height of T is 99,999.

Problem 2 What does a splay tree look like if its entries are accessed in increasing

order of their keys?

Solution: Assume that there are n entries in the splay tree and ki  ki+1 (i=1, 2, n-1),

where ki is the key of entry i. After entry 1 is assessed, it is moved to the root. Since

k1 is the smallest key, all other entries are in the right subtree of entry 1. Similarly,

after entry 2 is accessed, entry 2 is moved to the root and entry 1 becomes the left

child of entry 2. After entry n is accessed, entry n is moved to the root and entry i-1 is

the left child of entry i (i=2, 3, …, n). The resulting splay tree is shown as follows.

Problem 3 Assuming that T1, T2, T3, and T4 are AVL trees of height h, alter the

following binary search tree to yield an AVL tree.

Solution:

Problem 4 Design an algorithm findAll(k) for finding all the entries with the key k in a

binary search tree T, and show that it runs in time O(h+s), where h is the height of T

and s is the size of the collection returned.

T4

K3

T1

K2
11

1

K1

1

T2 T3

T4

K1
11

1

T1 K2
11

1

K3

1

T2 T3

Kn

Kn-1

Kn-2

K1

Solution: In a binary search tree, we need to make a rule for placing entries with

duplicate keys. Entries with duplicate keys can be inserted in the left subtree or the

right subtree of a node with the same key. Therefore, when we find the first node

with the same key, we can either search left subtree or the right subtree for all the

entries with the same key. However, in case of AVL trees, tri-node restructuring may

spoil this order, that is, entries with duplicate keys may be stored in both the left

subtree and the right subtree of the node with the same key.

The key idea of the algorithm for finding all the entries with the key k is that after we

find the first node, we search the subtree rooted at the first node that contains all the

entries with the key k. The algorithm is shown as follows:

Algorithm findAll(k)

Input: The search key k, the root v of the binary search tree T

Output: A list L containing all the entries with the key k

{

Create an empty list L;

while ( v != NULL )

{

if (v.key=k)

{

findAllEntries(v, L);

return L;

}

else

if ( v.key > k)

v=v.left;

else

v=v.right;

}

return L;

}

Algorithm findAllEntries(v, L)

Input: A node v with the key k and a List L

Output: All the entries with the key k in the subtree rooted at v

{

// We use recursive pre-order traversal to find all the entries with the key k

in the subtree rooted at v

if (v.key=k)

{

Add v to L;

if ( v.left != NULL)

FindAllEntries(v.left, L)

if (v.right !=NULL)

FindAllEntries(v.right, L);

}

return; // Traversal returns when v does not contain the key k

}

Time complexity analysis:

1. Finding the first node with the key k takes O(h) time.
2. Since at 2s nodes are visited by findAllEntries(), traversing the subtree rooted

at the first node takes O(s) time.

Therefore, this algorithm takes O(h+s) time.

Problem 5 Show that after the tri-node restructuring operation on the subtree rooted at

the node z, the new subtree is an avl tree.

Proof: Tri-node restructuring occurs only when a new node is inserted into an avl tree

or when a done is removed from an avl tree. Next, we consider the cases for inserting

a node. The proof for deleting a node is similar.

Let height (v) be the height of a subtree v or the height of the subtree rooted at v.

There are four cases:

Case 1:

By the definition of x, y, z, before tri-node restructuring we have the following

equations:

height(y)=height(T0)+2 (1)

height(x)≤height(T1)+1 (2)

|height(T3)-height(T2)|≤1. (3)

From the above equations, we have:

|height(T0)-height(T1)|≤1 (4)

|max{height(T0), height(T1)}-max{height(T2), height(T3)}|≤1 (5)

Equations (3) and (4) imply that in the new tree both z and x satisfy the height

difference constraint. Equation (5) implies that in the new subtree, the root y satisfies

the height difference constraint. Therefore, the new subtree rooted at y is an avl tree.

Case 2: This case is symmetrical to Case 1.

Case 3:

By the definition of x, y, z, before tri-node restructuring we have the following

equations:

height(y)=height(T0)+2 (1)

height(x)≤height(T3)+1 (2)

|height(T1)-height(T2)|≤1. (3)

From the above equations, we have:

|height(T0)-height(T1)|≤1 (4)

|max{height(T0), height(T1)}-max{height(T2), height(T3)}|≤1 (5)

Case 4: This case is symmetrical to Case 3.

Problem 6 Let T and U be (2,4) trees with n and m entries, respectively, such that all

the entries in T have keys less than the keys of all the entries in U. Describe an O(log

n + log m)-time algorithm for merging T and U into a single (2,4) tree.

Solution: Let ht and hu be the heights of T and U, respectively. Consider two possible

cases:

Case 1. hthu. Do the following:
a. Find the entry e with the smallest key in U.
b. Remove the entry e from U.

c. Let hu be the new height of U.

d. If ht>hu , do the following:

i. Insert the entry e into the rightmost node v of T at height hu +1, and
make the root of U the rightmost child of v.

ii. If there is an overflow, handle the overflow.

e. If ht=hu , do the following:
i. Create a new node v, and insert the entry e into v.

ii. Make T the left child of v and U the right child of v.

Case 2. ht= the total number of entries in the tree )

return IndexOutOfBound(); // error

return findIndex(i, root);

}

Algorithm findIndex(i, v)

Input: The index i and the current node v

Output: The position in the binary search tree of the entry at index i.

{

if ( (i=0 and left(v)=null) or left(v).size=i)

return v; // found

if (ithe key of e)

// e is in the left subtree, so the running number of inorder predecessors of

// e is unchanged

return indexOf(e, left(v), i);

else // e is in the right subtree and the running number of inorder

// predecessors of e increases by left(v).size+1

if (left(v)null)

return indexOf(e, right(v), i+left(v).size+1);

else

return indexOf(e, right(v), i+1);

}

Time complexity analysis: Both algorithms traverse the tree along one path from the

root to a leaf node in the worst case, and it takes O(1) time to visit each node.

Therefore, both algorithms take O(h) time, where h is the height of the tree.