Skip to content

Latest commit

 

History

History
354 lines (274 loc) · 10.2 KB

从零开始学习数据结构_红黑树.md

File metadata and controls

354 lines (274 loc) · 10.2 KB

秋招的时候，有次现场面试，面试官就让我手撕红黑树，当时就手写了插入算法的代码，当然了，其中插入算法，包含其左旋、右旋算法的实现，今天就把完整代码分享出来，希望能帮到各位。

一、红黑树

  1. 每个结点不是红的就是黑的；
  2. 根结点为黑色；
  3. 红结点的孩子必为黑结点；
  4. (除了根结点)任一结点不管通过什么路径，到达叶子节点的黑结点数目一定相同；

总结概括：一头一脚黑，黑同红不连：根为黑，到脚(叶子节点)的黑结点相同，红结点不相连。

二、红黑树与AVL树

  • AVL树 --> 由高度限定平衡，是严格意义上的平衡，绝对平衡；
  • RBTree --> 由红黑颜色限定平衡，不是太严格限定树的平衡；

三、红黑树的插入

红黑树是二叉搜索树，按二叉搜索树的大小比较进行插入；只能插入红色结点(黑色的话不满足黑同)，红色若相连，通过旋转解决！！！

结构体控制头如下：

typedef struct Node{  //红黑树结点类型
    Color color;  //红或黑色
    Type data;    //存储的数据
    struct Node *leftChild, *rightChild, *parent; //为了方便操作，左右孩子和父结点指针
}Node;

typedef struct RBTree{ //红黑树类型
    Node *root;   //根结点
    Node *NIL;    //指向一个空结点，构造了root有父结点;
}RBTree;

我的想法是：用一个指向树类型的指针，申请一个树类型空间，在利用树类型空间里面的 root 构造一棵树。

模型示意图如下：

在产生的结点中，每个结点的左右开始都赋值为 NIL；指向空结点，使 root 的父为空，便于操作；只能开始插入时为红结点，最终插入完成，经过旋转可为黑色。

对于要旋转的话，有如下 2 大种情形：

3.1 错误的方式

直接将根结点与左右孩子交换颜色，但是就不满足根是黑色了;

3.2 正确旋转的两种方式

1、

先做一次右单旋转，在交换1结点和2结点颜色。

如下图：

2、

先做一次先左后右的双旋转，在交换1结点和4结点的颜色。

如下图：

先左后右的旋转在这里可以通过：先左旋在右旋实现；实际上只写左和右旋函数就够了。

以上的 2 个图在左边的，实际上在右边是为镜像，一个道理。

3.3 左旋代码实现

void leftRotate(RBTree *t, Node *p){
    Node *s = p->rightChild;
    p->rightChild = s->leftChild;
    if(s->leftChild != t->NIL){
        s->leftChild->parent = p;
    }
    s->parent = p->parent;
    if(p->parent == t->NIL){
        t->root = s;
    }else if(p == p->parent->leftChild){
        p->parent->leftChild = s;
    }else{ 
        p->parent->rightChild = s;
    }

    s->leftChild = p;
    p->parent = s;
}

3.4 右旋代码实现

void rightRotate(RBTree *t, Node *p){
    Node *s = p->leftChild;
    p->leftChild = s->rightChild;
    if(s->rightChild != t->NIL){
        s->rightChild->parent = p;
    }
    s->parent = p->parent;

    if(p->parent == t->NIL){
        t->root = s;
    }else if(p == p->parent->leftChild){
        p->parent->leftChild = s;
    }else{
        p->parent->rightChild = s;
    }

    s->rightChild = p;
    p->parent = s;
}

四、RBtree插入完整代码+测试代码+运行结果

4.1 插入代码

#ifndef _RBTREE_H_
#define _RBTREE_H_

#include<malloc.h>

typedef enum{RED, BLACK} Color;

typedef struct Node{
    Color color;
    Type data;
    struct Node *leftChild, *rightChild, *parent;
}Node;

typedef struct RBTree{
    Node *root;
    Node *NIL;
}RBTree;

Node *createNode();   //创建一个结点空间
void initRBTree(RBTree **t);  //初始化红黑树
void leftRotate(RBTree *t, Node *p);  //坐旋转函数
void rightRotate(RBTree *t, Node *p);  //右旋转函数
void insertFixup(RBTree *t, Node *x);   //插入的调整函数
bool insert(RBTree *t, Type x);    //插入函数
void showRBTree(RBTree rb);       //显示函数
void show(RBTree rb, Node *t);   //真正的显示函数

