我阅读了更多关于二叉搜索树的内容,然后我发现了二叉搜索树的另一个变体,即 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供引用。
最佳答案
扩展我的评论,如果您从这个 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
关于java - 如何实现自调整二叉搜索树?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22160973/