Our implementation supports the following tree operations:

binary tree operations

• search x
• insert x
• delete x

• splay x
• splay_insert x
• splay_delete x

• insert_fast x1 x2 x3 ...
• delete_fast x1 x2 x3 ...

1. Trees have the important property that the left child y of a node x has a smaller key than x. Similarly, The key of a right child z of node x is bigger than the key at x. (Observe that the nodes read from left to right are in order of increasing keys.)
   Is this invariant also true at every step of each of the tree operations? Can you find the one exception?
   

2. Consider the effect of insert x followed by delete x on a tree T.
   Can you find examples where the result is the original tree T? Is it possible to get a different tree?
   What about splay_insert and splay_delete?

3. Are delete operations commutative? (i.e. does one obtain the same tree regardless of the order in which a collection of delete operations are performed?) What about splay_delete?

4. Consider the tree on 15 nodes in the form of a linear list.
   Observe the effect of splay x, where x is the key of the leaf.
   Can you find a general expression for the depth-change of the tree in such cases?

5. Is it possible that the depth of a tree increases during a splay operation?

6. Consider the complete tree on 15 nodes. Can you tell which operation generates the following tree T_1? Which two operations lead to tree T_2? Use the visualizer to help.

   Tree T_1	Tree T_2