Joining and splitting 2-3-4 trees The join operation takes

Chapter 18, Problem 18-2

(choose chapter or problem)

Joining and splitting 2-3-4 trees The join operation takes two dynamic sets S0 and S00 and an element x such that for any x0 2 S0 and x00 2 S00, we have x0 :key < x:key < x00:key. It returns a set S D S0 [ fxg [ S00. The split operation is like an inverse join: given a dynamic set S and an element x 2 S, it creates a set S0 that consists of all elements in S fxg whose keys are less than x:key and a set S00 that consists of all elements in S fxg whose keys are greater than x:key. In this problem, we investigate how to implement these operations on 2-3-4 trees. We assume for convenience that elements consist only of keys and that all key values are distinct. a. Show how to maintain, for every node x of a 2-3-4 tree, the height of the subtree rooted at x as an attribute x:height. Make sure that your implementation does not affect the asymptotic running times of searching, insertion, and deletion. b. Show how to implement the join operation. Given two 2-3-4 trees T 0 and T 00 and a key k, the join operation should run in O.1 C jh0 h00j/ time, where h0 and h00 are the heights of T 0 and T 00, respectively. c. Consider the simple path p from the root of a 2-3-4 tree T to a given key k, the set S0 of keys in T that are less than k, and the set S00 of keys in T that are greater than k. Show that p breaks S0 into a set of trees fT 0 0; T 0 1;:::;T 0 mg and a set of keys fk0 1; k0 2;:::;k0 mg, where, for i D 1; 2; : : : ; m, we have y< for any keys y 2 T 0 i1 and 2 T 0 i . What is the relationship between the heights of T 0 i1 and T 0 i ? Describe how p breaks S00 into sets of trees and keys. d. Show how to implement the split operation on T . Use the join operation to assemble the keys in S0 into a single 2-3-4 tree T 0 and the keys in S00 into a single 2-3-4 tree T 00. The running time of the split operation should be O.lg n/, where n is the number of keys in T . (Hint: The costs for joining should telescope.)