首页 > 其他分享 >1. 红黑树

1. 红黑树

时间:2022-10-09 13:46:20浏览次数:73  
标签:node right struct parent rbtree 红黑树 left

Linux C/C++服务器

红黑树(rbTree)

是一种特殊的平衡 二叉排序树,一般用于key,value查找,应用广泛;

定义

  1. 每个结点是红的或者黑的
  2. 根结点是黑的
  3. 每个叶子结点是黑的
  4. 如果一个结点是红的,则它的两个儿子都是黑的
  5. 对每个结点,从该结点到其子孙结点的所有路径上的包含相同数目的黑色结点
#define RED     0
#define BLACK   1

typedef int KEY_TYPE;

//这样写就把红黑树的性质单列出来了,_rbtree_node{if 0   else} 这一块方便写业务
#define RBTREE_ENTRY(name, type) \
    struct name {
        struct type *right;      \
        struct type *left;       \
        struct type *parent;     \
        unsigned char color;     \
    }

    
typedef struct _rbtree_node{   //这是红黑树中的一个节点node
    KEY_TYPE key;
    void *value;

#if 1
    struct _rbtree_node *right;
    struct _rbtree_node *left;
    struct _rbtree_node *parent;    //后续旋转操作时使用
    unsigned char color;
#else
    RBTREE_ENTRY(, rbtree_node) node;
#endif

} rbtree_node;

typedef struct _rbtree{          //这是一个红黑树的指针
    struct rbtree_node *root;
    struct rbtree_node *nil;   //叶子节点统一指向的节点    
} rbtree;

红黑树的旋转

红黑树性质被破环的时候,调整,左旋和右旋 不会修改结点的颜色

//左旋 左旋右旋不需要改变颜色
void rbtree_left_rotate(rbtree *T, rbtree_node *x){
    rbtree_node *y=x->right;

    //左旋总共有三对指针需要修改,第一对
    x->right = y->left;
    if(y->left != T->nil){
        y->left->parent = x;
    }

    //第二对
    y->parent = x->parent;
    if(x->parent == T->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;
}


//右旋,在左旋函数上 x改为y y改为x left改为right right改为left
void rbtree_left_rotate(rbtree *T, rbtree_node *y){
    rbtree_node *x = y->left;

    //左旋总共有三对指针需要修改,第一对
    y->left = x->right;
    if(x->right != T->nil){
        x->right->parent = y;
    }

    //第二对
    x->parent = y->parent;
    if(y->parent == T->nil){
        T->root = x;
    }else if(y == y->parent->right){
        y->parent->right = x;
    }else{
        y->parent->left = x;
    }

    //第三对
    x->left = y;
    y->parent = x;
}

红黑树的插入与变色

红黑树在插入一个结点之前,它已经是一颗红黑树插入结点为红色,在整个插入过程中插入节点的颜色不会改变,始终为红色,会改变parent节点的颜色

//调整插入后的红黑树,再插入过程中z的颜色始终为红色,会改变parent节点的颜色
void rbtree_insert_fixup(rbtree *T, rbtree_node *z){
    //z为RED,父节点不能为红色 
    while(z->parent->color == RED){
        if(z->parent == z->parent->parent->left){
            rbtree_node *y = z->parent->parent->right;
            if(y->color == RED){
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;

                z = z->parent->parent;    //回溯 一直到根节点
            } else { //y == BLACK
                if(z == z->parent->right){
                    z = z->parent;
                    rbtree_left_rotate(T, z);
                }

                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rbtree_right_rotate(T, z->parent->parent);
            }
        }
    }
}

//插入,插入z节点的颜色为红色,插入的过程中自始至终都为红色
void retree_insert(rbtree *T, rebtree_node *z){
    rbtree_node *y = T->nil;    //定义临时节点
    rbtree_node *x = T->root;
    
    while (x != T->nil){
        y = x;
        if(z->key < x->key){
            x=x->left;
        }else if(z->key > x->key){
            x=x->right;
        }else{
            //Exist 根据业务场景 做处理
            return;
        }
    }

    if(y == T->nil){
        T->root=z;
    }else{
        if(y->key > z->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }

    z->parent=y;
    z->left=T->nil;
    z->right=T->nil;
    z->color=RED;   //插入新节点颜色为红色
    
    rbtree_insert_fixup(T, z);
}

红黑树删除

和插入一样比较复杂

标签:node,right,struct,parent,rbtree,红黑树,left
From: https://www.cnblogs.com/go-ahead-wsg/p/16771841.html

相关文章

  • 状态机:给定规则下分类讨论——红黑树(+队列实验-银行模拟)
    状态机:分类讨论,为了递归与美观,把重复的去掉dueto二叉树不保证平衡,herecomesRed-Blacktree——每条路黑高相同,lmax<2lmin类似还有AVLT(1.44lgn,但维护代价大)红黑树......
  • 35+,如果面试让我手写红黑树!
    作者:小傅哥博客:https://bugstack.cn沉淀、分享、成长,让自己和他人都能有所收获!......
  • 树结构系列(二):平衡二叉树、AVL树、红黑树
    前面说到二叉树在极端情况下会退化成链表,那如何解决这个问题呢?答案是:树的平衡。我们通过树的平衡,使得左右子树的深度保持在较小范围内,从而保证二叉树的查询效率。这就是平......
  • [ 数据结构 - C++]红黑树RBTree
    在上篇文章我们了解了第一种平衡二叉搜索树AVL树,我们知道AVL树是通过平衡因子来控制左右子树高度差,从而将二叉树变成一颗平衡二叉搜索树。本篇文章我们将要了解另外一种平衡......
  • 红黑树
      packagetree.red.black;/***@author:tianhaichao*@date:2022/8/2914:27*@description:1、根节点为黑色*2、叶子节点为黑色空节点*3、红色......
  • 【数据结构】红黑树与平衡二叉树的区别以及原理详解(附图解)
    引用网址:https://blog.csdn.net/weixin_44780082/article/details/112239269文章目录前言一、什么是红黑树1.1平衡二叉树1.2红黑树1.3平衡二叉树和红黑树的区别二、红黑......
  • 判断红黑树
    https://www.acwing.com/problem/content/1630/思路:思路不难,按照题目意思判断即可,但是这个dfs有些难写,值得学习,特记录此题。#include<iostream>#include<algorithm>......
  • 红黑树:基于平衡搜索树的效率改进
    出现背景平衡二叉树解决了搜索二叉树可能过长导致查找次数过多的问题,但是随着不断的插入和删除,平衡二叉树算法需要不断的旋转以达到最佳结构,这个旋转操作浪费了不少时间,平......
  • 红黑树以及JAVA实现(一)
    目录前言一、B树1.1概念1.22-3-4树1.32-3-4树的插入节点分类1.42-3-4树的删除1.4.1当删除节点是叶子节点1.4.1.1当删除节点为非2节点1.4.1.2当删除节点为2节点1.4.......
  • 红黑树以及JAVA实现(二)
    目录红黑树的删除1.删除节点为叶子节点1.1删除节点为红色节点1.2删除节点为黑色1.2.1要删除的节点D是黑色,D的兄弟节点B也是黑色没有侄子节点1.2.2要删除的节点D是黑色......