AI 助理
备案控制台
开发者社区 人工智能 文章 正文

随处可见的红黑树

2024-01-09 43
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 随处可见的红黑树

红黑树

一、背景

我们知道二叉搜索树（BST），在极端情况下，会退化为单支树，查找效率从 O(log2n) 退化为 O(n)。主要原因就是BST不够平衡(左右子树高度差太大)。既然如此，那么我们就需要通过一定的算法，将不平衡树改变成平衡树。因此，AVL树就诞生了。AVL要求左右子树的高度差不能超过1，是严格平衡的二叉搜索树，为了维持这种严格平衡，每次插入和删除的时候都需要旋转操作。在频繁插入、删除的场景下，AVL的性能会大打折扣。红黑树通过牺牲严格的平衡性质，换取减少每次插入和删除的旋转操作。

二、概述

红黑树是一种自平衡的二叉搜索树。不论哪种搜索树，通过中序遍历，结果就是有序的。

红黑树五大性质：

  • 每个节点是红色或者黑色
  • 根节点是黑色的
  • 叶子节点是黑的
  • 如果一个节点是红的，那么该节点的两个儿子都是黑的
  • 每个节点，到叶子所有路径上的黑色节点个数相同。

三、红黑树代码实现

旋转：红黑树在插入或删除节点时，上面的性质可能会被破坏， 旋转操作就是为了使变化后的红黑树继续满足上面的性质。旋转操作分为左旋和右旋，旋转的本质，实际上是修改若干指针的指向。

左旋代码实现：

void rbtree_left_rotate(rbtree *T, rbtree_node *x) {
  rbtree_node *y = x->right;  // 获取x的右子树，保存到y
  x->right = y->left; // x的右子树指向y的左子树；
  //如果y的左子树不是叶子结点，需要改变y的左子树的父节点到x
  if (y->left != T->nil) { 
    y->left->parent = x;
  }
  y->parent = x->parent; // y的父节点指向x的父节点；
  // 此时需要判断x，x如果是根节点，则x的父节点为NULL，则需要让根节点指向此时的y；
  // 如果不是，则需要判断x是它父节点的左子树还是右子树,
  // 如果是左子树，就让父节点的左子树指向y，如果是右子树就让父节点的左=右子树指向y。
  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; // y的左子树指向x
  x->parent = y; // x的父节点指向y
}

右旋代码实现：只需要将左旋代码中的 x和y互换位置，left换成right，right换成left。

void rbtree_right_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->right = y;
  y->parent = x;
}

插入：每次插入都会插入到红黑树的最底层。并且上色为红色，因为红色不会影响第五条性质。插入完再继续进行调整（这里主要看自己与父节点是否为红色，如果是红色，迭代向上进行调整，如果是黑色就不用调整）。循环的中止条件就是遍历到叶子结点。如果插入的节点已经存在，也就是相等。取决于业务场景。比如定时任务，定时时间相同，可以稍稍修改一丢丢值。

始终需要扣住的点：红黑树不论是在什么时候，都是一棵红黑树，也就是说满足红黑树的性质。听起来像是废话，需要慢慢体会！

3.1 插入节点实现

红黑树插入节点z代码实现（看代码的时候结合着图看，会比较好理解一点）：

思考：假设插入节点z为红色，其父节点也为红色，那么z的祖父节点一定是黑色的！（红黑树性质决定），z的叔父节点的颜色就不确定了，需要分情况讨论：

  1. 要插入节点的父节点是祖父节点的左子树
    a) 叔父节点是红色的情况：

    b) 叔父节点是黑色的情况：
    这种情况下，需要考虑要插入的节点是其父节点的左孩子还是右孩子。
    b.1) 要插入的节点是其父节点的右孩子

    b.2) 要插入的节点是其父节点的左孩子
  2. 要插入节点的父节点是祖父节点的右子树（对照左子树情况理解就好）
