二叉树与红黑树重制版(二)

简介: 二叉树与红黑树重制版(二)

介绍

红黑树是网红,应用非常广泛。对于二叉排序树,有些极端的情况下会转成链表,降低了效率,所以引入了平衡因子,而对于AVL平衡树是强平衡,实现起来较复杂;所以引入了弱平衡的红黑树。

定义性质

1 每个结点都是红的或黑的

2 根结点为黑

3 叶子结点为黑

4 若一个结点为红,则两个儿子都是黑

5 对于每个结点,从该结点到其子孙结点的所有路径上包含相同的黑结点高度。

应用

两种用法:


a) key_value方式用于查找,性能快O(logn)

b) 使用中序遍历(注意层次遍历和中序遍历是一样的)


应用:

1 Linux进度调度CFS

2 Nginx Timer事件管理

3 Epoll事件块处理等

旋转

三个方向,六根指针进行操作

//左旋 参数:红黑树T,当前结点轴心
void rbtree_left_rotate(rbtree *T, rbstree_node *x){
        rbtree_node *y = x->right;
        //x y 都拿到了
        //1 第一步 x的柚子树指向y的左子树
        x->right = y->left;
        //2 第二步 y的左子树不等nil
        if (y->left != T->nil){
                y->left->parent = x;
        }
        //3 第三部 y的parent指向原来x的parent
        y->parent = x->parent;
        //4 第四部 x的parent为nil,则x是根结点
        if (x->parent == T->nil){
                T->root = y;
        }else if(x == x->parent->left){
                x->parent->left = y;
        }else{
                x->parent->right = y;
        }
        //5 第五部
        y->left = x;
        //6 第六部
        x->parent = y;
}
//右旋 的基础上 x-->y   y-->x  left-->right  right-->left
void rbtree_right_rotate(rbtree *T, rbstree_node *x){
        rbtree_node *x = y->left;
        //x y 都拿到了
        y->left = x->right;
        if (x->right != T->nil){
                x->left->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;
}

添加

三种情况:

父节点是祖父结点的左子树情况

1 叔结点是红色

2 叔结点是黑色,且当前结点是右子树

3 叔结点是黑色,且当前结点是左子树

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;
  //找到z指定的位置
  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;
  //1 当前就只有一个结点
  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;
}

完整代码

https://github.com/hengfengyaoren/Data-Structure-Algorithm/blob/main/rbtree.c

目录
相关文章
|
7月前
|
算法 C++ 开发者
【C/C++ 数据结构 】二叉树基本性质:对于任何一颗二叉树T,若其终端结点为n0 ,那么度数为2的结点数为n2。则n0=n2+1...
【C/C++ 数据结构 】二叉树基本性质:对于任何一颗二叉树T,若其终端结点为n0 ,那么度数为2的结点数为n2。则n0=n2+1...
87 0
|
4月前
|
存储 关系型数据库 Java
红黑树,B+树,B树的原理
红黑树(Red-Black Tree)、B树(B-Tree)和 B+树(B+ Tree)都是自平衡的树结构,用于高效地进行查找、插入和删除操作。它们在数据库和文件系统等应用中有广泛的应用。
112 2
|
2月前
|
算法 API
二叉树与红黑树重制版(一)
二叉树与红黑树重制版(一)
29 0
|
5月前
|
存储
【数据结构】AVL树——平衡二叉搜索树
【数据结构】AVL树——平衡二叉搜索树
|
7月前
|
存储 关系型数据库 索引
平衡二叉树,红黑树,B树和B+树的区别及其应用场景
平衡二叉树,红黑树,B树和B+树的区别及其应用场景
57 0
学习平衡搜索二叉树(AVL树)【日志】
学习平衡搜索二叉树(AVL树)【日志】
87 0
|
Java
红黑树(中)完整建树过程
手撕JAVA(十四)一文中有些地方表述有误,笔者日后在做修改。这里用画图的方式展示两次红黑树的完整建图过程,一次简单,一次复杂,根据建图过程,就可以理解红黑树是如何实现的。 总结的几点为: 1.根节点必为黑色,任何调整动作都无法将根节点染红 2.新插入节点的父节点和uncle节点同为红色,直接染黑父节点和uncle节点,染红祖父节点(如果祖父节点为根节点,就免疫)
75 0
|
算法
算法系列-多叉树的遍历
在内卷潮流的席卷下,身为算法小白的我不得不问自己,是否得踏上征程,征服这座巍巍高山。 从零开始,终点不知何方,取决于自己可以坚持多久。 希望你可以和我一样,克服恐惧,哪怕毫无基础,哪怕天生愚钝,依然选择直面困难。
数据结构152-二叉搜索树-删除节点有一个子节点代码
数据结构152-二叉搜索树-删除节点有一个子节点代码
66 0
数据结构152-二叉搜索树-删除节点有一个子节点代码
数据结构~基础2~树【《二叉树、二叉搜索树、AVL树、B树、红黑树》的设计】~红黑树
数据结构~基础2~树【《二叉树、二叉搜索树、AVL树、B树、红黑树》的设计】~红黑树
123 0
数据结构~基础2~树【《二叉树、二叉搜索树、AVL树、B树、红黑树》的设计】~红黑树