**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):

- Why do we need the for loop in line 19?
- What do the variables LeftTreeMax and RightTreeMin contain and why do we need these variables?
- The book explains that this is the implementation of a top-down splay algorithm. The book also explains the three rotations, zig, zig-zig, and zig-zag. Next to the appropiate lines in the code below, explain where each of these rotations are performed. Explain any differences between the way things happen in the code and the way they are explained in the book.

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; }

Jose M. Vidal Last modified: Mon Nov 22 18:24:42 EST 1999