void rbtree_insert_fixup(rbtree *T, rbtree_node *z) 
{
   while (z->parent->color == RED) // 只要当前z与其父节点的颜色都是红的就进行调整
   { 
    if (z->parent == z->parent->parent->left)  // 要插入节点的父节点是祖父节点的左子树
    {  
      rbtree_node *y = z->parent->parent->right;  // 拿到祖父节点的右节点，也就是叔父节点
      if (y->color == RED)  // 叔父节点的颜色是红色
      { 
        z->parent->color = BLACK;  // 将插入节点z的父节点染成黑色
        y->color = BLACK;          // 将插入节点z的叔父节点染成黑色
        z->parent->parent->color = RED;   // 将插入节点z的祖父节点染成红色
        z = z->parent->parent;     // 更新z节点为它的祖父节点，再次进行判断
      } 
      else // 叔父节点的颜色是黑色
      {       
        if (z == z->parent->right)  // 当前插入节点z是其父节点的右孩子
        {
          z = z->parent;
          rbtree_left_rotate(T, z);  
        }
        z->parent->color = BLACK;
        z->parent->parent->color = RED;
        rbtree_right_rotate(T, z->parent->parent);
      }
    }
    else  // 要插入节点的父节点是祖父节点的右子树
    {
      rbtree_node *y = z->parent->parent->left; // 拿到叔父节点
      if (y->color == RED) 
      {
        z->parent->color = BLACK;
        y->color = BLACK;
        z->parent->parent->color = RED;
        z = z->parent->parent; //z --> RED
      }
       else 
       {
        if (z == z->parent->left) 
        {
          z = z->parent;
          rbtree_right_rotate(T, z);
        }
        z->parent->color = BLACK;
        z->parent->parent->color = RED;
        rbtree_left_rotate(T, z->parent->parent);
      }
    }
  }
  T->root->color = BLACK;
}
void rbtree_insert(rbtree *T, rbtree_node *z) {
  rbtree_node *y = T->nil;  
  rbtree_node *x = T->root;  // 从根节点开始遍历
  while (x != T->nil)  // 遍历找插入位置，循环到叶子节点终止
  { 
    y = x;   // 保存x的上一级节点
    if (z->key < x->key) {
      x = x->left;
    } else if (z->key > x->key) {
      x = x->right;
    } else { //Exist
      return ;
    }
  }
  // 循环退出，找到插入位置，让待插入节点的父指针指向y（注意通过上述循环，x就是待插入的位置）
  z->parent = y;
  if (y == T->nil) {  // 当前红黑树为空
    T->root = z;
  } else if (z->key < y->key) {   // 当前红黑树不为空，需要判断是到y的左孩子还是右孩子
    y->left = z;
  } else {
    y->right = z;
  }
  // 因为每次插入，一定是插入到最后一行，所以需要让z节点的左右孩子都指向空
  z->left = T->nil;
  z->right = T->nil;
  z->color = RED; // 染成红色
  rbtree_insert_fixup(T, z);  // 迭代调整
}

3.2 删除及查找节点实现

