我正在阅读有关二叉搜索树的更多内容，然后发现了另一种变体Splay树，我正在尝试实现它，但某种程度上卡住了。
所以，我认为算法如下：
要将节点x插入Splay树中：
所以，我认为算法如下：
要将节点x插入Splay树中：
- 首先像普通的二叉搜索树一样插入节点。
- 然后将新插入的节点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;
}
}
有人能帮我吗？二叉搜索树代码在这里作为参考。