红黑树(RBTree)

印象里面在数据查找当中，常见的数据结构有 红黑树、哈希表、b/b+树、跳表。

一、红黑树

1.1、应用场景

个人印象里面，在以下场景中使用较多：

• C++ STL中的map，set
• epoll底层数据结构之一
• Linux的进程调度(CFS)
• nginx的定时器管理
• 各种含有key,value的数据查找场景

1.2、定义

红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过2。

1.3、特性

• 每个节点都是红的或者黑的
• 根节点是黑的
• 每个叶子节点是黑的
• 如果一个节点是红的，则它的两个子节点都是黑的
• 对每个节点，从该节点到其子孙节点的所有路径上包含相同数量的黑节点------决定红黑树的高度
  

1.4、从根节点出发，最长路径最大能包含多少节点？

从根节点出发，红黑树的最短路径和最长路径的节点数差异是2倍。这意味着，如果最短路径包含n个节点，那么最长路径将包含最多2n-1个节点。

二、具体实操

2.1、如何定义红黑树?

typedef struct _rbtree_node{int key;void* value;struct _rbtree_node* left;struct _rbtree_node* right;struct _rbtree_node* parent;unsigned char color; // 0: red, 1: black
}rbtree_node;// 叶子节点都是黑色的，可以定义为空节点，为了好判断，不能定义为NULL，否则是非法操作
typedef struct _rbtree{struct _rbtree_node* root;struct _rbtree_node* nil; // 叶子节点，黑色的空节点int size; // 树中节点的数量
}rbtree;

2.2、旋转：

• 红黑树性质被破坏的时候会发生旋转
  

void leftRotate(rbtree* tree, rbtree_node* x)
{rbtree_node* y = x->right; // 右子节点// 断x与y的父子关系x->right = y->left; // 让左子节点成为右子节点的父节点if(y->left != tree->nil) // 如果左子节点不是叶子节点，则更新父节点的指向{y->left->parent = x;}// 断x与x父节点的父子关系，并建立x父节点与y的父子关系y->parent = x->parent; // 让y的父节点指向x的父节点if(x->parent == tree->nil) // 如果x是根节点，则更新根节点的指向{tree->root = y;}else if(x == x->parent->left) // 如果x是其父节点的左子节点，则更新其父节点的左子节点{x->parent->left = y;}else // 如果x是其父节点的右子节点，则更新其父节点的右子节点{x->parent->right = y;}// 更新x与y的父子关系y->left = x; // 让x成为y的左子节点x->parent = y; // 更新父节点的指向
}// 将左旋反过来，x变y，left变right，right变left
void rightRotate(rbtree* tree, rbtree_node* y)
{rbtree_node* x = y->left; // 左子节点// 断y与x的父子关系y->left = x->right; // 让右子节点成为左子节点的父节点if(x->right != tree->nil) // 如果右子节点不是叶子节点，则更新父节点的指向{x->right->parent = y;}// 断y与y父节点的父子关系，并建立y父节点与x的父子关系x->parent = y->parent; // 让x的父节点指向y的父节点if(y->parent == tree->nil) // 如果y是根节点，则更新根节点的指向{tree->root = x;}else if(y == y->parent->right) // 如果y是其父节点的右子节点，则更新其父节点的右子节点{y->parent->right = x;}else // 如果y是其父节点的左子节点，则更新其父节点的左子节点{y->parent->left = x;}// 更新y与x的父子关系x->right = y; // 让y成为x的右子节点y->parent = x; // 更新父节点的指向
}

2.3、插入：

• 插入节点默认为红色

void rbtree_insert(rbtree* tree, rbtree_node* node)
{rbtree_node* y = tree->nil;  // 记录x的父节点rbtree_node* x = tree->root; // 根节点// 找到插入的位置while(x != tree->nil) // 如果不是叶子节点，则继续查找{   y = x; // 记录父节点if(node->key < x->key) // 如果插入节点的键小于当前节点的键，则向左子节点查找{x = x->left;}else if(node->key > x->key) // 如果插入节点的键大于等于当前节点的键，则向右子节点查找{x = x->right;}else{      // 如果插入节点的键等于当前节点的键，则替换当前节点x->value = node->value;}}// 如果是空红黑树，则直接插入if(y == tree->nil) // 如果y是叶子节点，则直接插入{tree->root = node; // 更新根节点}else{if(y->key > node->key) // 如果插入节点的键小于父节点的键，则将插入节点设置为左子节点{y->left = node;}else // 如果插入节点的键大于父节点的键，则将插入节点设置为右子节点{y->right = node;}}node->parent = y; // 更新父节点node->left = tree->nil;node->right = tree->nil;node->color = 0 ; // 新插入的节点默认为红色，不改变黑高// 插入之后，进行旋转和变色insertFixup(tree, node);
}

