Homework 5
Due Dates:
- Sections 1 & 3: Thursday, October 31, in class.
- Sections 2 & 4: Monday, November 4, in class.
-
Describe an algorithm for finding the successor of a key k in a balanced binary search tree in O( log n ) time. Can you do this in one pass (i.e., without going down the binary search tree more than once)? Describe your solution with a combination of pseudocode and English sentences.
Note: the successor of a key k is the smallest key k' such that k < k'.
-
How would you find the successor of a key in a B-Tree?
-
Suppose we modify a red-black tree in the following manner. Every black node will "absorb" its red children (if any). When a red child is absorbed by its black parent, its key is stored in the parent and all of the red child's children (which are grandchildren of the black parent) become the black parent's children. (Note: the resulting tree structure is no longer a binary tree.) How does the resulting search tree compare with the definition of a B-tree in our textbook for M=4?