Next: 5.6.3 23 Trees and BTrees
Up: 5.6 Problems
Previous: 5.6.1 AVL Trees
 1.
 Show that any arbitrary nnode binary tree can be
transformed into any other arbitrary nnode binary tree
using O(n) rotations.
 2.
 Draw the complete binary search tree of height 3 on the keys
{1, 2,^{ ... }, 15}. Add the NIL leaves and colour the nodes in three
different ways such that the blackheights of the resulting
redblack trees are 2, 3, and 4.
 3.
 Show the redblack trees that result after successively
inserting the keys 41, 38, 31, 12, 19, 8 into an initially empty
redblack tree. Now show the RB trees that result from the
successive deletion of the keys in the order 8, 12, 19, 31,
31, 38, 41.
 4.
 Suppose that a node x is inserted into an RB tree and
then immediately deleted. Is the resulting RB tree the same
as the initial RB tree? Justify your answer.
 5.
 Construct the RBtrees that result by
repeated insertions in each of the following
cases, starting from an initially empty tree.
 (a)

1, 2,..., 15
 (b)

8, 4, 12, 6, 14, 2, 10, 7, 11, 5, 9, 3, 8, 1, 15
 (c)

1, 2, 3, 4, 5, 6, 7, 15, 14, 13, 12, 11, 10, 9, 8
Next: 5.6.3 23 Trees and BTrees
Up: 5.6 Problems
Previous: 5.6.1 AVL Trees
eEL,CSA_Dept,IISc,Bangalore