Problem set week 6

The idea with this problem set is that you should practice on the following things:

• Binary search trees.

• AVL trees.

• Splay trees.

Exercises:

1. Implement a procedure which checks if a binary tree is an AVL tree (i.e. a search tree satisfying the AVL tree balancing invariant). The procedure's worst-case big-O time complexity should be as low as possible (assuming that tree elements can be compared in constant time).

2. Prove that the height of an AVL tree with n nodes is O(log n).

   Hint: Establish a lower bound on the number of nodes in an AVL tree of a given height, using the fact that 1+ϕ = ϕ², where ϕ is the golden ratio.

3. Implement a class for splay trees. The only public members of this class that you need to implement are
   • a constructor for an empty tree, and
   • a member method, which checks if a given element is a member of the tree.

   You can represent tree nodes using the following class:

   /**
    * Tree nodes.
    * <p>
    * The parent and child links are private to ensure that when
    * a child link is updated, the parent link of the child (if
    * any) is updated at the same time.
    */
   public class Node<A> {
       /** The parent node. */
       private Node<A> parent;
   
       /** The left subtree. */
       private Node<A> left;
   
       /** The right subtree. */
       private Node<A> right;
   
       /** The node contents. */
       public A contents;
   
       /**
        * Creates a node. Sets all parent/child pointers to null.
        */
       public Node(A contents) {
           this.contents = contents;
       }
   
       /**
        * Sets the left child.
        *
        * @param child The new left child. Can be null.
        */
       public void setLeft(Node<A> child) {
           left = child;
           if (child != null) {
               child.parent = this;
           }
       }
   
       /**
        * Sets the right child.
        *
        * @param child The new right child. Can be null.
        */
       public void setRight(Node<A> child) {
           right = child;
           if (child != null) {
               child.parent = this;
           }
       }
   
       /**
        * Returns the parent.
        */
       public Node<A> parent() {
           return parent;
       }
   
       /**
        * Returns the left child.
        */
       public Node<A> left() {
           return left;
       }
   
       /**
        * Returns the right child.
        */
       public Node<A> right() {
           return right;
       }
   }
   

Solutions.