void show(RBTree rb, Node *t){
    if(t != rb.NIL){
        show(rb, t->leftChild);
        printf("%d : %d\n", t->data, t->color);
        show(rb, t->rightChild);
    }
}

void showRBTree(RBTree rb){
    show(rb, rb.root);
}

bool insert(RBTree *t, Type x){
    Node *s = t->root;
    Node *p = t->NIL;
    while(s != t->NIL){  //找插入位置
        p = s;
        if(p->data == x){
            return false;
        }else if(x < p->data){
            s = s->leftChild;
        }else{
            s = s->rightChild;
        }
    }

    Node *q = createNode();
    q->data = x;
    q->parent = p;

    if(p == t->NIL){
        t->root = q;
    }else if(x < p->data){
        p->leftChild = q;
    }else{
        p->rightChild = q;
    }

    q->leftChild = t->NIL; //都指向空结点
    q->rightChild = t->NIL;

    q->color = RED;  //插入结点颜色为红

    insertFixup(t, q);  //调用一个调整函数

    return true;
}

void insertFixup(RBTree *t, Node *x){
    Node *s;
    while(x->parent->color == RED){
        if(x->parent == x->parent->parent->leftChild){  //leftChild
            s = x->parent->parent->rightChild;
            if(s->color == RED){
                x->parent->color = BLACK;
                s->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
                continue;
            }else if(x == x->parent->rightChild){
                x = x->parent;
                leftRotate(t, x);
            }

            x->parent->color = BLACK; //交换颜色
            x->parent->parent->color = RED;
            rightRotate(t, x->parent->parent);
            
        }else{  //rightChild
          s = x->parent->parent->leftChild;
            if(s->color == RED){
                x->parent->color = BLACK;
                s->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
                continue;
            }else if(x == x->parent->leftChild){
                x = x->parent;
                rightRotate(t, x);
            }

            x->parent->color = BLACK;  //交换颜色
            x->parent->parent->color = RED;
            leftRotate(t, x->parent->parent);
        }
    }
    t->root->color = BLACK;
}


void rightRotate(RBTree *t, Node *p){
    Node *s = p->leftChild;
    p->leftChild = s->rightChild;
    if(s->rightChild != t->NIL){
        s->rightChild->parent = p;
    }
    s->parent = p->parent;

    if(p->parent == t->NIL){
        t->root = s;
    }else if(p == p->parent->leftChild){
        p->parent->leftChild = s;
    }else{
        p->parent->rightChild = s;
    }

    s->rightChild = p;
    p->parent = s;
}
void leftRotate(RBTree *t, Node *p){
    Node *s = p->rightChild;
    p->rightChild = s->leftChild;
    if(s->leftChild != t->NIL){
        s->leftChild->parent = p;
    }
    s->parent = p->parent;
    if(p->parent == t->NIL){
        t->root = s;
    }else if(p == p->parent->leftChild){
        p->parent->leftChild = s;
    }else{ 
        p->parent->rightChild = s;
    }

    s->leftChild = p;
    p->parent = s;
}
    
void initRBTree(RBTree **t){
    (*t) = (RBTree *)malloc(sizeof(RBTree));
    (*t)->NIL = createNode();
    (*t)->root = (*t)->NIL;
    (*t)->NIL->color = BLACK;
    (*t)->NIL->data = -1;
}
Node *createNode(){
    Node *p = (Node *)malloc(sizeof(Node));
    p->color = BLACK;
    p->data = 0;
    p->leftChild = p->rightChild = p->parent = NULL;

    return p;
}

#endif

4.2 测试代码

#include<stdio.h>

typedef int Type;

#include"RBTree.h"

int main(void){
    RBTree *rb;
    int ar[] = {10, 7, 4, 8, 15, 5, 6, 11, 13, 12,};
    //int ar[] = {10, 7, 5};
    int n = sizeof(ar)/sizeof(int);
    int i;

    initRBTree(&rb);
    for(i = 0; i < n; i++){
        insert(rb, ar[i]);
    }
    
    printf("0代表红，1代表黑\n");
    showRBTree(*rb);
    return 0;
}

4.3 运行结果

五、删除算法

红黑树的删除思路：在搜索二叉树中，永远记住删除结点，先化为只有左树或右树一个分支在解决；

所以，先找到结点，在转换为只有一个分支的，在删除(只能删除红色的结点)，可能通过旋转调整函数进行平衡！！！

六、说明

原创文章链接：从零开始学习数据结构-->红黑树