1. Find a sequence of numbers which, when incrementally inserted into a red-blac

Question

1. Find a sequence of numbers which, when incrementally inserted into a red-black tree, causes the following sequence of rotations: left, right, left.

You may start with an initially non-empty tree, and you may insert numbers that
do not cause any rotations. But there should not be any additional rotations per-formed.
Draw the sequence of trees that you obtain after each insertion. For each such tree indicate the node that violates the red-black tree condition, indicate the nodes that participate in the rotation, the type of the rotation, and the subtrees that correspond to each other before and after the rotation.
Hint: Use a red-black tree demo from the web.

2. Suppose we insert the following values into a B-Tree with t = 3 in this order: 4, 9, 2, 14, 1, 7, 6, 10, 8, 4, 13, 11, 3, 5, 12
Draw the final B-Tree and each B-Tree before and after each split (i.e. you do not need to show the tree after every insertion).

3. Suppose you have a B-tree of minimum degree k and height h. What is the largest number of values that can be stored in such a B-tree?

Explanation / Answer

Red Black Trees A BST with more complex algorithms to ensure balance Each node is labeled as Red or Black. Path: A unique series of links (edges) traverses from the root to each node. –The number of edges (links) that must be followed is the path length In Red Black trees paths from the root to elements with 0 or 1 child are of particular interest

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.