伸展树&红黑树

浅浅的花香味﹌ 2022-06-18 05:29 123阅读 0赞

**伸展树&红黑树**

**一.伸展树特点**

**二.Java实现**

**三.与红黑树的比较**

**一.伸展树特点**

前面写了二叉查找树BSTree和一种平衡二叉树AVL树的java实现。再看伸展树(Splay Binary Search Tree)，写起来就比较顺了。

特点: 每次插入或者删除节点，都会旋转该节点(或其前驱/后继节点)，使之成为根节点。 这种树为达到的核心目的使最近访问的节点位于根节点及其附近。

**二.java实现**

理论可参考:[http://www.cnblogs.com/vamei/archive/2013/03/24/2976545.html][http_www.cnblogs.com_vamei_archive_2013_03_24_2976545.html],这是一种自下而上的实现方式。

下面只写到了增加和查询节点后的旋转，对于删除，后面补上。

package comUtils;
    
    public class SBSTree<T extends Comparable<T>>{
    	SBSNode<T> root;
    	
    	public class SBSNode<S extends T>{
    		T key;
    		SBSNode<T> left;
    		SBSNode<T> right;
    		public SBSNode(T key, SBSTree<T>.SBSNode<T> left,
    				SBSTree<T>.SBSNode<T> right) {
    			super();
    			this.key = key;
    			this.left = left;
    			this.right = right;
    		}
    	}
    	
    	/**@description
    	 * 判断SBS类型的节点是否为空
    	 */
    	public boolean isNull(SBSNode<T> sBSNode){
    		return null==sBSNode? true:false;
    	}
    	
    	/**@description
    	 * 判断SBS类型的节点是都不为空
    	 */
    	public boolean isNotNull(SBSNode<T> sBSNode){
    		return !isNull(sBSNode);
    	}
    	
    	/**@description
    	 * 显式的进行初始化
    	 */
    	public void init(){
    		root = null;
    	}
    	
    	/**@description
    	 * 判断树是否为空
    	 */
    	public boolean isEmpty(){
    		return isNull(root);
    	}
    	
    	/**@description
    	 * 左左旋转:插入或删除一个节点后，根节点的左子树的左子树还有非空子节点
    	 */
    	private SBSNode<T> LLRotate(SBSNode<T> bBSNode){
    		SBSNode<T> LNode = bBSNode.left;
    		bBSNode.left = LNode.right;
    		LNode.right = bBSNode;
    		return LNode;
    	}
    	
    	/**@description
    	 * 右右旋转:插入或删除一个节点后，根节点的右子树的右子树还有非空子节点
    	 */
    	private SBSNode<T> RRRotate(SBSNode<T> bBSNode){
    		SBSNode<T> LNode = bBSNode.right;
    		bBSNode.right = LNode.left;
    		LNode.left = bBSNode;
    		return LNode;
    	}
    	
    	/**@description 
         * 返回key所在的节点(中序查找所有节点) 
         */  
        public SBSNode<T> findAllNode(T key){
        	if(isNull(root)){
        		return null;
        	}else{
        		SBSNode<T> node = middleFindByKey(root,key);
        		if(isNotNull(node)){
        	       	root = rotateTree(root, node.key);
        	     }else{
        	     }
        	    return node;
        	}
        }  
        
        public SBSNode<T> middleFindByKey(SBSNode<T> treeNode,T key){  
        	SBSNode<T> sBSNode = null;  
            /*优先查找左自树*/  
            if(isNotNull(treeNode.left)){  
            	sBSNode = middleFindByKey(treeNode.left,key);  
                if(isNotNull(sBSNode)){  
                    return sBSNode;  
                }  
            }else{  
            }  
            /*查找中间节点*/  
            if(0 == treeNode.key.compareTo(key)){  
                return sBSNode = treeNode;  
            }else{  
            }  
            /*查找右子树*/  
            if(isNotNull(treeNode.right)){  
            	sBSNode = middleFindByKey(treeNode.right,key);  
                if(isNotNull(sBSNode)){  
                    return sBSNode;  
                }   
            }else{  
            }  
            return sBSNode;  
        }
    	
    	/**@description 
    	 * 添加节点
    	 */
    	public boolean addSBSNode(T key){
    		/*判断添加节点是否成功*/
    		boolean result = true;
    		SBSNode<T> sBSNode = new SBSNode<T>(key, null, null);
    		if(isNull(sBSNode)){
    			System.out.println("节点生成失败");
    			return !result;
    		}
    		if(isEmpty()){
    			root = sBSNode;
    		}else{
    			insert(root,sBSNode);
    			/*插入节点之后则key所在节点一定存在，然后旋转节点，且赋值给根节点*/
    			root = rotateTree(root,key);
    		}
    		return result;
    	}
    	
    	/**@description 
    	 * 添加节点
    	 */
    	private boolean insert(SBSNode<T> tree,SBSNode<T> sBSNode){
    		/*判断添加节点是否成功*/
    		boolean result = true;
    		if(sBSNode.key.compareTo(tree.key) < 0){
    			if(isNotNull(tree.left)){
    				result = insert(tree.left,sBSNode);
    			}else{
    				tree.left = sBSNode;
    			}
    		}else if(sBSNode.key.compareTo(tree.key) > 0){
    			if(isNotNull(tree.right)){
    				result = insert(tree.right,sBSNode);
    			}else{
    				tree.right = sBSNode;
    			}
    		}else{/*值相等什么也不做*/
    			result = false;
    		}
    		return result;
    	}
    	/**@description 
    	 * 旋转节点
    	 */
    	private SBSNode<T> rotateTree(SBSNode<T> tree,T key){
    		if(key.compareTo(tree.key) < 0){
    			if(isNotNull(tree.left)){ /*左边树不为空*/
    				if(key.compareTo(tree.left.key) < 0){
    					tree = LLRotate(tree);
    					tree = rotateTree(tree, key);
    				}else if(key.compareTo(tree.left.key) > 0){
    					tree.left = rotateTree(tree.left, key);
    					tree = LLRotate(tree);
    				}else{/*直接左旋转*/
    					tree = LLRotate(tree);
    				}
    			}else{/*左边树为空,说明没有该节点，这种情形不存在*/
    			}
    		}else if(key.compareTo(tree.key) > 0){
    			if(isNotNull(tree.right)){
    				if(key.compareTo(tree.right.key) > 0){
    					tree = RRRotate(tree);
    					tree = rotateTree(tree, key);
    				}else if(key.compareTo(tree.right.key) < 0){
    					tree.right = rotateTree(tree.right, key);
    					tree = RRRotate(tree);
    				}else{
    					/*直接右旋转*/
    					tree = RRRotate(tree);
    				}
    			}else{/*右边树为空,说明没有该节点，这种情形不存在*/
    			}
    		}else{/*这种情形只能是根节点*/
    			return tree;
    		}
    		return tree;
    	}
    	
    	 /**@description  
         * 前序遍历 
         */  
        public void beforeFind(SBSNode<T> treeNode){  
            if(isNotNull(treeNode)){  
            	System.out.print(treeNode.key+" ");  
                beforeFind(treeNode.left);  
                beforeFind(treeNode.right);  
            }else{  
            }  
        }  
        public void beforeFind(){  
            beforeFind(root);  
        }  
          
        /**@description  
         * 中序遍历 
         */  
        public void middleFind(SBSNode<T> treeNode){  
            if(isNotNull(treeNode)){  
                middleFind(treeNode.left);  
                System.out.print(treeNode.key+" ");  
                middleFind(treeNode.right);  
            }else{  
            }  
        }  
        public void middleFind(){  
            middleFind(root);  
        }  
          
        /**@description  
         * 后序遍历 
         */  
        public void afterFind(SBSNode<T> treeNode){  
            if(isNotNull(treeNode)){  
                afterFind(treeNode.left);  
                afterFind(treeNode.right);  
                System.out.print(treeNode.key+" ");  
            }else{  
            }  
        }  
        public void afterFind(){  
            afterFind(root);  
        } 
    
        public static void main(String[] args) {
    		SBSTree<Integer> bBSTree = new SBSTree<Integer>();
    		/*新增数据*/
    		bBSTree.addSBSNode(new Integer(40));
    		bBSTree.addSBSNode(new Integer(20));
    		bBSTree.addSBSNode(new Integer(60));
    		bBSTree.addSBSNode(new Integer(50));
    		bBSTree.addSBSNode(new Integer(70));
    		bBSTree.addSBSNode(new Integer(45));
    		bBSTree.addSBSNode(new Integer(7));
    		bBSTree.addSBSNode(new Integer(8));
    		bBSTree.findAllNode(45);
    		bBSTree.findAllNode(70);
    //		bBSTree.delBSNode(50);
    //		bBSTree.delBSNode(70);
    //		bBSTree.delBSNode(45);
    		
    		bBSTree.middleFind();
    		System.out.println();
    		bBSTree.beforeFind();
    		System.out.println();
    		bBSTree.afterFind();
    	}
    }

**三.与红黑树的比较**

伸展树一般情况下的时间复杂度为LOGN(实际上所有的树在一般的情况下的平均时间复杂度都是LOGN)，它的主要优点是访问经常访问的节点效率较高，不常访问的节点时间较长。因此业务场景是:90%的操作作用于10%的数据

红黑树特点是:

1)根节点黑色

2)每个节点或者是黑色,或者是红色的

3)每个叶子节点是黑色的

4)如果一个节点是红色的，则它的子节点必须是黑色的

5)从一个节点到其所有叶子节点的路径，包含相同数目的黑色节点

删除或者增加节点后，红黑树做多需要三次旋转就可以成为新的红色树。 它牺牲了高度平衡，所以在查改上稍逊AVL树，但是在增删上由于不需要达到高度平衡，因此在增删上稍优于AVL树。综合来说，红黑树是一个综合效率都很不错的树的实现。

如果与伸展树进行比较的话，优势就更明显了。除非是部分数据经常被访问，否则红黑树无疑是更高效的。

关于红黑树的Java实现，有空补上。

[http_www.cnblogs.com_vamei_archive_2013_03_24_2976545.html]: http://www.cnblogs.com/vamei/archive/2013/03/24/2976545.html