致谢两位发明人
-
Daniel Sleator
Daniel_Sleator.png -
Robert Tarjan
Robert Tarjan.png
插入示例
伸展树插入示例.png
删除示例
伸展树删除示例.png
源代码示例
package cs.tsinghua.edu.chapter8;
import cs.tsinghua.edu.chapter5.BST;
import cs.tsinghua.edu.chapter5.Entry;
import cs.tsinghua.edu.chapter5.Node;
public class SplayTree extends BST {
public static void main(String[] args) {
//伸展树构建
SplayTree tree = new SplayTree();
Entry entry7 = new Entry(7, 7);
tree.insert(entry7);
Entry entry6 = new Entry(6, 6);
tree.insert(entry6);
Entry entry5 = new Entry(5, 5);
tree.insert(entry5);
Entry entry4 = new Entry(4, 4);
tree.insert(entry4);
Entry entry3 = new Entry(3, 3);
tree.insert(entry3);
Entry entry2 = new Entry(2, 2);
tree.insert(entry2);
Entry entry1 = new Entry(1, 1);
tree.insert(entry1);
//中序遍历
Iterable<Node> nodes = tree.inOrder(tree.root);
for (Node node : nodes) {
System.out.println(node);
}
// //搜索测试
// Node node1 = tree.search(entry1);
// System.out.println(node1);
//删除测试
tree.delete(entry2);
//中序遍历
Iterable<Node> nodes2 = tree.inOrder(tree.root);
for (Node node : nodes2) {
System.out.println(node);
}
}
@Override
public void delete(Entry e) {
if (super.root == null) {
//空树
return ;
}
Node x = search(e);
if (e.getKey().compareTo(x.getEntry().getKey()) != 0) {
//目标节点目不存在
return ;
}
Node w = super.root;
//此时的根节点就是包含词条e的节点
if (!super.hasLChild(super.root)) {
//根节点没有左子树，直接删除
super.root = super.root.getRight();
if (super.root != null) {
super.root.setParent(null);
}
}else if (!super.hasRChild(super.root)) {
//根节点没有右子树，直接删除
super.root = super.root.getLeft();
if (super.root != null) {
super.root.setParent(null);
}
}else {
//根节点有左右子树
Node lTree = super.root.getLeft();
//split:摘除左子树，保留右子树
lTree.setParent(null);
super.root.setLeft(null);
super.root = super.root.getRight();
super.root.setParent(null);
//以原树根为节点再查找一次，将右子树中最小的节点伸展到树根
search(w.getEntry());
//join:接入左子树
super.root.setLeft(lTree);
lTree.setParent(super.root);
}
if (super.root != null) {
super.updateHeight(super.root);
}
//删除结束
}
@Override
public Node insert(Entry e) {
if (super.root == null) {
//空树
Node root = new Node();
root.setEntry(e);
super.root = root;
return root;
}
super.root = search(e);
if (root.getEntry().getKey().compareTo(e.getKey())==0) {
return super.root;
}
Node t = super.root;
if (super.root.getEntry().getKey().compareTo(e.getKey())<0) {
//t<e
Node root = new Node();
root.setEntry(e);
root.setLeft(t);
root.setRight(t.getRight());
super.root = root;
t.setParent(super.root);
if (super.hasRChild(t)) {
t.getRight().setParent(super.root);
t.setRight(null);
}
}else {
//t>e
Node root = new Node();
root.setEntry(e);
root.setLeft(t.getLeft());
root.setRight(t);
super.root = root;
t.setParent(super.root);
if (super.hasLChild(t)) {
t.getLeft().setParent(super.root);
t.setLeft(null);
}
}
updateHeightAbove(t);
return super.root;
}
@Override
public Node search(Entry e) {
Node p = super.search(e);
if (p == null) {
p = super.hot;
}
Node root = splay(p);
super.root = root;
return root;
}
private Node splay(Node v) {
if (v==null) {
return null;
}
Node p = null;
Node g = null;
while (((p=v.getParent())!=null)&&((g=(p.getParent()))!=null)) {
Node gg = g.getParent();
if (super.isLChild(v)) {
if (super.isLChild(p)) {
//left-left：g为轴点右旋->以p为轴右旋
attachAsLChild(g, p.getRight());
attachAsLChild(p, v.getRight());
attachAsRChild(p,g);
attachAsRChild(v,p);
}else {
//left-right：以p为轴右旋->以g为轴左旋
attachAsLChild(p,v.getRight());
attachAsRChild(g,v.getLeft());
attachAsLChild(v, g);
attachAsRChild(v,p);
}
}else {
if (super.isRChild(p)) {
//right-right：以g为轴点左旋->以p为轴左旋
attachAsRChild(g,p.getLeft());
attachAsRChild(p,v.getRight());
attachAsLChild(p,g);
attachAsLChild(v,p);
}else {
//right-left
attachAsRChild(p,v.getRight());
attachAsLChild(g,v.getRight());
attachAsRChild(v, g);
attachAsLChild(v,p);
}
}
if (gg == null) {
v.setParent(null);
}else {
if (g.getEntry().getKey().compareTo(gg.getLeft().getEntry().getKey()) == 0) {
attachAsLChild(gg, v);
}else {
attachAsRChild(gg, v);
}
}
//更新高度
super.updateHeight(g);
super.updateHeight(p);
super.updateHeight(v);
}
if (v.getParent() != null && p != null && p.getEntry().getKey().compareTo(v.getParent().getEntry().getKey()) == 0) {
//p是v的父亲
if (super.isLChild(v)) {
attachAsLChild(p, v.getRight());
attachAsRChild(v, p);
}else {
attachAsRChild(p,v.getLeft());
attachAsLChild(v,p);
}
updateHeight(p);
updateHeight(v);
}
v.setParent(null);
return v;
}
private void attachAsRChild(Node p, Node rc) {
p.setRight(rc);
if (rc != null) {
rc.setParent(p);
}
}
private void attachAsLChild(Node p, Node lc) {
p.setLeft(lc);
if (lc != null) {
lc.setParent(p);
}
}
}
双层伸展技巧示例
-
zig-zig/zag-zag情形
zig-zig/zag-zag.png -
zig-zag/zag-zig情形
zig-zag/zag-zig.png -
zig/zag情形
zig/zag.png