以N-新节点，P-父节点，G-祖父节点，U-叔父节点的命名方式来描述插入之后的调整过程。

情况	条件	调整
1	N是根节点	将N的颜色改为黑色，结束调整。
2	U是红色，P是G的左子节点	将P和U的颜色改为黑色，G的颜色改为红色，然后以G作为新的N继续向上调整
3	U是红色，P是G的右子节点	将P和U的颜色改为黑色，G的颜色改为红色，然后以G作为新的N继续向上调整
4	U是黑色，P是G的左子节点，N是P的左子节点(LL)	将P的颜色改为黑色，G的颜色改为红色，然后对G进行右旋。
5	U是黑色，P是G的左子节点，N是P的右子节点(LR)	对P进行左旋，N的颜色改为黑色，G的颜色改为红色，对G进行右旋。
6	U是黑色，P是G的右子节点，N是P的左子节点(RL)	对P进行右旋，N的颜色改为黑色，G的颜色改为红色，对G进行左旋。
7	U是黑色，P是G的右子节点，N是P的右子节点(RR)	将P的颜色改为黑色，G的颜色改为红色，然后对G进行左旋。

默认叶子节点不出现

// 插入之后的调整
void insertFixup(rbtree* tree, rbtree_node* node)
{rbtree_node* parent = node->parent;rbtree_node* grandparent = NULL;rbtree_node* uncle = NULL;// 如果节点本身是红色while(parent->color == 0) // 如果父节点是红色，那么祖父节点必是黑色，叔父节点可能是红色或黑色{grandparent = parent->parent; // 获取祖父节点if(parent == grandparent->left) // 如果父节点是其祖父节点的左子节点{uncle = grandparent->right; // 叔父节点// 情况2和3：叔父节点是红色if (uncle->color == 0){parent->color = 1; // 将父节点变为黑色uncle->color = 1; // 将叔父节点变为黑色grandparent->color = 0; // 将祖父节点变为红色node = grandparent; // 继续向上调整}else // 叔父节点是黑色{// 情况4：N是P的左子节点(LL)if (node == parent->left){rightRotate(tree, grandparent); // 对祖父节点进行右旋parent = node->parent; // 更新父节点}// 情况5：N是P的右子节点(LR)else{leftRotate(tree, parent); // 对父节点进行左旋parent = node->parent; // 更新父节点rightRotate(tree, grandparent); // 对祖父节点进行右旋}parent->color = 1; // 将父节点变为黑色grandparent->color = 0; // 将祖父节点变为红色node = parent; // 继续向上调整}}else // 父节点是其祖父节点的右子节点{uncle = grandparent->left; // 获取叔父节点// 情况2和3：叔父节点是红色if (uncle->color == 0){parent->color = 1; // 将父节点变为黑色uncle->color = 1; // 将叔父节点变为黑色grandparent->color = 0; // 将祖父节点变为红色node = grandparent; // 继续向上调整}else // 叔父节点是黑色{// 情况6：N是P的左子节点(RL)if (node == parent->left){rightRotate(tree, parent); // 对父节点进行右旋parent = node->parent; // 更新父节点leftRotate(tree, grandparent); // 对祖父节点进行左旋}// 情况7：N是P的右子节点(RR)else{leftRotate(tree, grandparent); // 对祖父节点进行左旋parent = node->parent; // 更新父节点}parent->color = 1; // 将父节点变为黑色grandparent->color = 0; // 将祖父节点变为红色node = parent; // 继续向上调整}}}tree->root->color = 1; // 将根节点变为黑色
}

三、问题

3.1、map为什么不用avl树?

AVL树是一种严格平衡的二叉树，要求每个节点的左右子树的高度最多相差1，在大量地进行插入和删除操作时，AVL树需要频繁地进行旋转来维持平衡状态，这会导致较高的时间复杂度。

而RB树（红黑树）是非严格的平衡二叉树，只要从根节点到叶子节点的最长路径不超过最短路径的2倍，那么就不用进行频繁地进行平衡调节，使得插入、删除、查找效率稳定在O(logn)级别。

Code
0vice·GitHub