首页 > 代码库 > 红黑树
红黑树
package datastructure.tree; /** * 红黑树是基于平衡二叉搜索树的一种扩展,它是给据红黑结点来判断是否旋转并进行相应的处理 * 这样就省去了平衡因子的判断,简化了算法的难度。根据红黑结点以调整树的平衡因子,这种 方 * 法可以近似平衡。红黑树具有以下性质: * 1.每个结点要么是黑色,要么是红色。(源于算法导论第三版) * 2.根结点是黑色的。 * 3.每个叶节点是黑色的(NIL) * 4.如果一个结点是红色的,则它的两个子结点都是黑色的。 * 5.对于每个结点,从该结点到其所有后代的叶结点的简单路径上,均包含相同数目的黑色结点。 * * 两种旋转: * 右旋: 给据中序遍历的规律,将旋转点移到右孩子上,左孩子提升为父节点。 * 左旋:同样是的规律,将旋转点旋转到左孩子,右孩子提升为父节点。 * 关于父节点下面的孩子,给据中序遍历的规律,可以判断各孩子的节点的位置变化。 * 注意:只会影响到孩子的孩子。不会超过三层,这样旋转就变得简单了。 * 应用: * 在JAVA中,TreeSet是TreeMap实现的,TreeMap就是红黑树实现的。 * 由于它具有快速删除,快速查找,其效率为O(logn),使用它比较适合需要排序 * 的对象。使用TreeSet作为 容器时,自定义的类型就需要实现Comparable * 接口,否则插入两个以上就会 抛出异常。里面有CompareTo方法,实现自己相应 * 的排序规则就行了。 *date structure *@author ZXLS *@date 2014年12月1日 *@version 1.7 */ public class RedBlackTree { static class Node{ Node left; Node right; Node parent; int key; int color; public Node(int key){ this.key=key; } @Override public String toString() { return "<"+key+","+(color==1?"Red":"BLACK")+">"; } } static class Tree{ public static Node nil=null; public static final int RED=1; public static final int BLACK=2; Node root; } /** * 插入树 * @param t * @param z */ public void RBInsert(Tree t,Node z){ Node y=Tree.nil; Node x=t.root; while(x!=Tree.nil){ y=x; if(z.key<x.key){ x=x.left; }else{ x=x.right; } } z.parent=y; if(y==Tree.nil){ t.root=z; } else if(z.key<y.key){ y.left=z; } else y.right=z; z.left=Tree.nil; z.left=Tree.nil; z.right=Tree.nil; z.color=Tree.RED; //将插入的点默认为红色的 RBInseFixUp(t,z); //对插入的点进行调整,保证红黑树的特性 } /** * 旋转调整,解决两个问题: * 1.什么时候进行调整? * 2.怎么旋转调整? * 主要情况: * 1.z的叔节点y为红色 * (解释为什么?:根据红黑树的性质,如果z的叔结点(y),y既然为红色,那么y的父节点必定为黑色,不可能为红色 * ,根据性质4即可得出,这样y为黑色,那么z的父亲(x),x必定为红色,而插入的节点默认是红色,这样就发生了冲突, * 给据上面的解释,我们可以发现红黑树的精髓所在!) * 2.z的叔节点y是黑色且z是一个右孩子 * 3.z的叔节点y是黑色且z是一个左孩子 * 分左,右情况。其中2,3也可以归为一类。 * 解决方案:(z.p:代表z节点的父节点) * 1.如果z.p存在且在左子树: * ①符合1:将z.p.p=red,z.p.p.right=black,z.p=black; * ②如果z.p.p在右子树:先左旋转,后右旋转。 * ③如果z.p.p在左子树:右旋转。 * 2.如果z.p存在且在右子树: * ①符合1:将z.p.p=red,z.p.p.right=black,z.p=black; * ②如果z.p.p在左子树:先右旋转,后左旋转。 * ③如果z.p.p在右子树:左旋转。 * 直到根节点或者某个z.p的颜色是黑色。(注意z是逐次往上移动,z=z.p.p)。 * 注意:空指针异常!!! * @param t 插入新节点后的红黑树 * @param z 要旋转的结点 */ private void RBInseFixUp(Tree t, Node z) { while(z!=null&&z.parent!=null&&z.parent.color==Tree.RED){ if(getParentOf(z)==leftOf(getParentOf(getParentOf(z)))){ //判断z.p是否在左子树 Node y=rightOf(getParentOf(getParentOf(z))); //如果在就取出z.p.p.right即z的叔节点。 if(getColorOf(y)==Tree.RED){ //叔节点为红色,执行方案1. setColorOf(getParentOf(z),Tree.BLACK); setColorOf(y,Tree.BLACK); z=getParentOf(getParentOf(z)); //执行完成后z就需要移到z.p.p, setColorOf(z,Tree.RED); } else { if(z==rightOf(getParentOf(z))){ //如果z在右子树 z=getParentOf(z); //将z移到z.p上 leftRotate(t, z); //执行左旋 } setColorOf(getParentOf(z),Tree.BLACK); //将z的父节点设置为黑色 setColorOf(getParentOf(getParentOf(z)),Tree.RED); //z的爷爷设为红色 rightRotate(t,getParentOf(getParentOf(z))); //以z的爷爷为旋转点,向右旋转 } } else{ //与上面的执行对称的操作 Node y=leftOf(getParentOf(getParentOf(z))); if(getColorOf(y)==Tree.RED){ setColorOf(getParentOf(z),Tree.BLACK); setColorOf(y,Tree.BLACK); z=getParentOf(getParentOf(z)); setColorOf(z,Tree.RED); } else{ if(z==leftOf(getParentOf(z))){ z=getParentOf(z); rightRotate(t,z); } setColorOf(getParentOf(z),Tree.BLACK); setColorOf(getParentOf(getParentOf(z)),Tree.RED); leftRotate(t,getParentOf(getParentOf(z))); } } } t.root.color=Tree.BLACK; } /** * 获取颜色,防止空指针异常 */ private int getColorOf(Node y) { return y==null?Tree.BLACK:y.color; } /** * 设置颜色,防止空指针异常 * @param y * @param c */ public void setColorOf(Node y,int c){ if(y!=null){ y.color=c; } } /** * 得到父节点,防止空指针异常 */ public Node getParentOf(Node x){ return x==null?null:x.parent; } /** * 得到左孩子,防止空指针异常 * @param x * @return */ public Node leftOf(Node x){ return x==null?null:x.left; } /** * 得到右孩子,防止空指针异常 * @param x * @return */ public Node rightOf(Node x){ return x==null?null:x.right; } /** * 左旋转 */ public void leftRotate(Tree t,Node x){ Node y=x.right; x.right=y.left; if(y.left!=Tree.nil){ y.left.parent=x; } y.parent=x.parent; if(x.parent==Tree.nil){ t.root=y; }else if(x==x.parent.left){ x.parent.left=y; }else{ x.parent.right=y; } y.left=x; x.parent=y; } /** * 右旋转 * @param t * @param x */ public void rightRotate(Tree t,Node x){ Node y=x.left; x.left=y.right; if(y.right!=Tree.nil){ y.right.parent=x; } y.parent=x.parent; if(x.parent==Tree.nil){ t.root=y; }else if(x==x.parent.left){ x.parent.left=y; }else{ x.parent.right=y; } y.right=x; x.parent=y; } public void inOrder(Node r){ if(r==null) return; inOrder(r.left); System.out.println(r); inOrder(r.right); } public void preOrder(Node r){ if(r==null) return; System.out.println(r); preOrder(r.left); preOrder(r.right); } public static void main(String[] args){ Tree tree=new Tree(); int[] arr={11,2,14,1,7,15,5,8,9}; //int[] arr={12,9,10}; RedBlackTree t=new RedBlackTree(); for(int i=0;i<arr.length;i++){ t.RBInsert(tree, new Node(arr[i])); } //中序遍历即可得到有序序列。 t.inOrder(tree.root); //System.out.println("***************"); //t.preOrder(tree.root); } }
红黑树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。