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′₀, T ′₁, . . . ,T′ _m} and a set of keys {k′₁, k′₂, . . . ,k′_m}, where, for i = 1,2, . . . ,m, we have y < k^′_i < z for any keys y ∈ T^′ _i-1 and z ∈ T^′ _i. What is the relationship between the heights of T′ _i-1 and T^′_i? 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.