void rbtree_delete_fixup(rbtree *T, rbtree_node *x) {
  while ((x != T->root) && (x->color == BLACK)) {
    if (x == x->parent->left) {
      rbtree_node *w= x->parent->right;
      if (w->color == RED) {
        w->color = BLACK;
        x->parent->color = RED;
        rbtree_left_rotate(T, x->parent);
        w = x->parent->right;
      }
      if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
        w->color = RED;
        x = x->parent;
      } else {
        if (w->right->color == BLACK) {
          w->left->color = BLACK;
          w->color = RED;
          rbtree_right_rotate(T, w);
          w = x->parent->right;
        }
        w->color = x->parent->color;
        x->parent->color = BLACK;
        w->right->color = BLACK;
        rbtree_left_rotate(T, x->parent);
        x = T->root;
      }
    } else {
      rbtree_node *w = x->parent->left;
      if (w->color == RED) {
        w->color = BLACK;
        x->parent->color = RED;
        rbtree_right_rotate(T, x->parent);
        w = x->parent->left;
      }
      if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
        w->color = RED;
        x = x->parent;
      } else {
        if (w->left->color == BLACK) {
          w->right->color = BLACK;
          w->color = RED;
          rbtree_left_rotate(T, w);
          w = x->parent->left;
        }
        w->color = x->parent->color;
        x->parent->color = BLACK;
        w->left->color = BLACK;
        rbtree_right_rotate(T, x->parent);
        x = T->root;
      }
    }
  }
  x->color = BLACK;
}
rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) {
  rbtree_node *y = T->nil;
  rbtree_node *x = T->nil;
  if ((z->left == T->nil) || (z->right == T->nil)) {
    y = z;
  } else {
    y = rbtree_successor(T, z);
  }
  if (y->left != T->nil) {
    x = y->left;
  } else if (y->right != T->nil) {
    x = y->right;
  }
  x->parent = y->parent;
  if (y->parent == T->nil) {
    T->root = x;
  } else if (y == y->parent->left) {
    y->parent->left = x;
  } else {
    y->parent->right = x;
  }
  if (y != z) {
    z->key = y->key;
    z->value = y->value;
  }
  if (y->color == BLACK) {
    rbtree_delete_fixup(T, x);
  }
  return y;
}
rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key) {
  rbtree_node *node = T->root;
  while (node != T->nil) {
    if (key < node->key) {
      node = node->left;
    } else if (key > node->key) {
      node = node->right;
    } else {
      return node;
    } 
  }
  return T->nil;
}
void rbtree_traversal(rbtree *T, rbtree_node *node) {
  if (node != T->nil) {
    rbtree_traversal(T, node->left);
    printf("key:%d, color:%d\n", node->key, node->color);
    rbtree_traversal(T, node->right);
  }
}

