红黑树（AVL树高级版）

鸣谢：
https://www.jianshu.com/p/0eaea4cc5619
https://blog.csdn.net/tanrui519521/article/details/80980135
https://zhuanlan.zhihu.com/p/24367771

删除：https://www.cnblogs.com/tongy0/p/5460623.html

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

性能优于AVL树，C++中的map，以及Java中的TreeMap，TreeSet， Java8中的HashMap的实现也采用了红黑树。

5条基本特征：

（1）每个结点要么是红的要么是黑的。
（2）根结点是黑的。
（3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
（4）如果一个结点是红的，那么它的两个儿子都是黑的。
（5）对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

  • 红黑树的5条特性确保了从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，使得整棵树大致上是平衡的
image.png

树的插入：（警惕红）

新插入的节点总是设为红色的，所以如果父节点为黑色，就不需要修复，因为没有任何性质被改变，所以只有在父节点为红色节点时需要做修复操作。

可以肯定调节的时候该点一定有grandparent，因为根节点为黑，连续两个红才需要调整。

情况1：cur为红，parent为红，pParent为黑，uncle存在且为红

则将parent，uncle改为黑，pParent改为红，然后把pParent当成cur，继续向上调整。

对策 :把父节点和叔叔节点变黑，爷爷节点涂红，然后把当前节点指针给到爷爷，让爷爷节点那层继续循环，接受红黑树特性检测。

simple case.png
z是当前点.png
情况2：cur为红，parent为红，pParent为黑，uncle不存在/u为黑

对策：当前节点的父节点作为新的当前节点，以新当前指点为支点左旋

parent为pParent的左孩子，cur为parent的左孩子，则进行右单旋转。

image.png
情况3：当前节点的父节点是红色，叔叔节点是黑色/不存在，且当前节点是其父节点的右儿子，祖父节点的左儿子是父节点

对策： 父节点变黑，祖父变红，以祖父节点为支点右旋

1为当前点，祖父节点为下一轮遍历的当前节点。

只变色不拐.png

4为当前点，取初始父节点3为下一轮遍历的当前节点。然后交换一下3和4，然后再重组

不变色只拐.png

3为当前点，取父亲为下一轮遍历的当前节点。

变色+拐.png
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
#define N 1000
#define red true
#define black false
class Node{
    public:
    static int length;
    bool br;
    // true red false black
    int num;
    Node*l,*r,*f;
    Node(){
        num=-1;
        r=f=l=NULL;
    } 
};
int Node::length=0;
void left_turn(Node*&root){
    Node*p=root->f;
    Node*pP=root->f->f;
    if(p->l){
        p->l->f=pP;
    }
    p->f=pP->f;
    pP->r=p->l;
    p->l=pP;
    if(pP->f==NULL){

    }
    else if(pP->f->num>pP->num){
        pP->f->l=p;
    }
    else{
        pP->f->r=p;
    }
    pP->f=p;
}
void right_turn(Node*&root){
    Node*p=root->f;
    Node*pP=root->f->f;
    if(p->r){
        p->r->f=pP;
    }
    p->f=pP->f;
    pP->l=p->r;
    p->r=pP;
    if(pP->f==NULL){

    }
    else if(pP->f->num>pP->num){
        pP->f->l=p;
    }
    else{
        pP->f->r=p;
    }
    pP->f=p;
}
void balance(Node*&root){
    // 如果是top点，没有father/grandfather需要单独讨论，因为可能是红点做top点
    if(root->f==NULL){
        root->br=black;
        return;
    }
    else if(root->br==black){
        return;
    }
    if(root->f->br==red){
        // Need to deal with this situation.
        // first decide you are in which side(l/r). there will be two choice and four cases.
        if(root->f->f->l&&root->f->f->r&&root->f->f->l->br==red&&root->f->f->r->br==red){
            // balance1 , p=red , uncle=red
            root->f->f->br=red;
            root->f->f->l->br=black;
            root->f->f->r->br=black;
            balance(root->f->f);
        }
        else{
            // balance2, p(left)=red , uncle=black/NULL
            if(root->f->f->r==NULL||root->f->f->r->br==black){
                // right turn
                Node*pP=root->f->f;
                Node*p=root->f;
                if(root->f->num>root->num){
                    p->br=black;
                    pP->br=red;
                    right_turn(root);
                    balance(root->f);
                }
                else{
                    root->br=black;
                    pP->br=red;                    
                    // adjust
                    if(root->l){
                        root->l->f=root->f;
                    }
                    p->r=root->l;
                    pP->l=root;
                    root->f=pP;
                    root->l=p;
                    p->f=root;
                    right_turn(root->l);
                    balance(root);
                }
            }
            // balance3 , p(right)=red , uncle(left)=black/NULL
            else{   // warm up
                Node*pP=root->f->f;
                Node*p=root->f;
                //left turn
                if(root->f->num>root->num){
                    root->br=black;
                    pP->br=red;                    
                    // adjust
                    pP->r=root;
                    p->f=root;
                    root->f=pP;
                    Node*t=root;
                    // 为了防止root被误置为NULL,出此下策保留该root指针
                    p->l=root->r; // bug p->l(指向root的左指针)=root->r 变成了 root=root->r
                    
                    root=t;
                    root->r=p;
                    left_turn(root->r);
                    balance(root);
                }
                else{
                    p->br=black;
                    pP->br=red;                    
                    left_turn(root);
                    balance(root->f);
                }
            }
        }
    }
    else{
        return;
    }
}
Node* leave=NULL;
Node* insert(Node*&root,int num){
    if(root==NULL){       
        Node *node=new Node();
        node->num=num;
        node->br=red;
        if(node->length==0){
            // root必须为black
            node->length=1;
            node->br=black;
        }
        root=node;
        leave=root;
        return node;
    }
    else if(root->num>num){
        root->l=insert(root->l,num);
        root->l->f=root;      
    }
    else{
        root->r=insert(root->r,num);
        root->r->f=root;      
    }
    return root;
}
// 打印看看结构
void print(Node*root){
    if(root==NULL){
        return;
    }
    cout<<root->num<<"  color: "<<(root->br==black?"black":"red")<<endl;
    print(root->l);
    print(root->r);
}
int main(){
  int i,j,input,k;
  int p,e;
  Node*root=NULL;
  freopen("inputs.txt","r+",stdin);
  cin>>p;
  for(i=0;i<p;i++){
      cin>>e;
      insert(root,e);
      balance(leave);
      root->length++; 
  }
  cout<<"preorder :\n";
  print(root);
}

