红黑树深入剖析及Java实现

图片 11

红黑树是平衡二叉查找树的一种。为了深远精通红黑树,我们须要从二叉查找树起来提起。

BST

二叉查找树(Binary Search
Tree,简单的称呼BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的冲天决定了它的搜索效率。

在理想的景况下,二叉查找树增加和删除查改的时光复杂度为O(logNState of Qatar(个中N为节点数),最坏的事态下为O(N卡塔尔(قطر‎。当它的中度为logN+1时,我们就说二叉查找树是平衡的。

图片 1

二叉查找树

BST

二叉查找树(Binary Search
Tree,简单称谓BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的冲天决定了它的索求效用。

在突出的情形下,二叉查找树增加和删除查改的时刻复杂度为O(logN卡塔尔(قطر‎(此中N为节点数),最坏的情状下为O(N卡塔尔(قطر‎。当它的高度为logN+1时,大家就说二叉查找树是平衡的。

图片 2

BST存在的主题素材

BST存在的要害难点是,数在插入的时候会促成树倾斜,分裂的插入顺序会形成树的冲天不等同,而树的冲天直接的震慑了树的找出效能。理想的中度是logN,最坏的状态是颇负的节点都在一条斜线上,这样的树的惊人为N。

BST的检索操作

T  key = a search key
Node root = point to the root of a BST

while(true){
    if(root==null){
        break;
    }
    if(root.value.equals(key)){
        return root;
    }
    else if(key.compareTo(root.value)<0){
        root = root.left;
    }
    else{
        root = root.right;
    }
}
return null;

从程序中得以见见,当BST查找的时候,先与当前节点进行相比:

  • 借使相等的话就回来当前节点;
  • 假定个别当前节点则持续寻觅当前节点的左节点;
  • 假如过量当前节点则继续搜索当前节点的右节点。

直至当前节点指针为空可能找寻到相应的节点,程序查找截至。

RBTree

依赖BST存在的标题,一种新的树——平衡二叉查找树(Balanced
BST卡塔尔发生了。平衡树在插入和删除的时候,会通过旋转操作将中度保持在logN。在那之中七款具备代表性的平衡树分别为AVL树和红黑树。AVL树由于达成相比较复杂,况且插入和删除品质差,在骨子里条件下的使用不比红黑树。

BST的插入操作

Node node = create a new node with specify value
Node root = point the root node of a BST
Node parent = null;

//find the parent node to append the new node
while(true){
   if(root==null)break;
   parent = root;
   if(node.value.compareTo(root.value)<=0){
      root = root.left;  
   }else{
      root = root.right;
   } 
}
if(parent!=null){
   if(node.value.compareTo(parent.value)<=0){//append to left
      parent.left = node;
   }else{//append to right
      parent.right = node;
   }
}

插入操作先通过循环查找到待插入的节点的父节点,和探求父节点的逻辑相像,都是比尺寸,小的往左,大的往右。找到父节点后,比较父节点,小的就插入到父节点的左节点,大就插入到父节点的右节点上。

RBTree的定义

RBTree的定义如下:

  • 1.别样三个节点都有颜色,钴绿恐怕赤褐
  • 2.根节点是莲红的
  • 3.父亲和儿子节点之间不可能出现七个一而再的红节点
  • 4.任何二个节点向下遍历到其后裔的卡牌节点,所通过的黑节点个数必得相等
  • 5.空节点被感觉是米黄的

class  Node<T>{
   public  T value;
   public   Node<T> parent;
   public   boolean isRed;
   public   Node<T> left;
   public   Node<T> right;
}

作为平衡二叉查找树里面众多的兑现之一,红黑树无疑是最从简、达成最为轻便的。红黑树通过引进颜色的概念,通过颜色那个节制原则的使用来保持树的惊人平衡。作为平衡二叉查找树,旋转是一个不可缺乏的操作。通过旋转能够减少树的冲天,在红黑树里面还足以转移颜色。

红黑树里面包车型客车插入和删除的操作相比较难明白,这个时候要精心记住一点:操作从前红黑树是平衡的,颜色是相符定义的。在操作的时候就须求向兄弟节点、父节点、外孙子节点借调剂交流颜色,要完毕那几个目标,就供给持续的开展旋转。所以红黑树的插入删除操作须要不停的转动,一旦借调了其余节点,删除和插入的节点就能够实现局地的平衡(局地相符红黑树的定义),不过被借调的节点就不会抵消了,这时候就要求以被借调的节点为源点继续举办调节,直到整棵树都以平衡的。在全方位修复的进度中,插入具体的分成3种情状,删除分为4种情状。

全方位红黑树的搜寻,插入和删除都是O(logNState of Qatar的,原因正是整个红黑树的惊人是logN,查找从根到叶,走过的路径是树的可观,删除和插入操作是从叶到根的,所以通过的不二秘籍都以logN。

实际参照他事他说加以考查:
红黑树深深解析及Java完毕

BST的删除操作

去除操作的步骤如下:

  1. 搜寻到要刨除的节点。
  2. 即便待删除的节点是卡片节点,则直接删除。
  3. 假若待删除的节点不是卡牌节点,则先找到待删除节点的中序遍历的后继节点,用该后继节点的值替换待删除的节点的值,然后删除后继节点。

图片 3

BST存在的标题

BST存在的尤为重要难点是,数在插入的时候会招致树倾斜,差别的插入顺序会以致树的万丈区别等,而树的中度直接的影响了树的搜寻作用。理想的莫斯中国科学技术大学学是logN,最坏的气象是具备的节点都在一条斜线上,那样的树的可观为N。

RBTree

听闻BST存在的标题,一种新的树——平衡二叉查找树(Balanced
BST卡塔尔产生了。平衡树在插入和删除的时候,会透过旋转操作将高度保持在logN。此中四款具备代表性的平衡树分别为AVL树和红黑树。AVL树由于完结比较复杂,並且插入和删除品质差,在骨子里条件下的行使不及红黑树。

红黑树(Red-BlackTree,以下简单称谓RBTree)的莫过于行使特别广阔,比方Linux内核中的完全公平级调动度器、高精度电火花计时器、ext3文件系统等等,各类语言的函数库如Java的TreeMap和TreeSet,C++
STL的map、multimap、multiset等。

RBTree也是函数式语言中最常用的悠久数据构造之一,在测算几何中也会有至关心爱戴要功效。值得一说的是,Java
第88中学HashMap的落到实处也因为用RBTree代替链表,品质两全升高。

RBTree的定义

RBTree的概念如下:

  1. 别的三个节点都有颜色,紫灰或许稻草黄
  2. 根节点是灰黄的
  3. 父亲和儿子节点之间不可能冒出多个接二连三的红节点
  4. 别的二个节点向下遍历到其后代的叶子节点,所经过的黑节点个数必得相等
  5. 空节点被感到是巴黎绿的

数据构造表示如下:

class  Node<T>{
   public  T value;
   public   Node<T> parent;
   public   boolean isRed;
   public   Node<T> left;
   public   Node<T> right;
}

RBTree在理论上依旧一棵BST树,可是它在对BST的插入和删除操作时会维持树的平衡,即保障树的万丈在[logN,logN+1](理论上,极端的情事下得以现身RBTree的可观到达2*logN,但实在很难蒙受)。那样RBTree的查找时间复杂度始终维持在O(logN卡塔尔(قطر‎进而临近于好好的BST。RBTree的去除和插入操作的岁月复杂度也是O(logN卡塔尔(قطر‎。RBTree的寻找操作正是BST的搜寻操作。

RBTree的团团转操作

旋转操作(Rotate卡塔尔的目标是使节点颜色契合定义,让RBTree的莫斯科大学到达平衡。
Rotate分为left-rotate(左旋)和right-rotate(右旋),区分左旋和右旋的法子是:待旋转的节点从侧边上涨到父节点就是右旋,待旋转的节点从左边上涨到父节点正是左旋。

图片 4

RBTree的寻找操作

RBTree的追寻操作和BST的物色操作是同一的。请参见BST的查找操作代码。

RBTree的插入操作

RBTree的插入与BST的插入格局是如同一口的,只但是是在插入过后,或然会促成树的不平衡,当时就须要对树进行旋转操作和颜料修复(在此边简单称谓插入修复),使得它切合RBTree的概念。

新插入的节点是甲午革命的,插入修复操作假如凌驾父节点的颜色为黑则修复操作甘休。相当于说,唯有在父节点为金黄节点的时候是要求插入修复操作的。

布署修复操作分为以下的二种景况,并且新插入的节点的父节点都以新民主主义革命的:

  1. 老伯节点也为白色。
  2. 公公节点为空,且祖父节点、父节点和新节点处于一条斜线上。
  3. 父辈节点为空,且祖父节点、父节点和新节点不处在一条斜线上。

布署操作-case 1

case
1的操作是将父节点和伯父节点与伯公节点的颜料交流,这样就切合了RBTRee的定义。即维持了高度的平衡,修复后颜色也顺应RBTree定义的第三条和第四条。下图中,操作实现后A节点产生了新的节点。假诺A节点的父节点不是石黄的话,则持续做修复操作。

图片 5

插入操作-case 2

case
2的操作是将B节点实行右旋操作,并且和父节点A交流颜色。通过该修复操作RBTRee的万丈和颜色都亲密无间红黑树的定义。借使B和C节点都以右节点的话,只要将操作形成左旋就能够了。

图片 6

插入操作-case 3

case 3的操作是将C节点进行左旋,那样就从case 3转变来case
2了,然后针对case 2进行操作管理就行了。case
2操作做了一个右旋操作和颜色调换成达到指标。如水果树的布局是下图的镜像构造,则只须要将相应的左旋产生右旋,右旋产生左旋就能够。

图片 7

安插操作的下结论

插入后的修补操作是二个向root节点回溯的操作,一旦牵涉的节点都相符了红黑树的定义,修复操作结束。之所以会向上回溯是出于case
1操作会将父节点,二伯节点和伯公节点举办换颜色,有相当的大希望会导致祖父节点不平衡(红黑树定义3卡塔尔(قطر‎。此时必要对外祖父节点为起源进行调解(向上回溯)。

五伯节点调解后一旦依旧遭逢它的四伯颜色难题,操作就能够持续上扬回溯,直到root节点结束,依据定义root节点永恒是白灰的。在衍生和变化的追溯的进度中,针对插入的3中状态举行调整。直到适合红黑树的概念结束。直到牵涉的节点都合乎了红黑树的定义,修复操作停止。

一旦地点的3中状态要是对应的操作是在右子树上,做相应的镜像操作便是了。

RBTree的删除操作

去除操作首先供给做的也是BST的删减操作,删除操作会删除相应的节点,假若是卡片节点就径直删除,假使是非叶子节点,会用对应的中序遍历的后继节点来顶替要删减节点的职分。删除后就须求做去除修复操作,使的树相符红黑树的定义,切合定义的红黑树中度是平衡的。

除去修复操作在遭受被去除的节点是庚寅革命节点依然到达root节点时,修复操作甘休。

删除修复操作是针对删除浅青节点才有的,当海军蓝节点被剔除后会让全部树不符合RBTree的定义的第四条。须要做的管理是从兄弟节点上借调青灰的节点过来,如若兄弟节点未有黑节点能够借调的话,就只好往上追溯,将每拔尖的黑节点数减去一个,使得整棵树切合红黑树的概念。

去除操作的全体考虑是从兄弟节点借调樱草黄节点使树保持局地的平衡,固然有的的平衡达到了,就看完整的树是不是是平衡的,假使不平衡就随之向上追溯调治。

删去修复操作分为八种情景(删除黑节点后卡塔尔:

  1. 待删除的节点的小朋友节点是新民主主义革命的节点。
  2. 待删除的节点的弟兄节点是暗黑的节点,且兄弟节点的子节点都以水泥灰的。
  3. 待调解的节点的弟兄节点是黄色的节点,且兄弟节点的左子节点是革命的,右节点是奶油色的(兄弟节点在左边手卡塔尔(قطر‎,要是兄弟节点在左边包车型地铁话,正是兄弟节点的右子节点是新民主主义革命的,左节点是浅绛红的。
  4. 待调治的节点的兄弟节点是米色的节点,且右子节点是是巴黎绿的(兄弟节点在右边手卡塔尔(قطر‎,借使兄弟节点在左侧,则就是对应的就是左节点是革命的。

剔除操作-case 1

鉴于兄弟节点是乙丑革命节点的时候,不能借调黑节点,所以须要将兄弟节点升高到父节点,由于兄弟节点是革命的,遵照RBTree的概念,兄弟节点的子节点是浅青的,就足以从它的子节点借调了。

case 1那样调换之后就能够成为前边的case 2,case 3,可能case
4举办拍卖了。上升操作需求对C做二个左旋操作,借使是镜像布局的树只须要做相应的右旋操作就可以。

就此要做case
1操作是因为兄弟节点是乙亥革命的,不能借到多个黑节点来补偿删除的黑节点。

图片 8

删去操作-case 2

case
2的删除操作是由于兄弟节点能够去掉贰个米黄节点,因为兄弟节点和兄弟节点的子节点都以镉黄的,所以能够将兄弟节点变红,这样就足以保险树的一对的颜色相符定义了。那时要求将父节点A产生新的节点,继续提高调解,直到整颗树的颜料适合RBTree的概念截止。

case
2这种意况下之所以要将兄弟节点变红,是因为如若把兄弟节点借调过来,会促成兄弟的协会不合乎RBTree的定义,那样的境况下只好是将兄弟节点也成为栗褐来到达颜色的平衡。当将兄弟节点也变红之后,达到了一些的平衡了,可是对于四伯节点的话是不切合定义4的。那样就需求回溯到父节点,接着实行修补操作。

图片 9

删除操作-case 3

case
3的删除操作是贰在那之中等步骤,它的指标是将左臂的深红节点借调过来,那样就能够转变来case
4状态了,在case
4状态下得以将D,E节点都阶段过来,通过将多个节点产生橙褐来保管红黑树的完好平衡。

故而说case-3是叁此中间状态,是因为依据红黑树的概念来讲,下图而不是平衡的,他是通过case
2操作完后向上回溯现身的情事。之所以会并发case 3和前面包车型大巴case
4的事态,是因为能够因而借用外甥节点的新民主主义革命,形成黑灰来相符红黑树定义4.

图片 10

除去操作-case 4

Case
4的操作是真的的节点借调操作,通过将兄弟节点以致兄弟节点的右节点借调过来,并将兄弟节点的右子节点形成鹅黄来达到借调四个黑节点的目标,那样的话,整棵树依然符合RBTree的概念的。

Case
4这种景观的发出独有在待删除的节点的弟兄节点为黑,且子节点不全体为黑,才有望借调到几个节点来做黑节点使用,进而有限支撑整棵树都相符红黑树的概念。

图片 11

去除操作的计算

红黑树的去除操作是最复杂的操作,复杂的地点就在于当删除了深红节点的时候,怎么样从兄弟节点去借调治点,以保障树的颜色契合定义。由于暗紫的弟兄节点是不得已借调出黑节点的,那样只好通过筛选操作让她上涨到父节点,而鉴于它是红节点,所以它的子节点便是黑的,能够借调。

对于兄弟节点是中蓝节点的能够分为3种情状来管理,当所以的小伙子节点的子节点都是棕红节点时,能够一向将兄弟节点变红,那样一些的红黑树颜色是契合定义的。不过整颗树不自然是符合红黑树定义的,供给往上追溯继续调节。

对此兄弟节点的子节点为左红右黑抑或
(全体为红,右红左黑State of Qatar这几种情景,能够先将日前的情状通过增选改换为后一种情状,在后一种景况下,因为兄弟节点为黑,兄弟节点的右节点为红,能够借调出五个节点出来做黑节点,那样就足以确认保障删除了黑节点,整棵树照旧相符红黑树的定义的,因为淡紫节点的个数未有变动。

红黑树的去除操作是碰着删除的节点为深翠绿,或然追溯调解到了root节点,那时删除的修补操作结束。

RBTree的Java实现

public class RBTreeNode<T extends Comparable<T>> {
    private T value;//node value
    private RBTreeNode<T> left;//left child pointer
    private RBTreeNode<T> right;//right child pointer
    private RBTreeNode<T> parent;//parent pointer
    private boolean red;//color is red or not red

    public RBTreeNode(){}
    public RBTreeNode(T value){this.value=value;}
    public RBTreeNode(T value,boolean isRed){this.value=value;this.red = isRed;}

    public T getValue() {
        return value;
    }
    void setValue(T value) {
        this.value = value;
    }
    RBTreeNode<T> getLeft() {
        return left;
    }
    void setLeft(RBTreeNode<T> left) {
        this.left = left;
    }
    RBTreeNode<T> getRight() {
        return right;
    }
    void setRight(RBTreeNode<T> right) {
        this.right = right;
    }
    RBTreeNode<T> getParent() {
        return parent;
    }
    void setParent(RBTreeNode<T> parent) {
        this.parent = parent;
    }
    boolean isRed() {
        return red;
    }
    boolean isBlack(){
        return !red;
    }
    /**
    * is leaf node
    **/
    boolean isLeaf(){
        return left==null && right==null;
    }

    void setRed(boolean red) {
        this.red = red;
    }

    void makeRed(){
        red=true;
    }
    void makeBlack(){
        red=false;
    }
    @Override
    public String toString(){
        return value.toString();
    }
}

public class RBTree<T extends Comparable<T>> {
    private final RBTreeNode<T> root;
    //node number
    private java.util.concurrent.atomic.AtomicLong size = 
                    new java.util.concurrent.atomic.AtomicLong(0);

    //in overwrite mode,all node's value can not  has same    value
    //in non-overwrite mode,node can have same value, suggest don't use non-overwrite mode.
    private volatile boolean overrideMode=true;

    public RBTree(){
        this.root = new RBTreeNode<T>();
    }

    public RBTree(boolean overrideMode){
        this();
        this.overrideMode=overrideMode;
    }

    public boolean isOverrideMode() {
        return overrideMode;
    }

    public void setOverrideMode(boolean overrideMode) {
        this.overrideMode = overrideMode;
    }

    /**
     * number of tree number
     * @return
     */
    public long getSize() {
        return size.get();
    }
    /**
     * get the root node
     * @return
     */
    private RBTreeNode<T> getRoot(){
        return root.getLeft();
    }

    /**
     * add value to a new node,if this value exist in this tree,
     * if value exist,it will return the exist value.otherwise return null
     * if override mode is true,if value exist in the tree,
     * it will override the old value in the tree
     * 
     * @param value
     * @return
     */
    public T addNode(T value){
        RBTreeNode<T> t = new RBTreeNode<T>(value);
        return addNode(t);
    }
    /**
     * find the value by give value(include key,key used for search,
     * other field is not used,@see compare method).if this value not exist return null
     * @param value
     * @return
     */
    public T find(T value){
        RBTreeNode<T> dataRoot = getRoot();
        while(dataRoot!=null){
            int cmp = dataRoot.getValue().compareTo(value);
            if(cmp<0){
                dataRoot = dataRoot.getRight();
            }else if(cmp>0){
                dataRoot = dataRoot.getLeft();
            }else{
                return dataRoot.getValue();
            }
        }
        return null;
    }
    /**
     * remove the node by give value,if this value not exists in tree return null
     * @param value include search key
     * @return the value contain in the removed node
     */
    public T remove(T value){
        RBTreeNode<T> dataRoot = getRoot();
        RBTreeNode<T> parent = root;

        while(dataRoot!=null){
            int cmp = dataRoot.getValue().compareTo(value);
            if(cmp<0){
                parent = dataRoot;
                dataRoot = dataRoot.getRight();
            }else if(cmp>0){
                parent = dataRoot;
                dataRoot = dataRoot.getLeft();
            }else{
                if(dataRoot.getRight()!=null){
                    RBTreeNode<T> min = removeMin(dataRoot.getRight());
                    //x used for fix color balance
                    RBTreeNode<T> x = min.getRight()==null ? min.getParent() : min.getRight();
                    boolean isParent = min.getRight()==null;

                    min.setLeft(dataRoot.getLeft());
                    setParent(dataRoot.getLeft(),min);
                    if(parent.getLeft()==dataRoot){
                        parent.setLeft(min);
                    }else{
                        parent.setRight(min);
                    }
                    setParent(min,parent);

                    boolean curMinIsBlack = min.isBlack();
                    //inherit dataRoot's color
                    min.setRed(dataRoot.isRed());

                    if(min!=dataRoot.getRight()){
                        min.setRight(dataRoot.getRight());
                        setParent(dataRoot.getRight(),min);
                    }
                    //remove a black node,need fix color
                    if(curMinIsBlack){
                        if(min!=dataRoot.getRight()){
                            fixRemove(x,isParent);
                        }else if(min.getRight()!=null){
                            fixRemove(min.getRight(),false);
                        }else{
                            fixRemove(min,true);
                        }
                    }
                }else{
                    setParent(dataRoot.getLeft(),parent);
                    if(parent.getLeft()==dataRoot){
                        parent.setLeft(dataRoot.getLeft());
                    }else{
                        parent.setRight(dataRoot.getLeft());
                    }
                    //current node is black and tree is not empty
                    if(dataRoot.isBlack() && !(root.getLeft()==null)){
                        RBTreeNode<T> x = dataRoot.getLeft()==null 
                                            ? parent :dataRoot.getLeft();
                        boolean isParent = dataRoot.getLeft()==null;
                        fixRemove(x,isParent);
                    }
                }
                setParent(dataRoot,null);
                dataRoot.setLeft(null);
                dataRoot.setRight(null);
                if(getRoot()!=null){
                    getRoot().setRed(false);
                    getRoot().setParent(null);
                }
                size.decrementAndGet();
                return dataRoot.getValue();
            }
        }
        return null;
    }
    /**
     * fix remove action
     * @param node
     * @param isParent
     */
    private void fixRemove(RBTreeNode<T> node,boolean isParent){
        RBTreeNode<T> cur = isParent ? null : node;
        boolean isRed = isParent ? false : node.isRed();
        RBTreeNode<T> parent = isParent ? node : node.getParent();

        while(!isRed && !isRoot(cur)){
            RBTreeNode<T> sibling = getSibling(cur,parent);
            //sibling is not null,due to before remove tree color is balance

            //if cur is a left node
            boolean isLeft = parent.getRight()==sibling;
            if(sibling.isRed() && !isLeft){//case 1
                //cur in right
                parent.makeRed();
                sibling.makeBlack();
                rotateRight(parent);
            }else if(sibling.isRed() && isLeft){
                //cur in left
                parent.makeRed();
                sibling.makeBlack();
                rotateLeft(parent);
            }else if(isBlack(sibling.getLeft()) && isBlack(sibling.getRight())){//case 2
                sibling.makeRed();
                cur = parent;
                isRed = cur.isRed();
                parent=parent.getParent();
            }else if(isLeft && !isBlack(sibling.getLeft()) 
                                    && isBlack(sibling.getRight())){//case 3
                sibling.makeRed();
                sibling.getLeft().makeBlack();
                rotateRight(sibling);
            }else if(!isLeft && !isBlack(sibling.getRight()) 
                                            && isBlack(sibling.getLeft()) ){
                sibling.makeRed();
                sibling.getRight().makeBlack();
                rotateLeft(sibling);
            }else if(isLeft && !isBlack(sibling.getRight())){//case 4
                sibling.setRed(parent.isRed());
                parent.makeBlack();
                sibling.getRight().makeBlack();
                rotateLeft(parent);
                cur=getRoot();
            }else if(!isLeft && !isBlack(sibling.getLeft())){
                sibling.setRed(parent.isRed());
                parent.makeBlack();
                sibling.getLeft().makeBlack();
                rotateRight(parent);
                cur=getRoot();
            }
        }
        if(isRed){
            cur.makeBlack();
        }
        if(getRoot()!=null){
            getRoot().setRed(false);
            getRoot().setParent(null);
        }

    }
    //get sibling node
    private RBTreeNode<T> getSibling(RBTreeNode<T> node,RBTreeNode<T> parent){
        parent = node==null ? parent : node.getParent();
        if(node==null){
            return parent.getLeft()==null ? parent.getRight() : parent.getLeft();
        }
        if(node==parent.getLeft()){
            return parent.getRight();
        }else{
            return parent.getLeft();
        }
    }

    private boolean isBlack(RBTreeNode<T> node){
        return node==null || node.isBlack();
    }
    private boolean isRoot(RBTreeNode<T> node){
        return root.getLeft() == node && node.getParent()==null;
    }
    /**
     * find the successor node
     * @param node current node's right node
     * @return
     */
    private RBTreeNode<T> removeMin(RBTreeNode<T> node){
        //find the min node
        RBTreeNode<T> parent = node;
        while(node!=null && node.getLeft()!=null){
            parent = node;
            node = node.getLeft();
        }
        //remove min node
        if(parent==node){
            return node;
        }

        parent.setLeft(node.getRight());
        setParent(node.getRight(),parent);

        //don't remove right pointer,it is used for fixed color balance
        //node.setRight(null);
        return node;
    }

    private T addNode(RBTreeNode<T> node){
        node.setLeft(null);
        node.setRight(null);
        node.setRed(true);
        setParent(node,null);
        if(root.getLeft()==null){
            root.setLeft(node);
            //root node is black
            node.setRed(false);
            size.incrementAndGet();
        }else{
            RBTreeNode<T> x = findParentNode(node);
            int cmp = x.getValue().compareTo(node.getValue());

            if(this.overrideMode && cmp==0){
                T v = x.getValue();
                x.setValue(node.getValue());
                return v;
            }else if(cmp==0){
                //value exists,ignore this node
                return x.getValue();
            }

            setParent(node,x);

            if(cmp>0){
                x.setLeft(node);
            }else{
                x.setRight(node);
            }

            fixInsert(node);
            size.incrementAndGet();
        }
        return null;
    }

    /**
     * find the parent node to hold node x,if parent value equals x.value return parent.
     * @param x
     * @return
     */
    private RBTreeNode<T> findParentNode(RBTreeNode<T> x){
        RBTreeNode<T> dataRoot = getRoot();
        RBTreeNode<T> child = dataRoot;

        while(child!=null){
            int cmp = child.getValue().compareTo(x.getValue());
            if(cmp==0){
                return child;
            }
            if(cmp>0){
                dataRoot = child;
                child = child.getLeft();
            }else if(cmp<0){
                dataRoot = child;
                child = child.getRight();
            }
        }
        return dataRoot;
    }

    /**
     * red black tree insert fix.
     * @param x
     */
    private void fixInsert(RBTreeNode<T> x){
        RBTreeNode<T> parent = x.getParent();

        while(parent!=null && parent.isRed()){
            RBTreeNode<T> uncle = getUncle(x);
            if(uncle==null){//need to rotate
                RBTreeNode<T> ancestor = parent.getParent();
                //ancestor is not null due to before before add,tree color is balance
                if(parent == ancestor.getLeft()){
                    boolean isRight = x == parent.getRight();
                    if(isRight){
                        rotateLeft(parent);
                    }
                    rotateRight(ancestor);

                    if(isRight){
                        x.setRed(false);
                        parent=null;//end loop
                    }else{
                        parent.setRed(false);
                    }
                    ancestor.setRed(true);
                }else{
                    boolean isLeft = x == parent.getLeft();
                    if(isLeft){
                        rotateRight(parent);
                    }
                    rotateLeft(ancestor);

                    if(isLeft){
                        x.setRed(false);
                        parent=null;//end loop
                    }else{
                        parent.setRed(false);
                    }
                    ancestor.setRed(true);
                }
            }else{//uncle is red
                parent.setRed(false);
                uncle.setRed(false);
                parent.getParent().setRed(true);
                x=parent.getParent();
                parent = x.getParent();
            }
        }
        getRoot().makeBlack();
        getRoot().setParent(null);
    }
    /**
     * get uncle node
     * @param node
     * @return
     */
    private RBTreeNode<T> getUncle(RBTreeNode<T> node){
        RBTreeNode<T> parent = node.getParent();
        RBTreeNode<T> ancestor = parent.getParent();
        if(ancestor==null){
            return null;
        }
        if(parent == ancestor.getLeft()){
            return ancestor.getRight();
        }else{
            return ancestor.getLeft();
        }
    }

    private void rotateLeft(RBTreeNode<T> node){
        RBTreeNode<T> right = node.getRight();
        if(right==null){
            throw new java.lang.IllegalStateException("right node is null");
        }
        RBTreeNode<T> parent = node.getParent();
        node.setRight(right.getLeft());
        setParent(right.getLeft(),node);

        right.setLeft(node);
        setParent(node,right);

        if(parent==null){//node pointer to root
            //right  raise to root node
            root.setLeft(right);
            setParent(right,null);
        }else{
            if(parent.getLeft()==node){
                parent.setLeft(right);
            }else{
                parent.setRight(right);
            }
            //right.setParent(parent);
            setParent(right,parent);
        }
    }

    private void rotateRight(RBTreeNode<T> node){
        RBTreeNode<T> left = node.getLeft();
        if(left==null){
            throw new java.lang.IllegalStateException("left node is null");
        }
        RBTreeNode<T> parent = node.getParent();
        node.setLeft(left.getRight());
        setParent(left.getRight(),node);

        left.setRight(node);
        setParent(node,left);

        if(parent==null){
            root.setLeft(left);
            setParent(left,null);
        }else{
            if(parent.getLeft()==node){
                parent.setLeft(left);
            }else{
                parent.setRight(left);
            }
            setParent(left,parent);
        }
    }

    private void setParent(RBTreeNode<T> node,RBTreeNode<T> parent){
        if(node!=null){
            node.setParent(parent);
            if(parent==root){
                node.setParent(null);
            }
        }
    }
    /**
     * debug method,it used print the given node and its children nodes,
     * every layer output in one line
     * @param root
     */
    public void printTree(RBTreeNode<T> root){
        java.util.LinkedList<RBTreeNode<T>> queue =new java.util.LinkedList<RBTreeNode<T>>();
        java.util.LinkedList<RBTreeNode<T>> queue2 =new java.util.LinkedList<RBTreeNode<T>>();
        if(root==null){
            return ;
        }
        queue.add(root);
        boolean firstQueue = true;

        while(!queue.isEmpty() || !queue2.isEmpty()){
            java.util.LinkedList<RBTreeNode<T>> q = firstQueue ? queue : queue2;
            RBTreeNode<T> n = q.poll();

            if(n!=null){
                String pos = n.getParent()==null ? "" : ( n == n.getParent().getLeft() 
                                                                        ? " LE" : " RI");
                String pstr = n.getParent()==null ? "" : n.getParent().toString();
                String cstr = n.isRed()?"R":"B";
                cstr = n.getParent()==null ? cstr : cstr+" ";
                System.out.print(n+"("+(cstr)+pstr+(pos)+")"+"t");
                if(n.getLeft()!=null){
                    (firstQueue ? queue2 : queue).add(n.getLeft());
                }
                if(n.getRight()!=null){
                    (firstQueue ? queue2 : queue).add(n.getRight());
                }
            }else{
                System.out.println();
                firstQueue = !firstQueue;
            }
        }
    }

    public static void main(String[] args) {
        RBTree<String> bst = new RBTree<String>();
        bst.addNode("d");
        bst.addNode("d");
        bst.addNode("c");
        bst.addNode("c");
        bst.addNode("b");
        bst.addNode("f");

        bst.addNode("a");
        bst.addNode("e");

        bst.addNode("g");
        bst.addNode("h");

        bst.remove("c");

        bst.printTree(bst.getRoot());
    }
}

代码调节和测量检验的时候,printTree输出格式如下:

d(B)
b(B d LE) g(R d RI)
a(R b LE) e(B g LE) h(B g RI)
f(R e RI)

括号侧面表示成分的剧情。括号内的第一个成分表示颜色,B表示black,奥迪Q3表示red;第壹个因素表示父成分的值;第八个要素表示左右,LE表示在父成分的左边。TiggoI代表在父成分的右侧。

先是个成分d是root节点,由于它并未有父节点,所以括号内独有八个要素。

总结

用作平衡二叉查找树里面众多的得以达成之一,红黑树无疑是最从简、达成最为精简的。红黑树通过引进颜色的定义,通过颜色那么些节制标准的运用来维持树的莫斯中国科学技术大学学平衡。作为平衡二叉查找树,旋转是贰个少不了的操作。通过旋转能够减少树的可观,在红黑树里面还是能够转变颜色。

红黑树里面的插入和删除的操作比较难通晓,那时要小心记住一点:操作在此以前红黑树是平衡的,颜色是相符定义的。在操作的时候就供给向兄弟节点、父节点、孙子节点借调治将养调换颜色,要达到规定的标准那个目标,就须求不停的进展旋转。所以红黑树的插入删除操作需求不停的旋转,一旦借调了别的节点,删除和插入的节点就能落得局地的平衡(局地相符红黑树的概念),但是被借调的节点就不会抵消了,那时候就须要以被借调的节点为源点继续开展调治,直到整棵树都以平衡的。在全体修复的长河中,插入具体的分成3种情形,删除分为4种情状。

万事红黑树的搜索,插入和删除都以O(logN卡塔尔(قطر‎的,原因正是总体红黑树的惊人是logN,查找从根到叶,走过的路子是树的可观,删除和插入操作是从叶到根的,所以通过的门道都以logN。

参谋文献

  1. Cormen T H, Leiserson C E, Rivest 牧马人 L, 等. 算法导论(第3版).
    殷建平, 等. 机械工业出版社, 二零一一.
  2. Sedgewick Koleos, Wayne K. 算法(第4版). 谢路云 译.
    人民邮政和邮电通讯书局, 2011.
  3. Weiss M A. 数据构造与算法解析(第2版). 冯舜玺 译.
    机械工业书局, 2000.
  4. Knuth D E. Computer程序设计艺术 卷3:排序与搜索(Republika Hrvatska语版 第2版).
    人民邮政和邮电通讯书局, 2009.
You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图