How to implement self adjusting Binary Search Tree?

Question

I was reading more on the binary search tree and then I found out about another variant of Binary Search Tree which is Splay tree and I am trying to implement it but somehow I got stuck.

So the algorithm which looks to me is -

To insert a node x into a splay tree:

• First insert the node as with a normal binary search tree.
• Then splay the newly inserted node x to the top of the tree.

I guess, I am able to make the first point work in the above algo.. But not sure what should I do here for the second point?

public class SplayTreeTest<T extends Comparable<T>> extends BinarySearchTree<SplayTreeTest.TNode<T>,T> {

    protected static class TNode<T> extends BinarySearchTree.BSTNode<TNode<T>,T> {  }

    public SplayTreeTest(Comparator<T> c) {
        super(new TNode<T>(), c);
    }

    public SplayTreeTest() {
        this(new DefaultComparator<T>());
    }
    public void splayIt(TNode<T> u) {
        // not sure what should I do here?
        // so that addItem and findItem works?

    }

    public boolean addItem(T x) {
        TNode<T> u = newNode(x);
        if (!super.add(u)) return false;
        splayIt(u);
        return true;
    }

    public T findItem(T x) {
        TNode<T> u = super.findLast(x);
        if (u != null) 
            splayIt(u);
        return u != null && u.x.equals(x) ? x : null;
    }   
}

Can anyone help me with this? BinarySearchTree code is here for reference.

Answer 1

Expanding on my comment, if you start with this Splay Tree and insert 5, here are the steps to get it to the root:

  2            2            2              2              2               5
 / \          / \          / \            / \            / \            /   \
1   4        1   4        1   4          1   4          1   5          2    14
     \            \            \              \            / \        / \   / \
     14           14           14              5          4  14      1   4 6  18
     / \          / \        /    \             \            / \              /
    6  18 =>     6  18 =>   5      18 =>        14   =>     6  18 =>         17
       /        /   /        \     /            / \            /            /
      17       5   17         6   17           6  18          17           15
     /            /              /                /          /       
    15           15             15               17         15
                                                /
                                               15

Answer 2

The reference implementation implements top-down splaying. Even if you need it in Java, the C reference implementation is really good for working out the details:

Answer 3

Look at the source code of java.util.TreeMap.