/*
7
5 7 1 4 6 3 2

5  color: black
3  color: red
1  color: black
2  color: red
4  color: black
7  color: black
6  color: red

6 7 0 4 5 2 1

6  color: black
4  color: red
1  color: black
0  color: red
2  color: red
5  color: black
7  color: black

*/

树的删除：（警惕黑）

在红黑树中，删除一个节点往大的说，只有以下四种情况。

情况一：删除的节点的左、右子树都非空；

情况二：删除的节点的左子树为空树，右子树非空；

情况三：删除的节点的右子树为空树，左子树非空；

情况四：删除的节点的左、右子树都为空树；

其中情况一，可以按与其他二叉搜索树的删除方式一样处理，最终可以转换到后面的三种情况。具体为：找到(Old)D节点的直接后继节点(暂且称为X节点)，然后将X的值转移到D节点，最后将X节点作为真正要被删除掉的节点(即：(Real)D节点)。这样删除操作后，可以保证该树仍然为一棵二叉搜索树。但这样删除(Real)D节点后，可能会破坏红黑树的性质。所以需要额外做一些调整处理，这便是下面将要详细讨论的内容。

说明：下文中所提到的D，除非有特别说明，否则都将指的是(Real)D（一般可以认为该RealD节点的左子树为空，OldD不一定），最终要删除的节点一般是OldD的右节点或者右节点的最前面的一个左节点，当然也可能无右节点只能删自己。

image.png

删除的类别可以分为几种：

（1）首先 ，从当前点D和DR之间的颜色顺序看。

< 1 > 红->黑/NULL ，P肯定为黑 ， 直接删掉红，用黑（NULL）替换。

image.png

< 2 > 黑->红 ，直接拿红替换黑，然后红变黑。

image.png

< 3 > 黑->黑 / NULL ， 情况变得复杂。

（2）然后 ，根据uncle的颜色再分一次情况讨论：

< 1 > 如果uncle是红，那就很容易了。因为P不可能是红只能是黑，只有一种情况。

image.png
image.png

< 2 > uncle为黑时，特别复杂。

    1. SL=红，uncle=黑，P=黑/红，SR=黑/红

将S右旋转时，接着将SL改为P的颜色，P的颜色改为黑色(用这个黑色来填补DR分支的黑节点数)，将P左旋转。

image.png
    1. SR=红，P=黑/红，SL=黑/红
image.png
    1. S=黑，P=红，SL=SR=黑（处理简单，只要变色）
image.png
    1. SR=SL=黑，P=黑（处理简单，只要变色）
image.png
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • 30张图带你彻底理解红黑树
    写在前面 当在10亿数据进行不到30次比较就能查找到目标时，不禁感叹编程之魅力！人类之伟大呀！ —— 学红黑树有感...
    安卓大叔阅读 662,455评论 262赞 1,258
  • 30张图带你彻底理解红黑树（转）
    30张图带你彻底理解红黑树 写在前面 当在10亿数据中只需要进行10几次比较就能查找到目标时，不禁感叹编程之魅力！...
    雄关漫道从头越阅读 8,307评论 1赞 75
  • 红黑树详解
    1、红黑树介绍 红黑树又称R-B Tree，全称是Red-Black Tree，它是一种特殊的二叉查找树，红黑树的...
    文哥的学习日记阅读 13,364评论 1赞 35
  • 红黑树专题
    0.目录 1.算法导论的红黑树本质上是2-3-4树 2.红黑树的结构和性质 3.红黑树的插入 4.红黑树的删除 5...
    王侦阅读 7,481评论 1赞 2
  • 没有手机的日子
    一部小小的手机，竟然能影响一个人的情绪与生活。 一不小心，手机滑落在水里，慌忙中捡起来。火急火燎的将其吹干，可还是...
    独孤若曦阅读 4,733评论 26赞 19

友情链接更多精彩内容