Splay Tree

324012406

浏览: 24042 次
性别:
来自: 杭州

最近访客更多访客>>

lygjzy

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

算法与数据结构

Splay Tree 是二叉查找树的一种，它与平衡二叉树、红黑树不同的是，Splay Tree从不强制地保持自身的平衡，每当查找到某个节点n的时候，在返回节点n的同时，Splay Tree会将节点n旋转到树根的位置，这样就使得Splay Tree天生有着一种类似缓存的能力，因为每次被查找到的节点都会被搬到树根的位置，所以当80%的情况下我们需要查找的元素都是某个固定的节点，或者是一部分特定的节点时，那么在很多时候，查找的效率会是O(1)的效率！当然如果查找的节点是很均匀地分布在不同的地方时，Splay Tree的性能就会变得很差了，但Splay Tree的期望的时间复杂度还是O（nlogn）的。

这里先介绍一下左旋（zag）和右旋（zig）的操作

然后就是Splay Tree进行Splay操作的具体步骤，主要分两种情况：

先看图中的左边，查找到的x节点的父节点是y，x是y的左子树，y的父节点z是根节点，y也是z的左子树，要把x旋转到根节点的位置，就要进行zig(y)，然后再进行zig(x)操作

再看图中的右边，查找到的z节点的父节点是y，z是y的右子树，y的父节点x是根节点，y也是x的右子树，要把z旋转到根节点的位置，就要进行zag(y)，然后进行zag(x)操作

若是途中的情况，若需要把x移动到根节点，则需要先进行zig(x)，然后再进行zag(x)操作

还有一种y是z的左子树，x是y的右子树的情况，这时就需要先进行zag(x)，然后再进行zig(x)操作了

下面就给出我自己写的Java版的Splay Tree的一种实现（为了方便，自己定义了类似于Map的接口，仅供参考）：

Splay Tree Node

public class SplayTreeNode implements Serializable {
    private static final long serialVersionUID = 72651428543015658L;
    
    protected int key;
    protected Object value;
    protected SplayTreeNode father;
    protected SplayTreeNode leftChild;
    protected SplayTreeNode rightyChild;
    
    // get, set 方法
}

Splay Tree 的接口

public interface SplayTree {
    /**
     * 添加/更新node结点
     * @param node
     * @return
     */
    public void put(SplayTreeNode node);

    /**
     * 根据key获取对应的node结点，若该结点不存在，则返回null
     * @param key
     * @return
     */
    public SplayTreeNode get(int key);

    /**
     * 根据key删除对应的node结点，若该结点不存在，则什么都不做
     * @param key
     */
    public void remove(int key);
    
    /**
     * 返回SplayTree中结点的个数
     * @return
     */
    public int size();
    
    /**
     * 显示SplayTree的树形结构
     */
    public void showTree();

    /**
     * 显示SplayTree各个结点的详细信息
     */
    public void showDetail();

Splay Tree 的实现

public class DefaultSplayTree implements SplayTree, Serializable {
    private static final long serialVersionUID = 4967206515246041054L;
    
    protected int size;
    protected SplayTreeNode root;
    
    public DefaultSplayTree() {
        this.size = 0;
        this.root = null;
    }
    
    /* (non-Javadoc)
     * @see SplayTree#get(int)
     */
    @Override
    public SplayTreeNode get(int key) {       
        SplayTreeNode currentNode = this.root;
        while (true) {
            // 找不到对应的结点，返回null
            if (currentNode == null) {
                return null;
            }
            
            // 当前结点就是要找的结点
            if (key == currentNode.getKey()) {
                this.splay(currentNode);
                return currentNode;
            // key比当前结点的key要小
            } else if (key < currentNode.getKey()) {
                currentNode = currentNode.getLeftChild();
            // key比当前结点的key要大
            } else {
                currentNode = currentNode.getRightyChild();
            }
        }
    }

    /* (non-Javadoc)
     * @see SplayTree#put(SplayTreeNode)
     */
    @Override
    public void put(SplayTreeNode node) {
        if (node == null) {
            return;
        }
        
        // 当前的splay树为空
        if (this.root == null) {
            this.root = node;
            this.size ++;
            return;
        }
        
        // 当前结点
        SplayTreeNode currentNode = this.root;
        // 当前结点的父结点
        SplayTreeNode currentNodeFather = null;
        // 当前结点是否是父结点的左子树
        boolean isLeft = false;;
        while (true) {
            // 当前结点为null，则此位置为添加结点的插入位置
            if (currentNode == null) {
                node.setFather(currentNodeFather);
                if (isLeft) {
                    currentNodeFather.setLeftChild(node);
                } else {
                    currentNodeFather.setRightyChild(node);
                }
                this.size ++;
                this.splay(node);
                return;
            }      
            
            // 若当前结点的key比添加的结点的key要小，则在当前结点的左子树中查找
            if (node.getKey() < currentNode.getKey()) {
                currentNodeFather = currentNode;
                isLeft = true;
                currentNode = currentNode.getLeftChild();
                
            // 若当前结点的key比添加的结点的key要大，则在当前结点的右子树中查找
            } else if (node.getKey() > currentNode.getKey()) {
                currentNodeFather = currentNode;
                isLeft = false;
                currentNode = currentNode.getRightyChild();
            
            // 当前结点的key和要添加的结点的key相等，则更新该结点
            } else {
                currentNode.setValue(node.getValue());
                node = currentNode;
                this.splay(node);
                return;
            }
        } 
    }

    /* (non-Javadoc)
     * @see SplayTree#remove(int)
     */
    @Override
    public void remove(int key) {
        SplayTreeNode node = this.get(key);
        if (node != null) {
            this.join(node.getLeftChild(), node.getRightyChild());
            this.size --;
        }
    }
    
