EECE 352: PS 12

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

1. Why do we need the for loop in line 19?
2. What do the variables LeftTreeMax and RightTreeMin contain and why do we need these variables?
3. 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;
}