splay树 (树ADT连载 5/13)

单旋转: 与 AVL 树中介绍的单旋转相同，分为左单旋状和右单旋转。
之字形双旋转：与 AVL 树中介绍的之字形双旋转相同，实际上就是连续两次不同向的单旋转，分为左右双旋转和右左双旋转。
一字形双旋转：实际上就是连续两次同向的单旋转，分为左左双旋转和右右双旋转。

private BinaryNode<E> splay(E e, BinaryNode<E> t) { // 自顶向下展开目标结点
    BinaryNode<E> leftTreeMax, rightTreeMin;
    header.left = header.right = nullNode;
    leftTreeMax = rightTreeMin = header;
    nullNode.element = e;   // 确保能够匹配，便于编程
    while(true) {
        int compareRes = e.compareTo(t.element);
        if(compareRes < 0) { // 目标在t的左子树中
            if(e.compareTo(t.left.element) < 0) t = rotateRight(t); // 一字型右旋(右单旋)
            if(t.left == nullNode) break; // t无左儿子，已完成一次单旋(包括之字形)，跳出循环
            rightTreeMin.left = t; // 挂接到R下，同时保存R首次不为空时的根，且此后head.left不变
            rightTreeMin = t; // 更新rightTreeMin
            t = t.left; // 令t.left为中间树M的根结点
        }
        else if(compareRes > 0) { // 目标在t的右子树中
            if(e.compareTo(t.right.element) > 0) t = rotateLeft(t); // 一字型左旋(左单旋)
            if(t.right == nullNode) break; // t无右儿子，已完成一次单旋(包括之字形)，跳出循环
            leftTreeMax.right = t; // 挂接到L下，同时保存了L首次不为空时的根，且此后head.right不变
            leftTreeMax = t; // 更新leftTreeMax
            t = t.right; // 令t.right为中间树M的根结点
        }
        else break; // 相等即可退出
    } // 后续四句完成组装
    leftTreeMax.right = t.left;
    rightTreeMin.left = t.right;
    t.left = header.right; // header.right为L的根
    t.right = header.left; // header.left为R的根
    return t;
}

public void insert(E e) { // 插入结点
    if(newNode == null) newNode = new BinaryNode<>(e);
    if(root == nullNode) { // 当前为空树，将newNode作为root插入
        newNode.left = newNode.right = nullNode;
        root = newNode;
    }
    else { // 否则将目标结点旋转至根处，比较大小后插入
        root = splay(e, root);
        int compareRes = e.compareTo(root.element);
        if(compareRes < 0) { // e小于root的值，将newNode作为根插入
            newNode.left = root.left;
            newNode.right = root;
            root.left = nullNode;
            root = newNode;
        }
        else if(compareRes > 0) { // e大于root的值，将newNode作为根插入
            newNode.right = root.right;
            newNode.left = root;
            root.right = nullNode;
            root = newNode;
        }
        else return; // 相等时不插入
    }
    newNode = null; // 下一次插入时newNode == null
}

public E findMin() { // 查找最小结点驱动方法
    if(isEmpty()) throw new NoSuchElementException();
    return findMin(root).element;
}
private BinaryNode<E> findMin(BinaryNode<E> t) { // 返回树的最小结点
    while(t.left != nullNode) t = t.left;
    root = splay(t.element, root);
    return t;
}
public E findMax() { // 查找最大结点驱动方法
    if(isEmpty()) throw new NoSuchElementException();
    return findMax(root).element;
}
private BinaryNode<E> findMax(BinaryNode<E> t) { // 返回树的最大结点
    while(t.right != nullNode) t = t.right;
    root = splay(t.element, root);
    return t;
}

public void remove(E e) { // 删除结点
    if(!contains(e)) return; // 不存在直接返回，若存在，则该目标结点已被展开至根
    BinaryNode<E> newRoot;
    if(root.left == nullNode) newRoot = root.right; // 无左儿子，直接删除(懒惰删除)
    else { // 有左儿子
        newRoot = root.left;
        newRoot = splay(e, newRoot); // 将左子树中最大者旋转至根，令其为删除操作后的新根
        newRoot.right = root.right; // 将root.right接到newTree.right上
    }
    root = newRoot;
}

public boolean contains(E e) { // 判断树中是否有指定元素的结点
    if(isEmpty()) return false;
    root = splay(e, root);
    return root.element.compareTo(e) == 0;
}

