Problem 1: (15%) Show the bottom-up Splay tree that results after inserting all of the following numbers into a bottom-up splay tree.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13.
Problem 2: (15%) Show the bottom-up Splay tree that results after each of the following operations are performed on it, in the order shown.
Insert(1) Insert(10) Insert(5) Insert(8) Insert(7) Insert(6) Insert(4) Insert(3) Insert(12) Find(1) Find(2) Find(3) Find(1) Delete(3) Delete(1) Delete(2)
Problem 3: (15%) Show the top-down Splay tree that results after inserting all of the following numbers into a top-down splay tree.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13.
Problem 4: (15%) Show the top-down Splay tree that results after each of the following operations are performed on it, in the order shown.
Insert(1) Insert(10) Insert(5) Insert(8) Insert(7) Insert(6) Insert(4) Insert(3) Insert(12) Find(1) Find(2) Find(3) Find(1) Delete(3) Delete(1) Delete(2)
Problem 5: (40%) In Figure 21.17 (page 697) from the book (reproduced below):
template <class Etype> void SplayTree<Etype>:: Splay( const Etype & X, BinaryNode<Etype> * & T ) { BinaryNode<Etype> *LeftTreeMax, *RightTreeMin, Header; Header.Left = Header.Right = NilNode; LeftTreeMax = RightTreeMin = &Header; // Copy X to NilNode to guarantee match NilNode->Element = X; for( ; ; ) if( X < T->Element ) { if( X < T->Left->Element ) T = RotateWithLeftChild( T ); if( T->Left == NilNode ) break; // Link Right RightTreeMin->Left = T; RightTreeMin = T; T = T->Left; } else if( T->Element < X ) { if( T->Right->Element < X ) T = RotateWithRightChild( T ); if( T->Right == NilNode ) break; // Link Left LeftTreeMax->Right = T; LeftTreeMax = T; T = T->Right; } else break; LeftTreeMax->Right = T->Left; RightTreeMin->Left = T->Right; T->Left = Header.Right; T->Right = Header.Left; }