五、完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define RED       1
#define BLACK       2
typedef int KEY_TYPE;
typedef struct _rbtree_node {
  unsigned char color;
  struct _rbtree_node *right;
  struct _rbtree_node *left;
  struct _rbtree_node *parent;
  KEY_TYPE key;
  void *value;
} rbtree_node;
typedef struct _rbtree {
  rbtree_node *root;
  rbtree_node *nil;
} rbtree;
rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) {
  while (x->left != T->nil) {
    x = x->left;
  }
  return x;
}
rbtree_node *rbtree_maxi(rbtree *T, rbtree_node *x) {
  while (x->right != T->nil) {
    x = x->right;
  }
  return x;
}
rbtree_node *rbtree_successor(rbtree *T, rbtree_node *x) {
  rbtree_node *y = x->parent;
  if (x->right != T->nil) {
    return rbtree_mini(T, x->right);
  }
  while ((y != T->nil) && (x == y->right)) {
    x = y;
    y = y->parent;
  }
  return y;
}
void rbtree_left_rotate(rbtree *T, rbtree_node *x) {
  rbtree_node *y = x->right;  // x  --> y  ,  y --> x,   right --> left,  left --> right
  x->right = y->left; //1 1
  if (y->left != T->nil) { //1 2
    y->left->parent = x;
  }
  y->parent = x->parent; //1 3
  if (x->parent == T->nil) { //1 4
    T->root = y;
  } else if (x == x->parent->left) {
    x->parent->left = y;
  } else {
    x->parent->right = y;
  }
  y->left = x; //1 5
  x->parent = y; //1 6
}
void rbtree_right_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->right = y;
  y->parent = x;
}
void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {
  while (z->parent->color == RED) { //z ---> 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; //z --> RED
      } else {
        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);
      }
    }else {
      rbtree_node *y = z->parent->parent->left;
      if (y->color == RED) {
        z->parent->color = BLACK;
        y->color = BLACK;
        z->parent->parent->color = RED;
        z = z->parent->parent; //z --> RED
      } else {
        if (z == z->parent->left) {
          z = z->parent;
          rbtree_right_rotate(T, z);
        }
        z->parent->color = BLACK;
        z->parent->parent->color = RED;
        rbtree_left_rotate(T, z->parent->parent);
      }
    }
  }
  T->root->color = BLACK;
}
void rbtree_insert(rbtree *T, rbtree_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 ;
    }
  }
  z->parent = y;
  if (y == T->nil) {
    T->root = z;
  } else if (z->key < y->key) {
    y->left = z;
  } else {
    y->right = z;
  }
  z->left = T->nil;
  z->right = T->nil;
  z->color = RED;
  rbtree_insert_fixup(T, z);
}
void rbtree_delete_fixup(rbtree *T, rbtree_node *x) {
  while ((x != T->root) && (x->color == BLACK)) {
    if (x == x->parent->left) {
      rbtree_node *w= x->parent->right;
      if (w->color == RED) {
        w->color = BLACK;
        x->parent->color = RED;
        rbtree_left_rotate(T, x->parent);
        w = x->parent->right;
      }
      if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
        w->color = RED;
        x = x->parent;
      } else {
        if (w->right->color == BLACK) {
          w->left->color = BLACK;
          w->color = RED;
          rbtree_right_rotate(T, w);
          w = x->parent->right;
        }
        w->color = x->parent->color;
        x->parent->color = BLACK;
        w->right->color = BLACK;
        rbtree_left_rotate(T, x->parent);
        x = T->root;
      }
    } else {
      rbtree_node *w = x->parent->left;
      if (w->color == RED) {
        w->color = BLACK;
        x->parent->color = RED;
        rbtree_right_rotate(T, x->parent);
        w = x->parent->left;
      }
      if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
        w->color = RED;
        x = x->parent;
      } else {
        if (w->left->color == BLACK) {
          w->right->color = BLACK;
          w->color = RED;
          rbtree_left_rotate(T, w);
          w = x->parent->left;
        }
        w->color = x->parent->color;
        x->parent->color = BLACK;
        w->left->color = BLACK;
        rbtree_right_rotate(T, x->parent);
        x = T->root;
      }
    }
  }
  x->color = BLACK;
}
rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) {
  rbtree_node *y = T->nil;
  rbtree_node *x = T->nil;
  if ((z->left == T->nil) || (z->right == T->nil)) {
    y = z;
  } else {
    y = rbtree_successor(T, z);
  }
  if (y->left != T->nil) {
    x = y->left;
  } else if (y->right != T->nil) {
    x = y->right;
  }
  x->parent = y->parent;
  if (y->parent == T->nil) {
    T->root = x;
  } else if (y == y->parent->left) {
    y->parent->left = x;
  } else {
    y->parent->right = x;
  }
  if (y != z) {
    z->key = y->key;
    z->value = y->value;
  }
  if (y->color == BLACK) {
    rbtree_delete_fixup(T, x);
  }
  return y;
}
rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key) {
  rbtree_node *node = T->root;
  while (node != T->nil) {
    if (key < node->key) {
      node = node->left;
    } else if (key > node->key) {
      node = node->right;
    } else {
      return node;
    } 
  }
  return T->nil;
}
void rbtree_traversal(rbtree *T, rbtree_node *node) {
  if (node != T->nil) {
    rbtree_traversal(T, node->left);
    printf("key:%d, color:%d\n", node->key, node->color);
    rbtree_traversal(T, node->right);
  }
}
int main() {
  int keyArray[20] = {24,25,13,35,23, 26,67,47,38,98, 20,19,17,49,12, 21,9,18,14,15};
  rbtree *T = (rbtree *)malloc(sizeof(rbtree));
  if (T == NULL) {
    printf("malloc failed\n");
    return -1;
  }
  T->nil = (rbtree_node*)malloc(sizeof(rbtree_node));
  T->nil->color = BLACK;
  T->root = T->nil;
  rbtree_node *node = T->nil;
  int i = 0;
  for (i = 0;i < 20;i ++) {
    node = (rbtree_node*)malloc(sizeof(rbtree_node));
    node->key = keyArray[i];
    node->value = NULL;
    rbtree_insert(T, node);
  }
  rbtree_traversal(T, T->root);
  printf("----------------------------------------\n");
  for (i = 0;i < 20;i ++) {
    rbtree_node *node = rbtree_search(T, keyArray[i]);
    rbtree_node *cur = rbtree_delete(T, node);
    free(cur);
    rbtree_traversal(T, T->root);
    printf("----------------------------------------\n");
  }
}

