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

Question

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

所以在我看来，算法是-

null

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

Answer 1

在我的评论中，如果您从这个八字树开始并插入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