class SplayTree<E extends Comparable<? super E>> {
    private BinaryNode<E> root, newNode;
    private final BinaryNode<E> nullNode;
    public SplayTree() {
        this.nullNode = new BinaryNode<>();
        this.root = this.nullNode.left = this.nullNode.right = this.nullNode;
    }
    public void insert(E e) { // 插入结点
        if(newNode == null) newNode = new BinaryNode<>(e);
        if(root == nullNode) { // 当前为空树，将newNode作为root插入
            newNode.left = newNode.right = nullNode;
            root = newNode;
        }
        else { // 否则将目标结点旋转至根处，比较大小后插入
            root = splay(e, root);
            int compareRes = e.compareTo(root.element);
            if(compareRes < 0) { // e小于root的值，将newNode作为根插入
                newNode.left = root.left;
                newNode.right = root;
                root.left = nullNode;
                root = newNode;
            }
            else if(compareRes > 0) { // e大于root的值，将newNode作为根插入
                newNode.right = root.right;
                newNode.left = root;
                root.right = nullNode;
                root = newNode;
            }
            else return; // 相等时不插入
        }
        newNode = null; // 下一次插入时newNode == null
    }
    public void remove(E e) { // 删除结点
        if(!contains(e)) return; // 不存在直接返回，若存在，则该目标结点已被展开至根
        BinaryNode<E> newRoot;
        if(root.left == nullNode) newRoot = root.right; // 无左结点，直接删除(懒惰删除)
        else { // 有左结点
            newRoot = root.left;
            newRoot = splay(e, newRoot); // 将左子树中最大者旋转至根，令其为删除操作后的新根
            newRoot.right = root.right; // 将root.right接到newTree.right上
        }
        root = newRoot;
    }
    public E findMin() { // 查找最小结点驱动方法
        if(isEmpty()) throw new NoSuchElementException();
        return findMin(root).element;
    }
    public E findMax() { // 查找最大结点驱动方法
        if(isEmpty()) throw new NoSuchElementException();
        return findMax(root).element;
    }
    public boolean contains(E e) { // 判断树中是否有指定元素的结点
        if(isEmpty()) return false;
        root = splay(e, root);
        return root.element.compareTo(e) == 0;
    }
    public void printTree(){ // 按中序遍历打印树的驱动方法
        if(isEmpty()) System.out.println("Empty tree");
        else printTree(root);
    }
    public int size() { // 求树的结点个数驱动方法
        return size(root);
    }
    public void makeEmpty() { // 树置空
        root = nullNode;
    }
    public boolean isEmpty() { // 树判空
        return root == nullNode;
    }
    private final BinaryNode<E> header = new BinaryNode<>(null);
    private BinaryNode<E> splay(E e, BinaryNode<E> t) { // 自顶向下展开目标结点
        BinaryNode<E> leftTreeMax, rightTreeMin;
        header.left = header.right = nullNode;
        leftTreeMax = rightTreeMin = header;
        nullNode.element = e;   // 确保能够匹配，便于编程
        while(true) {
            int compareRes = e.compareTo(t.element);
            if(compareRes < 0) { // 目标在t的左子树中
                if(e.compareTo(t.left.element) < 0) t = rotateRight(t); // 一字型右旋
                if(t.left == nullNode) break; // t无左儿子，已完成一次单旋(包括之字形)，跳出循环
                rightTreeMin.left = t; // 挂接到R下，同时保存R首次不为空时的根，且此后head.left不变
                rightTreeMin = t; // 更新rightTreeMin
                t = t.left; // 令t.left为中间树M的根结点
            }
            else if(compareRes > 0) { // 目标在t的右子树中
                if(e.compareTo(t.right.element) > 0) t = rotateLeft(t); // 一字型左旋
                if(t.right == nullNode) break; // t无右儿子，已完成一次单旋(包括之字形)，跳出循环
                leftTreeMax.right = t; // 挂接到L下，同时保存了L首次不为空时的根，且此后head.right不变
                leftTreeMax = t; // 更新leftTreeMax
                t = t.right; // 令t.right为中间树M的根结点
            }
            else break; // 相等即可退出
        } // 后续四句完成组装
        leftTreeMax.right = t.left;
        rightTreeMin.left = t.right;
        t.left = header.right; // header.right为L的根
        t.right = header.left; // header.left为R的根
        return t;
    }
    private BinaryNode<E> rotateRight(BinaryNode<E> k2){ // 右单旋
        BinaryNode<E> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        return k1; // 返回调整后原失衡处结点
    }
    private BinaryNode<E> rotateLeft(BinaryNode<E> k1){ // 左单旋
        BinaryNode<E> k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        return k2; // 返回调整后原失衡处结点
    }
    private BinaryNode<E> findMin(BinaryNode<E> t) { // 返回树的最小结点
        while(t.left != nullNode) t = t.left;
        root = splay(t.element, root);
        return t;
    }
    private BinaryNode<E> findMax(BinaryNode<E> t) { // 返回树的最大结点
        while(t.right != nullNode) t = t.right;
        root = splay(t.element, root);
        return t;
    }
    private void printTree(BinaryNode<E> t) { // 中序遍历打印树
        if(t != nullNode) {
            printTree(t.left);
            System.out.println(t.element);
            printTree(t.right);
        }
    }
    private int size(BinaryNode<E> t) { // 递归地遍历所有结点，返回结点总数
        if(t != nullNode) {
            if(t.left != nullNode && t.right != nullNode) {
                return 1 + size(t.left) + size(t.right);
            }
            else {
                return t.left != nullNode ? 1 + size(t.left) : 1 + size(t.right);
            }
        }
        return 0;
    }
    /**
     * 二叉树结点嵌套类
     */
    private static class BinaryNode<E>{
        public E element;
        public BinaryNode<E> left, right;
        @SuppressWarnings("unused")
        public BinaryNode(){
            this(null, null, null);
        }
        public BinaryNode(E element){
            this(element, null, null);
        }
        public BinaryNode(E element, BinaryNode<E> left, BinaryNode<E> right){
            this.element = element;
            this.left = left;
            this.right = right;
        }
    }
}

package com.yukiyama;

import java.util.NoSuchElementException;

public class SplayTreeDemo {

    public static void main(String[] args) {
        SplayTree<Integer> t = new SplayTree<>( );
        int[] elements = {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
        for(int e : elements) t.insert(e);
        t.printTree();
        System.out.printf("size: %d, min: %d, max: %d\n", t.size(), t.findMin(), t.findMax()); // 输出10
        System.out.printf("has 10? %s, has 100? %s\n", t.contains(10), t.contains(100));
        t.remove(1);
        t.remove(10);
        t.remove(16);
        t.printTree();
        System.out.printf("size: %d\n", t.size());// 输出0
        System.out.println("is empty: " + t.isEmpty()); // false
        t.makeEmpty();
        System.out.println("is empty: " + t.isEmpty()); // true
    }

}