文章参考与<零声教育>的C/C++linux服务期高级架构线上课学习。有兴趣的同学可以了解下哦。

文章标签：
算法
基层搬砖的Panda
目录
相关文章
只是雪豹
|
7月前
|
关系型数据库 容器
红黑树的简单介绍
红黑树的简单介绍
只是雪豹
57 0
cheems~
|
7月前
|
存储 应用服务中间件 调度
随处可见的红黑树详解
随处可见的红黑树详解
cheems~
81 0
技术鱼.
|
7月前
|
存储 调度
红黑树总结
红黑树总结
技术鱼.
72 0
廖文
|
2月前
|
应用服务中间件 Linux 调度
红黑树
红黑树
廖文
25 0
嘎嘎旺
|
6月前
|
关系型数据库 C++
【c++】红黑树
【c++】红黑树
嘎嘎旺
28 0
炫酷的伊莉娜
|
7月前
|
C++ 容器
【C++】红黑树（上）
【C++】红黑树（上）
炫酷的伊莉娜
61 1
达达达达达达
|
6月前
|
Linux 调度 数据库
红黑树详解
红黑树详解
达达达达达达
95 0
toKeep
|
7月前
|
Linux C++
红黑树的实现
红黑树的实现
toKeep
45 2
我也要当昏君
|
7月前
|
调度
随处可见的红黑树
随处可见的红黑树
我也要当昏君
44 0
北海。
|
7月前
|
存储 Linux 调度
C++【红黑树】
C++【红黑树】
北海。
67 0

热门文章

最新文章

  • 1
    docker容器里安装ssh
  • 2
    优秀的代码都是如何分层的？
  • 3
    RDS入门——Excel文件转存到RDS数据库实践
  • 4
    3、Python与设计模式--建造者模式
  • 5
    PostgreSQL SQL HINT的使用
  • 6
    跟阿里云技术专家阙寒一起深度了解视频直播CDN技术
  • 7
    AjaxFileUploader上传插件 兼容性好
  • 8
    （转载） 数组a[]={3,5,2,4,1,8}，要求从a中找出所有“和”等于10的子集
  • 9
    SAP WM Movement Type Mail Control for Background processing
  • 10
    Ext 4 概述（七）之面板Panel &amp; 杂项
  • 1
    自学记录HarmonyOS Next DRM API 13：构建安全的数字内容保护系统
    43
  • 2
    《MaxFrame：数据处理的卓越实践与提升》
    58
  • 3
    《DataWorks：数据处理的卓越实践与改进思考》
    51
  • 4
    三维球体空间中光线反射模拟与三维点云提取matlab仿真
    50
  • 5
    《多模态数据信息提取解决方案的体验与部署》
    47
  • 6
    基于PSO优化的PV光伏发电系统simulink建模与仿真
    57
  • 7
    数据链中常见电磁干扰matlab仿真,对比噪声调频,线性调频,噪声,扫频,灵巧五种干扰模型
    51
  • 8
    《破局之路：人工智能产业的健康发展》
    39
  • 9
    《强化学习算法在动态环境中的优化之路》
    44
  • 10
    《大模型训练成本高，如何在不牺牲性能的前提下破局》
    43

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    手把手教你白嫖阿里云服务器(免费领服务器)