The join operation takes two dynamic sets S and S and an element x such that for

Question:

The join operation takes two dynamic sets S′ and S′′ and an element x such that for any x′ ∈ S′ and x′′ ∈ S′′, we have x′.key < x.key < x′′.key. It returns a set S = S′ ⋃ {x} ⋃ S′′. The split operation is like an "inverse" join: given a dynamic set S and an element x ∈ S, it creates a set S′ that consists of all elements in S – {x} whose keys are less than x:key and a set S′′ that consists of all elements in S – {x} 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′ and T′′ and a key k, the join operation should run in O(1 + |h′ - h′′|) time, where h′ and h′′ are the heights of T′ and T′′, respectively.

c. Consider the simple path p from the root of a 2-3-4 tree T to a given key k, the set S′ of keys in T that are less than k, and the set S′′ of keys in T that are greater than k. Show that p breaks S′ into a set of trees {T′0, T ′1, . . . ,T′ m} and a set of keys {k′1, k′2, . . . ,k′m}, where, for i = 1,2, . . . ,m, we have y < ki < z for any keys y ∈ T i-1 and z ∈ T i. What is the relationship between the heights of T′ i-1 and Ti? Describe how p breaks S′′ 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 S into a single 2-3-4 tree T′ and the keys in S′′ into a single 2-3-4 tree T′′. The running time of the split operation should be O(lg n), where n is the number of keys in T.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Introduction to Algorithms

ISBN: 978-0262033848

3rd edition

Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

Question Posted: