红黑树详解 查询 插入 编程实现

红黑树前言

红黑树(Red Black Tree)是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的。但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的:它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。
根节点的父节点指向nullptr，也可以指向哨兵节点
注意叶子结点的左右孩子指向哨兵节点 不是nullptr

红黑树性质

红黑树性质5点

性质1.每个节点是红色或黑色。
性质2.根节点是黑色。
性质3.每个叶节点(NIL)是黑色。哨兵节点
性质4每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)红色节点不允许连续
性质5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树插入过程规律

1.根节点一定是黑色，叶子结点，即哨兵节点时黑色
2.两个红色不能连接在一起，需要转化，看该问题节点父节点的父节点的左孩子，如果为红色，则进行颜色的转换，如果为黑色，就要进行旋转。

红黑树插入过程详解1

根节点默认是黑色的
插入到34时，就出问题了。

找问题节点双亲的双亲的左边，如果为黑色，开始旋转调整，左单旋 ，左旋中间的点由红变成黑 变成局部根节点 最左上的由黑变成红

找问题节点双亲的双亲的左边，如果为黑色，开始旋转调整，双旋 ，先以拐点为根节点 进行右单旋 不改变颜色 在进行左单旋 要改变颜色 …

红黑树插入过程详解2

在用程序测试一个例子
测试
16,3,7,11,9,26,18,14,15,45,34,50

当没有节点的时候，root和nil都指向一个哨兵节点

此时需要调整 先左旋

再右旋 注意改变颜色

此时需要调整 改变颜色就行

插入9

插入26

进行 颜色调整

插入34 左旋

如果插入18 先右旋再左旋

看代码

编程实现红黑树的插入

红黑树的定义和节点的定义

#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<stdio.h>
#include<stack>  //  using  namespace std;
#include<queue> 
#include <cassert>
typedef enum {RED=0,BLACK=1}ColorType;
typedef int ElemType;
typedef struct RBNode //
{
    //左右孩子 和父节点 颜色 数据
    struct RBNode* leftchild;
    struct RBNode* parent;
    struct RBNode* rightchild;
    ColorType color;
    ElemType data;
}RBNode, * PRBNode;

typedef struct
{
    RBNode* root;
    RBNode* Nil;
    int cursize;
}RBTree;

辅助函数实现

购买节点初始化红黑树

//购买一个节点
RBNode* Buynode(ElemType val, RBNode* Parg = nullptr,ColorType color=RED)
{
    RBNode* s = (RBNode*)malloc(sizeof(RBNode));
    if (nullptr == s) exit(EXIT_FAILURE);
    s->data = val;
    s->parent = Parg;
    s->color = color;
    return s;
}
void Freenode(RBNode* p)
{
    free(p);
}
//root和Nil都指向一个黑色的哨兵节点
void InitBSTree(RBTree* ptree)
{
    assert(nullptr != ptree);
    
    ptree->Nil = Buynode(0, nullptr,BLACK); //哨兵节点
    ptree->root = ptree->Nil;
    ptree->cursize = 0;
}

查询函数

// 查询值  注意ptr是指向哨兵节点
RBNode* FindValue(RBTree* ptree, ElemType val)
{
    assert(ptree != nullptr);
    RBNode* ptr = ptree->root;
    while (ptree->Nil != ptr && ptr->data != val)
    {
        ptr = val < ptr->data ? ptr->leftchild : ptr->rightchild;
    }
    return ptr;

}

辅助函数 找中序遍历的第一个节点 和最后节点 和指定节点的next prev

//中序非递归遍历
// Min;找当前节点为二叉树根节点的 最小的数
RBNode* First(RBTree* ptree, RBNode* ptr)
{
    while (ptree->Nil!= ptr && ptree->Nil != ptr->leftchild)
    {
        ptr = ptr->leftchild;
    }
    return ptr;
}
//找当前节点的后继 
RBNode* Next(RBTree* ptree, RBNode* ptr)
{
    //外部节点 和  双亲 就是nullptr
    if (ptree->Nil == ptr) return nullptr;
    if (ptr->rightchild != ptree->Nil)
    {
        return First(ptree,ptr->rightchild);
    }
    else
    {
        //向上跑
        RBNode* pa = ptr->parent;
        while (pa != nullptr && pa->leftchild != ptr)
        {
            ptr = pa;
            pa = ptr->parent;
        }
        return pa;
    }
}
// Max
RBNode* Last(RBTree*ptree,RBNode* ptr)
{
    while (ptr != ptree->Nil && ptr->rightchild != ptree->Nil)
    {
        ptr = ptr->rightchild;
    }
    return ptr;
}
RBNode* Prev(RBTree* ptree, RBNode* ptr)
{
    if (nullptr == ptr) return nullptr;
    if (ptr->leftchild != nullptr)
    {
        return Last(ptree,ptr->leftchild);
    }
    else
    {
        RBNode* pa = ptr->parent;
        while (pa != nullptr && pa->rightchild != ptr)
        {
            ptr = pa;
            pa = ptr->parent;
        }
        return pa;
    }
}

左单旋和右单旋函数实现

//左单旋 三步走 ptr是最上面的那个节点 newroot是ptr的下一个节点，即rightchild
//1. 定义一个新的root，root的父节点指向ptr的父节点
//2. ptr的右指向root的左，看root左是否为空，不为空，root的左的父节点指向ptr
//3. newroot的左指向ptr 考虑谁连接newroot
//要么是根，要么是ptr父节点的左或者右

RBNode* RotateLeft(RBTree* ptree, RBNode* ptr)
{
    assert(ptree != nullptr && ptr != nullptr);
    //第一步
    RBNode* newroot = ptr->rightchild;
    newroot->parent = ptr->parent;
    //第二步
    ptr->rightchild = newroot->leftchild;
    if (newroot->leftchild != ptree->Nil) {
        newroot->leftchild->parent = ptr;
    }
    //第三步
    newroot->leftchild = ptr;
    RBNode* pa = ptr->parent;
    if (pa==nullptr) {//ptr->parent=nullptr;
        ptree->root = newroot;
    }
    else {
        if (pa->leftchild == ptr) {
            pa->leftchild = newroot;
        }
        else {
            pa->rightchild = newroot;
        }
    }
    ptr->parent = newroot;
    return newroot;
}
//右单旋是左单旋的镜像
RBNode*RotateRight(RBTree* ptree, RBNode* ptr) {
    assert(ptree != nullptr && ptr != nullptr);
    RBNode* newroot = ptr->leftchild;
    newroot->parent = ptr->parent;

    ptr->leftchild = newroot->rightchild;
    if (newroot->rightchild != ptree->Nil) {
        newroot->rightchild->parent = ptr;
    }
    //如果是根节点
    newroot->rightchild = ptr;
    if (ptr->parent == nullptr) {
        ptree->root = newroot;
    }
    else {
        if (ptr->parent->leftchild == ptr) {
            ptr->parent->leftchild = newroot;
        }
        else {
            ptr->parent->rightchild = newroot;
        }
    }
    ptr->parent = newroot;
    return newroot;
}

红黑树的插入与调整构建

如果没有该节点就插入 插入的话，根据排序二叉树的定义先找到该插入的位置 然后核心就是调整 需要进行四种类型的旋转

