本文共 7427 字，大约阅读时间需要 24 分钟。
点击关注上方“五分钟学算法”，
设为“置顶或星标”，第一时间送达干货。
转自景禹
红黑树的插入
在一棵AVL树中，我们通过左旋和右旋来调整由于插入和删除所造成的不平衡问题。在红黑树中，可以使用两种方式进行平衡操作：
重新着色
旋转
当红黑树中出现不平衡的状态，我们首先会考虑重新着色，如果重新着色依旧不能使红黑树平衡，那么就考虑旋转。插入操作主要有两种情况，具体取决于叔叔结点的颜色。如果叔叔结点是红色的，我们会重新着色。如果叔叔结点是黑色的，我们会旋转或者重新着色，或者两者都考虑。
一个 NULL 结点被认为是黑色的，这在上篇已经提到过。
设 x 为新插入的结点。
进行标准的 BST 插入并将新插入的结点设置为红色。
如果 x 是根结点，将 x 的颜色转化为黑色（整棵树的黑高增加 1）。
如果 x 的父结点 p 不是黑色并且 x 不是根结点，则：
a) 如果 x 的叔叔结点 u 是红色。
b) 如果 x 的叔叔结点 u 是黑色，则对于 x、 x 的父结点 p 和 x 的爷爷结点 g有以下四种情况：
LL（p 是 g 的左孩子且 x 是 p 的左孩子）
LR （p 是 g 的左孩子且 x 是 p 的右孩子）
RR （p 是 g 的右孩子且 x 是 p 的右孩子）
RL（p 是 g 的右孩子且 x 是 p 的左孩子）
将插入结点 x 的父结点（Parent ）p 和叔叔（uncle）结点 u 的颜色变为黑色；
将 x 的爷爷结点（Grand Parent）g 设置为红色；
将 x = x的爷爷结点 g ，对于新的 x 重复 2，3两步。
插入结点 x 的叔叔结点 u 为红色
无规矩不能说清楚问题，无图不欢，我们做如下约定：
对于新插入结点 x，我们执行标准的 BST 插入之后，将插入结点 x 着色为红色；如果插入结点不是根结点，且x的父结点 p 为红色结点，分为 a) 和 b) 两种情况处理，我们先看的是 a) 的情况：x 的叔叔结点 u 为红色，如下图所示：
第一步：将 p 和 u 的颜色设置为 黑色
第二步：将 g 的颜色设置为红色
第三步：将 x = g，对 g 重复执行算法框架中的 2，3 两步。
不要嫌我烦，我又得说一说 2，3 两步是干嘛的
如果 x 是根结点，将 x 的颜色转化为黑色（整棵树的黑高增加 1）。
如果 x 的父结点 p 不是黑色并且 x 不是根结点，则：
a).
b).
a) 我们已经讲过了，综合来看就如下图所示：
那我们接下来看看 b) 的情况下该如何处理。
插入结点 x 的叔叔结点 u 为黑色
当插入结点 x 的叔叔结点为的时候，根据插入结点 x 、x 的父结点 p 和 x 的爷爷结点 g 可能出现的位置关系，分为以下四种情况：
LL
LR
首先通过 左旋 p 转化为 LL 的情况：
然后按照 LL 的情况处理：
RR
RL
首先 右旋 p 转化为 RR 的情况：
然后按照 RR 的情况处理：
到这里，插入排序可以说是已经讲完了，但我知道有些朋友难免会感到困惑，那就让我们一起构造一颗自己的红黑树，解决掉所有的困惑吧！
红黑树插入操作案例
下面就带大家构造一颗稍微复杂一点儿的红黑树：
初始时，我们仅已知下面要依次插入的序列：
第一步：插入结点 2 ，结点 2 就是根结点，设置为黑色：
第二步：插入结点 6 ，首先执行标准的 BST 插入操作并将结点 6 设置为红色，但 6 号结点的父结点 2 的颜色为黑色，所以什么都不做了。
第三步：插入结点 9（x） ，执行标准的 BST 插入操作并设置为红色，其父结点 6（p） 的颜色为红色且且叔叔结点为 NULL结点为黑色，属于 RR 的情况，故对其爷爷结点 2（g） 进行左旋操作，并交换 g 和 p 的颜色。
第四步：插入结点 10（x） ，执行标准的 BST 插入操作并设置为红色，其父结点 9（p） 为红色，其叔叔结点 2（u） 为红色结点，属于 a)的情况，将其父结点 9 和叔叔结点涂黑色，并将其爷爷结点涂红色并设置为新的x，判断其爷爷结点 6 ，发现为根结点，重新更新为黑色。
第五步：插入结点 12（x） ，执行标准的BST插入操作并设置为红色，其父结点 10（p） 为红色，其叔叔结点为黑色，其爷爷结点 9（g） 为红色，RR 的情况，则左旋 g ，交换 g 和 p 的颜色。
接下来的步骤我希望小禹禹可以忘记 x、p、g、u ，所谓忘记，就是让你沉浸其中，无我，但是所有的过程你又是无比清晰，我想你得 道 了。
第六步：插入结点 15
第七步：插入结点 20
第八步：插入结点 18 （注意这里我故意少了一步，要心中补上）
第九步：插入结点 1
第十步：插入结点 5
第十一步：插入结点 13
红黑树插入操作的实现
结点的定义，增加了父结点指针以及结点颜色标记：
struct Node { int data; bool color; Node *left, *right, *parent; // 构造器 Node(int data) { this->data = data; left = right = parent = NULL; this->color = RED; } }; 标准的二叉排序树的插入操作
/*标准的二叉排序树的插入操作*/Node* BSTInsert(Node* root, Node *x) { /* 如果树为空，则插入的结点作为根结点返回 */ if (root == NULL) return x; /* x的值小于根结点的值，则向左子树走 */ if (x->data < root->data) { root->left = BSTInsert(root->left, x); root->left->parent = root; } else if (x->data > root->data) { root->right = BSTInsert(root->right, x); root->right->parent = root; } /* 返回插入结点 x 的树根*/ return root; } 红黑树中结点的左旋操作
红黑树中的左旋操作与AVL树中讲的结点的左旋操作类似，但是这里需要修改结点的父指针，所以情况可能稍微复杂一点儿，但只要你对照着我花费时间给你画的图，理解起来也不是很难。
void RBTree::rotateLeft(Node *&root, Node *&g) { Node *p = g->right; g->right = p->left; //g->right = T3 if (g->right != NULL) //T3 != NULL g->right->parent = g; //T3->parent = g p->parent = g->parent; if (g->parent == NULL) { root = p; } else if (g == g->parent->left) { g->parent->left = p; } else{ g->parent->right = p; } p->left = g; g->parent = p; } 红黑树中结点的右旋操作
void RBTree::rotateRight(Node *&root, Node *&g) { Node *p = g->left; g->left = p->right; if (g->left != NULL) g->left->parent = g; p->parent = g->parent; if (g->parent == NULL) root = p; else if (g == g->parent->left) g->parent->left = p; else g->parent->right = p; p->right = g; g->parent = p; } 由于插入结点造成不平衡时的平衡处理
看这个代码的时候注意配合最前面的算法框架描述会更清楚一些。
// 处理由于红黑树结点的插入操作所造成的平衡问题 void RBTree::fixViolation(Node *&root, Node *&pt) { Node *parent_pt = NULL; Node *grand_parent_pt = NULL; while ((pt != root) && (pt->color != BLACK) && (pt->parent->color == RED)) { parent_pt = pt->parent; grand_parent_pt = pt->parent->parent; /* 情况一: pt的父结点parent_pt 是其爷爷结点grand_parent_pt的左孩子 */ if (parent_pt == grand_parent_pt->left) { Node *uncle_pt = grand_parent_pt->right; /* Case : a) pt 的叔叔结点 uncle_pt 为红色结点 只需要调整结点颜色，不需要旋转*/ if (uncle_pt != NULL && uncle_pt->color == RED) { grand_parent_pt->color = RED; parent_pt->color = BLACK; uncle_pt->color = BLACK; pt = grand_parent_pt; } else // Case :b) x 的叔叔结点为黑色 { /* Case : 2 pt 是其父结点的右孩子 需要左旋操作 */ if (pt == parent_pt->right) { rotateLeft(root, parent_pt); pt = parent_pt; parent_pt = pt->parent; } /* Case : 3 pt 是其父结点的左孩子 需要右旋操作 */ rotateRight(root, grand_parent_pt); swap(parent_pt->color, grand_parent_pt->color); pt = parent_pt; } } /* 情况二: pt的父结点parent_pt 是其爷爷结点grand_parent_pt的左孩子 */ else { Node *uncle_pt = grand_parent_pt->left; /* Case : a) pt 的叔叔结点 uncle_pt 为红色结点 只需要调整结点颜色，不需要旋转*/ if ((uncle_pt != NULL) && (uncle_pt->color == RED)) { grand_parent_pt->color = RED; parent_pt->color = BLACK; uncle_pt->color = BLACK; pt = grand_parent_pt; } else // Case :b) x 的叔叔结点为黑色 { /* Case : 2 pt 是其父结点的右孩子 需要左旋操作 */ if (pt == parent_pt->left) { rotateRight(root, parent_pt); pt = parent_pt; parent_pt = pt->parent; } /* Case : 3 pt 是其父结点的左孩子 需要右旋操作 */ rotateLeft(root, grand_parent_pt); swap(parent_pt->color, grand_parent_pt->color); pt = parent_pt; } } } //如果是根结点，颜色置为黑色 root->color = BLACK; } 红黑树插入操作代码
// 红黑树插入操作 void RBTree::insert(const int &data) { Node *pt = new Node(data); // 执行标准的BST插入操作 root = BSTInsert(root, pt); // 进行平衡处理 fixViolation(root, pt); } 应用案例
题目描述
给定一个二叉树，判断它是否是一颗类似于红黑树一样的高度平衡的二叉树。
本题中，一棵类似于红黑树高度平衡的二叉树定义为：
对于每一个结点的最大高度不超过最小高度的2倍。
输入输出示例
10 4 \ / \ 12 1 10 \ / \ 20 6 15 高度不平衡，10的最大高度为3，最小高度为1 高度平衡，可以是一颗红黑树 16 / \ 5 65 / \ 32 75 / 30 高度平衡，可以是一颗红黑树
题目解析
对于每一个结点，到最远的叶结点的路径长度未超过到最近的叶结点的路径长度的两倍，期望时间复杂度为 ，也就是树中的每一个结点都只能遍历一次。
看到这里，希望你停下来，给你的大脑一个机会，思考一下。
思路，遍历树中的每一个结点，获取结点的最大高度与最小高度，并进行比较，判断是否平衡。我们可以设计一个返回三个值的递归函数，一个布尔值（表示树是否平衡），结点的最小高度和最大高度，其中布尔值可以直接返回，而结点的最小高度和最大高度通过引用传递实现，以便在递归返回时父调用使用这些值。
using namespace std; struct Node { int key; Node *left, *right; }; /* 创建一个新的结点 */Node* newNode(int key) { Node* node = new Node; node->key = key; node->left = node->right = NULL; return (node); } // 判断二叉树是否与bool isBalancedUtil(Node *root, int &maxh, int &minh) { // 如果是叶子结点，必然是平衡结点，返回true if (root == NULL) { maxh = minh = 0; return true; } int lmxh, lmnh; // 存储左子树的最大与最小高度 int rmxh, rmnh; // 存储右子树的最大与最小高度 // 检查左子树是否平衡，并设置左子的最大与最小高度 if (isBalancedUtil(root->left, lmxh, lmnh) == false) return false; // 检查右子树是否平衡，并设置右子树的最大与最小高度 if (isBalancedUtil(root->right, rmxh, rmnh) == false) return false; // root 的最大高度为左子树与右子树最大高度的最大值+1 // root 的最小高度为左右子树的最小高度的最小值 + 1 maxh = max(lmxh, rmxh) + 1; minh = min(lmnh, rmnh) + 1; // 如果结点的最大高度小于等于最小高度的两倍，返回true if (maxh <= 2*minh) return true; return false; } // 对 isBalancedUtil() 进行包装bool isBalanced(Node *root) { int maxh, minh; return isBalancedUtil(root, maxh, minh); } int main() { Node * root = newNode(16); root->left = newNode(5); root->right = newNode(65); root->right->left = newNode(32); root->right->right = newNode(75); root->right->left->left = newNode(30); isBalanced(root)? cout << "Balanced" : cout << "Not Balanced"; return 0; } 推荐阅读
• • • • • • •
欢迎关注我的公众号“五分钟学算法”，如果喜欢，麻烦点一下“在看”~
转载地址：http://pxqqz.baihongyu.com/