java - 如何实现自调整二叉搜索树？

Question

我阅读了更多关于二叉搜索树的内容，然后我发现了二叉搜索树的另一个变体，即 Splay树，我正在尝试实现它，但不知何故我被卡住了。

所以在我看来算法是 -

将节点 x 插入到伸展树(Splay Tree)中:

• 首先像普通的二叉搜索树一样插入节点。
• 然后将新插入的节点x展开到树的顶部。

我想，我能够使上述算法中的第一点起作用。但不确定我应该为第二点做什么？

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

谁能帮我解决这个问题？ BinarySearchTree 代码是 here供引用。

Answer 1

扩展我的评论，如果您从这个 Splay Tree 开始并插入 5，则以下是将其获取到根的步骤:

  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