void Insert(RBTree* ptree, RBNode* pa, ElemType val) {
    RBNode*s = Buynode(val, pa, RED);
    s->leftchild = ptree->Nil;
    s->rightchild = ptree->Nil;
    //插入根节点 刚开始没有数据
    if (pa == nullptr) {
        ptree->root = s;
    }
    //插入新节点
    else {
        if (pa->data > s->data) {
            pa->leftchild = s;
        }
        else {
            pa->rightchild = s;
        }
    }

    RBNode* ptr = s;
    //调整节点
    //需要向上回溯到根节点为止， ptr = ptr->parent->parent;
    // 因为两个连续红的调整完毕 问题节点父节点的父节点变成了红色 可能导致 又出现两个连续红色
    //说明回溯到根节点了，就全部平衡了
    //插入一个值后，如果高度不变就不用再回溯用tag标记
    //调整完成后，就不用再进行调整
    while (ptr != ptree->root && ptr->parent->color == RED) {
        //判断问题节点再父节点的父节点的右边
        if (ptr->parent->parent->rightchild == ptr->parent) {
            RBNode* left = ptr->parent->parent->leftchild;
            //问题节点的父节点的父节点 的左节点为红色 只用转移颜色 不用旋转
            if (left->color == RED) {
                //转移颜色
                left->color = BLACK;
                ptr->parent->color = BLACK;
                ptr->parent->parent->color = RED;
                // 因为两个连续红的调整完毕 问题节点父节点的父节点变成了红色 可能导致 又出现两个连续红色
                ptr = ptr->parent->parent;
            }
            //问题节点的父节点的父节点 的左节点为黑色 需要旋转 
            else {
                
                //条件满足就执行 不满足 不管 
                if (ptr->parent->leftchild == ptr) {
                    //这里形成了一个折线  双旋
                    //将问题节点的父节点传入 右单旋函数 
                    ptr = ptr->parent;
                    RotateRight(ptree, ptr);
                    //RotateRight(ptree, ptr->parent);//逻辑上是错误的e
                }
                //在此基础上调整颜色后进行左单旋 
                //如果 不是折线 右单旋不用执行 直接左单旋
                ptr->parent->color = BLACK;
                ptr->parent->parent->color = RED;
                RotateLeft(ptree, ptr->parent->parent);
            }


        }
        //判断问题节点再父节点的父节点的左边 
        else {
            RBNode* right = ptr->parent->parent->rightchild;
         
            if (right->color == RED) {
                right->color = BLACK;
                ptr->parent->color = BLACK;
                ptr->parent->parent->color = RED;
                ptr = ptr->parent->parent;
            }
            else {
                if (ptr->parent->rightchild == ptr) {
                    ptr = ptr->parent;
                    RotateLeft(ptree, ptr);
                }
                ptr->parent->color = BLACK;
                ptr->parent->parent->color = RED;
                RotateRight(ptree, ptr->parent->parent);
            }
           
        }
    }
    ptree->root->color = BLACK;
}
//不允许有重复值 
//注意特殊情况就是插入第一个节点 root
bool Insert_Item(RBTree* ptree, ElemType val)
{
    assert(ptree != nullptr);
    RBNode* p = ptree->root;
    RBNode* pa = nullptr;

    while (p != ptree->Nil && p->data != val)
    {
        pa = p;
        p = val < p->data ? p->leftchild : p->rightchild;
    }
    //说明有该节点 就不用插入了
    if (p != ptree->Nil) return false;
    Insert(ptree, pa, val);
    ptree->cursize += 1;
    return true;
}

测试函数

//根据中序遍历输出红黑树的结果 非递归遍历
void NiceInOrder(RBTree* ptree)
{
    assert(nullptr != ptree);
    for (RBNode* p = First(ptree, ptree->root);
        !(p == nullptr||p==ptree->Nil);
        p = Next(ptree,p))
    {
        printf("color:%s:key %d\n", ((p->color == RED) ? "红" : "黑"),p->data);
    }
    printf("\n");
}
int main()
{
    int ar[] = { 16,3,7,11,9,26,18,14,15,45,34,50 };
    int n = sizeof(ar) / sizeof(ar[0]);
    RBTree myt;
    InitBSTree(&myt);
  
    for (int i = 0; i < n; ++i)
    {
        Insert_Item(&myt, ar[i]);
    }
    NiceInOrder(&myt);
}

红黑树删除节点

持续更新…