致谢两位发明人

• 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