    /**
     * 对node结点进行右旋
     * @param node
     */
    protected void zig(SplayTreeNode node) {
        // 获取旋转结点的父结点
        SplayTreeNode father = node.getFather();
        
        // 将旋转结点的右子树设为父结点的左子树
        father.setLeftChild(node.getRightyChild());
        // 若旋转结点的右子树不为空，则将父结点设为右子树的父结点
        if (node.getRightyChild() != null) {
            node.getRightyChild().setFather(father);
        }     
        
        // 将父结点的父结点（爷爷结点）设为旋转结点的父结点
        node.setFather(father.getFather());
        // 若爷爷结点不为空
        if (father.getFather() != null) {
            // 若父结点为爷爷结点的左子树，则将旋转结点设为爷爷结点的左子树
            if (father == father.getFather().getLeftChild()) {
                father.getFather().setLeftChild(node);
                
            // 若父结点为爷爷结点的右子树，则将旋转结点设为爷爷结点的右子树
            } else {
                father.getFather().setRightyChild(node);
            }
        } 
        
        // 将父结点设为旋转结点的右子树
        node.setRightyChild(father);
        // 更新父结点的父结点为旋转结点
        father.setFather(node);
    }
    
    /**
     * 对node结点进行左旋
     * @param node
     */
    protected void zag(SplayTreeNode node) {
        // 获取旋转结点的父结点
        SplayTreeNode father = node.getFather();
        
        // 将旋转结点的左子树设为父结点的右子树
        father.setRightyChild(node.getLeftChild());
        // 若旋转结点的左子树不为空，则将父结点设为左子树的父结点
        if (node.getLeftChild() != null) {
            node.getLeftChild().setFather(father);
        }
        
        // 将父结点的父结点（爷爷结点）设为旋转结点的父结点
        node.setFather(father.getFather());
        // 若爷爷结点不为空
        if (father.getFather() != null) {
            // 若父结点为爷爷结点的左子树，则将旋转结点设为爷爷结点的左子树
            if (father == father.getFather().getLeftChild()) {
                father.getFather().setLeftChild(node);
            
            // 若父结点为爷爷结点的右子树，则将旋转结点设为爷爷结点的右子树
            } else {
                father.getFather().setRightyChild(node);
            }
        }
        
        // 将父结点设为旋转结点的左子树
        node.setLeftChild(father);
        // 更新父结点的父结点为旋转结点
        father.setFather(node);
    }
    
    /**
     * 对node结点进行伸展
     * @param node
     */
    protected void splay(SplayTreeNode node) {
        if (this.root == null) {
            return;
        }
        
        while (node.getFather() != null) {
            if (node.getFather() == this.root) {
                if (node == node.getFather().getLeftChild()) {
                    this.zig(node);
                } else {
                    this.zag(node);
                }
            } else if (node.getFather().getFather().getLeftChild() == node.getFather()) {
                if (node == node.getFather().getLeftChild()) {
                    this.zig(node.getFather());
                    this.zig(node);
                } else {
                    this.zag(node);
                    this.zig(node);
                }
            } else {
                if (node == node.getFather().getRightyChild()) {
                    this.zag(node.getFather());
                    this.zag(node);
                } else {
                    this.zig(node);
                    this.zag(node);
                }
            }
        }
        this.root = node;
    }
    
    /**
     * 合并treeA, treeB，更新root
     * @param treeA
     * @param treeB
     */
    protected void join(SplayTreeNode treeA, SplayTreeNode treeB) {
        if (treeA != null) {
            treeA.setFather(null);
        }
        if (treeB != null) {
            treeB.setFather(null);
        }
        
        if (treeA == null) {
            this.root = treeB;
            return;
        }
        if (treeB == null) {
            this.root = treeA;
            return;
        }
        
        SplayTreeNode node = treeA;
        while (node.getRightyChild() != null) {
            this.splay(node.getRightyChild());
            node = node.getRightyChild();
        }
        
        node.setRightyChild(treeB);
        treeB.setFather(node);
        this.root = node;
    }

    /* (non-Javadoc)
     * @see SplayTree#size()
     */
    @Override
    public int size() {
        return this.size;
    }
    
    /* (non-Javadoc)
     * @see SplayTree#showTree()
     */
    @Override
    public void showTree() {
        List<SplayTreeNode> nodeList = new ArrayList<SplayTreeNode>();
        nodeList.add(this.root);
        this.bfs(nodeList);     
    }
    
    /**
     * 广度优先遍历SplayTree的每个结点，若结点不为空则输出key值，若为空则输出*
     * @param nodeList
     */
    protected void bfs(List<SplayTreeNode> nodeList) {
        List<SplayTreeNode> newNodeList = new ArrayList<SplayTreeNode>();
        boolean found = false;
        for (SplayTreeNode node : nodeList) {
            if (node != null) {
                found = true;
                System.out.print(node.getKey() + " ");
                newNodeList.add(node.getLeftChild());
                newNodeList.add(node.getRightyChild());
            } else {
                System.out.print("* ");
                newNodeList.add(null);
                newNodeList.add(null);
            }
        }
        System.out.println("");
        
        if (found) {
            this.bfs(newNodeList);
        }
    }
    
    /* (non-Javadoc)
     * @see SplayTree#showDetail()
     */
    @Override
    public void showDetail() {
        this.inorderTraversal(this.root);   
    }
    
    /**
     * 中序遍历SplayTree的每个结点，并输出结点的详细信息
     * @param node
     */
    protected void inorderTraversal(SplayTreeNode node) {
        if (node != null) {
            System.out.println(node.toString());
            this.inorderTraversal(node.getLeftChild());
            this.inorderTraversal(node.getRightyChild());
        }
    }
}