本文详细讲解了红黑树的性质、查询、插入操作中的插入并维持二叉搜索树、调整红黑树，以及删除节点后的调整策略。涉及红黑树的完整代码示例，并针对map和multi_map的不同应用。重点介绍了OJ实战中的给定二叉搜索树插入顺序求深度问题的解决方案。
目录
一，红黑树
一颗二叉搜索树，首先把节点的孩子补齐，把空指针都换成指向NIL节点的指针，其中NIL节点是一个特殊的无意义的节点。
这样，这颗二叉搜索树就变成Full Binary Tree：
PS：有效节点的度都是2，NIL节点都是叶子节点，度都是0，反之，叶子节点也都是NIL节点。
如果这颗二叉树满足如下条件，那么它就是红黑树：
- Each node is either red or black.
- All leaves (NIL) are considered black.
- If a node is red, then both its children are black.
- Every path from a given node to any of its descendant NIL leaves goes through the same number of black nodes.
也就是说，每个节点都是红黑二选一，NIL叶子节点都是黑的，红节点一定有2个黑孩子，任意一条从根到NIL的路径上的黑色节点的数量都是相同的。
注意：
1，另外一种版本的红黑树，要求根节点必须是黑色节点，为了方便，我们用V4和V5区分他们，默认讨论V4
2，NIL节点是为了描述简洁而加上的逻辑概念，在实现层面，可以不用NIL节点，我在本文中的代码实现，都是没有NIL节点的。
二，红黑树的性质
根据条件1,2,3，每条路径上黑色节点数量 >= 红色节点数量，对于红黑树V5，每条路径上黑色节点数量 > 红色节点数量
再根据条件4，每条路径总长度 <= 任意一条路径总长度 * 2，换句话说，the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.
也就是说，红黑树是比较平衡的，但是又没有平衡二叉树那么严格。
在操作过程中，条件1,2一般不会变，条件3,4容易违背，需要调整，为了方便，我们分别称之为red-violation、black-violation
三，红黑树的查询
红黑树作为一棵二叉搜索树，查询过程和普通二叉搜索树完全相同。
typedef enum Flag{
RED = 0,
BLACK = 1
}Flag;
struct TreeNode {
int val;
Flag flag;
TreeNode *fa;
TreeNode *left;
TreeNode *right;
};
TreeNode* find(TreeNode* root, int val)
{
if(!root)return NULL;
if(root->val==val)return root;
if(root->val>val)return find(root->left,val);
return find(root->right,val);
}
//find first node.val > val
Treenode* findBig(Treenode* root, int val)
{
if (!root)return NULL;
if (root->val <= val)return findBig(root->right, val);
auto ans = findBig(root->left, val);
return ans? ans:root;
}
//find last node.val < val
Treenode* findSmall(Treenode* root, int val)
{
if (!root)return NULL;
if (root->val >= val)return findSmall(root->left, val);
auto ans = findSmall(root->right, val);
return ans ? ans : root;
}四，红黑树的插入
插入和平衡二叉树类似，分两步，先插入再调整。
1，插入并维持二叉搜索树
红黑树作为二叉搜索树，一定可以找到某个NIL叶子节点，把它换成新增节点之后，仍然是一颗二叉搜索树。
为了保持红黑树的特点，新增节点要么是红的要么是黑的，而且它的2个孩子必须是2个NIL黑节点。
因为black-violation比red-violation更难调整解决，所以让新增节点都是红色的会比较简单。
在二叉搜索树和平衡二叉树中，我的实现中，节点都没有指向父亲的指针，所以插入操作比较别扭：
void InsertNode(TreeNode* &root, TreeNode* node);
尤其是平衡二叉树中，还涉及到性能问题。
所以这次，我添加了指向父亲的指针，于是本来一样的插入操作也变的有点不一样了。
void InsertAndLink(TreeNode* root, TreeNode* node)
{
if(root->val>node->val){
if(root->left)InsertAndLink(root->left,node);
else root->left=node,node->fa=root;
}
else {
if(root->right)InsertAndLink(root->right,node);
else root->right=node,node->fa=root;
}
}
void InsertNode(TreeNode* &root, TreeNode* node)
{
if(!root)root=node;
InsertAndLink(root,node);
}
void InsertNode(TreeNode* &root, int val)
{
TreeNode* p = find(root,val);
if(p)return;
p= new TreeNode();
p->val=val, p->flag=RED;
p->fa=NULL, p->left=NULL, p->right=NULL;
InsertNode(root,p);
}PS：
后面还需要在其中添加一个调整操作的调用。
2，调整并维持红黑树
插入红色节点之后，需要解决red-violation，这就需要调整红黑树的结构，并给一些节点变色。
注意：因为下面的分类中，存在递归的情况，所以现在要讨论的情况其实是：
把红黑树中任意一个黑节点变成红节点（new节点），以new节点为根的树已经调整为了一棵以红节点为根的红黑树，调整之后和new节点变化之前相比，所有路径的黑节点的总数并没有发生变化，接下来需要继续往上解决red-violation
（1）new节点没有父节点，或父节点为黑节点
这种情况下，没有red-violation，不需要调整
（2）new节点的父节点为红节点
这种情况下，有red-violation，需要调整。
（2.1）如果父亲节点是根节点
这种情况只有红黑树V4涉及，V5没有这种情况。
这种情况下，直接把根节点变成黑节点即可。
（2.2）如果父亲节点不是根节点，那么就有祖父节点
祖父节点肯定是黑节点，我们再根据祖父节点的另外一个孩子（new节点的叔叔节点）的情况进行分类
（2.2.1）叔叔节点存在，而且是红节点
这种情况下，首先把父亲、祖先、叔叔三个节点都变色：
然后再把祖先节点当做new节点，往上递归即可。
（2.2.2）叔叔节点不存在，或者叔叔节点是黑节点
这种情况和平衡二叉树类似，需要根据从祖父节点到父亲节点再到new节点之间的位置关系，分成LL，RR，LR，RL四种情况。
所以这种情况下，只需要把祖父节点变成黑色，把父亲节点和new节点变成红色，然后再进行对应的4种旋转操作之一，即可完成调整工作。
至此，得到插入节点后调整的代码：
void RotateLL(TreeNode* root)
{
TreeNode* c1 = root->left, * c2 = c1->left;
root->left = c2, c1->left = c1->right, c1->right = root->right, root->right = c1;
int val = root->val;
root->val = c1->val, c1->val = val;
}
void RotateRR(TreeNode* root)
{
TreeNode* c1 = root->right, * c2 = c1->right;
root->right = c2, c1->right = c1->left, c1->left = root->left, root->left = c1;
int val = root->val;
root->val = c1->val, c1->val = val;
}
void RotateLR(TreeNode* root)
{
TreeNode* c1 = root->left, * c2 = c1->right;
root->left = c2, c1->right = c2->left, c2->left = c1;
RotateLL(root);
}
void RotateRL(TreeNode* root)
{
TreeNode* c1 = root->right, * c2 = c1->left;
root->right = c2, c1->left = c2->right, c2->right = c1;
RotateRR(root);
}
void Rotate(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
if(root->left==c1){
if(c1->left==c2)RotateLL(root);
else RotateLR(root);
} else{
if(c1->left==c2)RotateRL(root);
else RotateRR(root);
}
}
void Adjust(TreeNode* root, TreeNode* node)
{
if(!root || !node || root==node)return;
TreeNode* p = node->fa;
if(p == root)p->flag = BLACK;
if(p->flag == BLACK)return;
//到了这里，node就一定有祖父节点，而且父节点是红节点，所以一定有red-violation
TreeNode* pp = p->fa;
int dir=(p==pp->left);
TreeNode* unc = dir?pp->right:pp->left;
if(unc && unc->flag==RED){
pp->flag=RED,p->flag=BLACK,unc->flag=BLACK;
return Adjust(root,pp);
}
//到了这里，叔叔节点要么不存在，要么是黑节点
Rotate(pp,p,node);
pp->flag=BLACK,p->flag=RED,node->flag=RED;
}PS：
这个代码好像还缺了更新fa指针的操作，我在做旋转操作化简之前有补充，但是没有更新到本博客，于是代码被覆盖了。
梳理完插入之后，关于V4和V5的区别也清楚了，V5就是在V4的基础之上，插入和删除的最后都增加一步，直接把根节点变成黑色节点。
3，旋转操作化简
既然有了指向父亲的指针，那么旋转操作其实是可以写的简单一些，包括其中一些值交换的操作也可以换成真正的节点交换。
相应的，最后的变色操作也要略为改动
//让s是p的孩子，dir=1，0 分别表示左孩子和右孩子
void Link(TreeNode* p, TreeNode* s, int dir)
{
if (s)s->fa = p;
if (!p)return;
if (dir)p->left = s;
else p->right = s;
}
void LinkLeft(TreeNode*p,TreeNode*s)
{
Link(p,s,1);
}
void LinkRight(TreeNode*p,TreeNode*s)
{
Link(p,s,0);
}
//把s放到t的位置
void LinkReplace(TreeNode*s,TreeNode*t)
{
Link(t->fa,s,(t->fa && t->fa->left==t));
}
void RotateLL(TreeNode* root)
{
TreeNode* c1 = root->left;
LinkReplace(c1,root);
LinkLeft(root,c1->right);
LinkRight(c1,root);
}
void RotateRR(TreeNode* root)
{
TreeNode* c1 = root->right;
LinkReplace(c1,root);
LinkRight(root,c1->left);
LinkLeft(c1,root);
}
void RotateLR(TreeNode* root)
{
TreeNode* c1 = root->left, * c2 = c1->right;
LinkLeft(root,c2);
LinkRight(c1,c2->left);
LinkLeft(c2,c1);
RotateLL(root);
}
void RotateRL(TreeNode* root)
{
TreeNode* c1 = root->right, * c2 = c1->left;
LinkRight(root,c2);
LinkLeft(c1,c2->right);
LinkRight(c2,c1);
RotateRR(root);
}
void Rotate(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
if (root->left == c1) {
if (c1->left == c2)RotateLL(root);
else RotateLR(root);
}
else {
if (c1->left == c2)RotateRL(root);
else RotateRR(root);
}
}
void InsertNode(TreeNode*& root, TreeNode* node)
{
if (!root)root = node;
else InsertAndLink(root, node);
Adjust(root, node);
while (root->fa)root = root->fa;
}五，红黑树的删除
删除也是和平衡二叉树类似，先删除再调整：
1，删除并维持二叉搜索树
和二叉搜索树一样，删除操作分成三种情况：
（1）没有孩子，直接删除即可
（2）只有一个孩子，用孩子代替它即可
（3）左孩子和右孩子都有的情况下，用后继节点代替它即可
对于第（1）种情况，删除的是叶子节点。
对于第（2）（3）种情况，把代替操作理解为先交换2个节点的值（不交换颜色），再删除代替节点。
所以，经过不断的迭代，可以把删除操作归结为删除叶子节点的问题。
TreeNode* GetMin(TreeNode* root)
{
if (!root)return root;
if (root->left)return GetMin(root->left);
return root;
}
void DeleteNode(TreeNode*& root, TreeNode* node)
{
if (node->left == NULL && node->right == NULL) {
DeleteAdjust(node);
LinkReplace(NULL,node);
return;
}
TreeNode* p;
if (node->left == NULL)p = node->right;
else if (node->right == NULL)p = node->left;
else p = GetMin(node->right);
node->val = p->val;
DeleteNode(root,p);
while (root->fa)root = root->fa;
}2，调整并维持红黑树
如果删除的叶子节点是红节点，就不需要调整，如果是黑节点，就有black-violation，需要调整。
如果叶子节点是红色的，那么就直接删除，如果是黑色的，那么我们调整的思路是，在删除叶子节点之前，让它所在的路径的黑色节点数加1，其他路径的黑色节点数不变，最后删掉这个叶子节点就得到红黑树。
因为下面的分类中，存在递归的情况，所以现在要讨论的情况其实是：
红黑树中任意一个黑节点（D节点），调整红黑树使得D节点所在的路径的黑色节点数加1，其他路径的黑色节点数不变
（1）D节点是红节点
直接把红节点变成黑节点即可
（2）D节点是根节点
对于根节点，它的黑色节点数加1相当于就是整个树全部加1，这种情况下可以不处理
（3）D节点是黑节点，而且不是根节点，那么它一定有父亲节点和兄弟节点
（3.1）兄弟节点是红节点
父亲节点一定是黑节点，兄弟节点一定有2个孩子，而且都是黑节点。
这种情况下，通过旋转，变成兄弟节点是黑节点的情况。
（3.2）兄弟节点是黑节点
再根据兄弟节点有没有红色孩子分类讨论
（3.2.1）兄弟节点有红色孩子
根据从父亲节点到兄弟节点的红色孩子的位置，又分成四种情况：LL、LR、RR、RL
下图是RR和RL
（3.2.2）兄弟节点没有孩子或只有黑色孩子
把兄弟节点设为红色，然后再把父亲节点当做D节点，往上递归即可。
至此，得到删除后的调整代码：
void changeColor(TreeNode* a, TreeNode* b)
{
Flag flag = a->flag;
a->flag = b->flag, b->flag = flag;
}
void DeleteAdjust(TreeNode* node)
{
if (!node || !node->fa)return;
if (node->flag == RED) {
node->flag = BLACK;
return;
}
//到了这里，node节点是黑节点，而且不是根节点，那么它一定有父亲节点和兄弟节点
TreeNode* p = node->fa; //父亲
int dir = (node == p->left);
TreeNode* br = dir ? p->right : p->left; //兄弟
if (br->flag == RED) {
LinkReplace(br, p);
Link(p, dir ? br->left : br->right, !dir);
Link(br, p, dir);
p->flag = RED, br->flag = BLACK;
DeleteAdjust(node);
return;
}
//到了这里，node节点和兄弟节点都是黑节点
TreeNode* brleft = br->left, * brright = br->right;
if (brleft && brleft->flag == RED || brright && brright->flag == RED) {
if (dir) {
if (brleft && brleft->flag == RED) {
brleft->flag = p->flag, p->flag = BLACK;
RotateRL(p);
}
else {
changeColor(p, br);
brright->flag = BLACK;
RotateRR(p);
}
}
else {
if (brright && brright->flag == RED) {
brright->flag = p->flag, p->flag = BLACK;
RotateLR(p);
}
else {
changeColor(p, br);
brleft->flag = BLACK;
RotateLL(p);
}
}
}
else {
br->flag = RED;
DeleteAdjust(p);
}
}六，红黑树完整代码
#include<iostream>
#include <vector>
using namespace std;
#define is_multi_map false
typedef enum Flag {
RED = 0,
BLACK = 1
}Flag;
struct TreeNode {
int val;
Flag flag;
TreeNode* fa;
TreeNode* left;
TreeNode* right;
};
TreeNode* find(TreeNode* root, int val)
{
if (!root)return NULL;
if (root->val == val)return root;
if (root->val > val)return find(root->left, val);
return find(root->right, val);
}
void InsertAndLink(TreeNode* root, TreeNode* node)
{
if (root->val > node->val) {
if (root->left)InsertAndLink(root->left, node);
else root->left = node, node->fa = root;
}
else {
if (root->right)InsertAndLink(root->right, node);
else root->right = node, node->fa = root;
}
}
//让s是p的孩子，dir=1，0 分别表示左孩子和右孩子
void Link(TreeNode* p, TreeNode* s, int dir)
{
if (s)s->fa = p;
if (!p)return;
if (dir)p->left = s;
else p->right = s;
}
void LinkLeft(TreeNode* p, TreeNode* s)
{
Link(p, s, 1);
}
void LinkRight(TreeNode* p, TreeNode* s)
{
Link(p, s, 0);
}
//把s放到t的位置
void LinkReplace(TreeNode* s, TreeNode* t)
{
Link(t->fa, s, (t->fa && t->fa->left == t));
}
void RotateLL(TreeNode* root)
{
TreeNode* c1 = root->left;
LinkReplace(c1, root);
LinkLeft(root, c1->right);
LinkRight(c1, root);
}
void RotateRR(TreeNode* root)
{
TreeNode* c1 = root->right;
LinkReplace(c1, root);
LinkRight(root, c1->left);
LinkLeft(c1, root);
}
void RotateLR(TreeNode* root)
{
TreeNode* c1 = root->left, * c2 = c1->right;
LinkLeft(root, c2);
LinkRight(c1, c2->left);
LinkLeft(c2, c1);
RotateLL(root);
}
void RotateRL(TreeNode* root)
{
TreeNode* c1 = root->right, * c2 = c1->left;
LinkRight(root, c2);
LinkLeft(c1, c2->right);
LinkRight(c2, c1);
RotateRR(root);
}
void Rotate(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
if (root->left == c1) {
if (c1->left == c2)RotateLL(root);
else RotateLR(root);
}
else {
if (c1->left == c2)RotateRL(root);
else RotateRR(root);
}
}
void Adjust(TreeNode* root, TreeNode* node)
{
if (!root || !node || root == node)return;
TreeNode* p = node->fa;
if (p == root)p->flag = BLACK;
if (p->flag == BLACK)return;
//到了这里，node就一定有祖父节点，而且父节点是红节点，所以一定有red-violation
TreeNode* pp = p->fa;
int dir = (p == pp->left);
TreeNode* unc = dir ? pp->right : pp->left;
if (unc && unc->flag == RED) {
pp->flag = RED, p->flag = BLACK, unc->flag = BLACK;
return Adjust(root, pp);
}
//到了这里，叔叔节点要么不存在，要么是黑节点
Rotate(pp, p, node);
pp->flag = RED, pp->fa->flag=BLACK;
}
void InsertNode(TreeNode*& root, TreeNode* node)
{
if (!root)root = node;
else InsertAndLink(root, node);
Adjust(root, node);
while (root->fa)root = root->fa;
}
void InsertNode(TreeNode*& root, int val)
{
TreeNode* p = find(root, val);
if(!is_multi_map && p)return;
p = new TreeNode();
p->val = val, p->flag = RED;
p->fa = NULL, p->left = NULL, p->right = NULL;
InsertNode(root, p);
}
TreeNode* GetMin(TreeNode* root)
{
if (!root)return root;
if (root->left)return GetMin(root->left);
return root;
}
void changeColor(TreeNode* a, TreeNode* b)
{
Flag flag = a->flag;
a->flag = b->flag, b->flag = flag;
}
void DeleteAdjust(TreeNode* node)
{
if (!node || !node->fa)return;
if (node->flag == RED) {
node->flag = BLACK;
return;
}
//到了这里，node节点是黑节点，而且不是根节点，那么它一定有父亲节点和兄弟节点
TreeNode* p = node->fa; //父亲
int dir = (node == p->left);
TreeNode* br = dir ? p->right : p->left; //兄弟
if (br->flag == RED) {
LinkReplace(br, p);
Link(p, dir ? br->left : br->right, !dir);
Link(br, p, dir);
p->flag = RED, br->flag = BLACK;
DeleteAdjust(node);
return;
}
//到了这里，node节点和兄弟节点都是黑节点
TreeNode* brleft = br->left, * brright = br->right;
if (brleft && brleft->flag == RED || brright && brright->flag == RED) {
if (dir) {
if (brleft && brleft->flag == RED) {
brleft->flag = p->flag, p->flag = BLACK;
RotateRL(p);
}
else {
changeColor(p, br);
brright->flag = BLACK;
RotateRR(p);
}
}
else {
if (brright && brright->flag == RED) {
brright->flag = p->flag, p->flag = BLACK;
RotateLR(p);
}
else {
changeColor(p, br);
brleft->flag = BLACK;
RotateLL(p);
}
}
}
else {
br->flag = RED;
DeleteAdjust(p);
}
}
void DeleteNode(TreeNode*& root, TreeNode* node)
{
if (node->left == NULL && node->right == NULL) {
DeleteAdjust(node);
LinkReplace(NULL, node);
while (root->fa)root = root->fa;
return;
}
TreeNode* p;
if (node->left == NULL)p = node->right;
else if (node->right == NULL)p = node->left;
else p = GetMin(node->right);
node->val = p->val;
DeleteNode(root, p);
while (root->fa)root = root->fa;
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int>v1;
if (root == NULL)return v1;
v1 = inorderTraversal(root->left);
v1.insert(v1.end(), root->val);
vector<int>v2 = inorderTraversal(root->right);
v1.insert(v1.end(), v2.begin(), v2.end());
return v1;
}
//输出一维vector
template<typename T>
void fcout(vector<T> v)
{
for (int i = 0; i < v.size(); i++)cout << v[i] << " ";
cout << endl;
}
int main()
{
TreeNode* root = NULL;
InsertNode(root, -10);
InsertNode(root, -3);
InsertNode(root, 0);
InsertNode(root, 5);
InsertNode(root, 9);
fcout(inorderTraversal(root));
DeleteNode(root,find(root, -3));
fcout(inorderTraversal(root));
DeleteNode(root,find(root, 0));
fcout(inorderTraversal(root));
return 0;
}运行结果：
-10 -3 0 5 9
-10 0 5 9
-10 5 9
七，map、multi_map
完整代码中有一个宏is_multi_map
is_multi_map为true表示整体是multi_map，即允许重复元素
is_multi_map为false表示整体是map，即不允许重复元素。
八，OJ实战
力扣 1902. 给定二叉搜索树的插入顺序求深度
给定一个从 0 开始索引的整数类型数组 order ，其长度为 n，是从 1 到 n 的所有整数的一个排列，表示插入到一棵二叉搜索树的顺序。
二叉搜索树的定义如下：
- 一个节点的左子树只包含键值小于该节点键值的节点。
- 一个节点的右子树只包含键值大于该节点键值的节点。
- 左子树和右子树须均为二叉搜索树。
该二叉搜索树的构造方式如下：
order[0]将成为该二叉搜索树的根。- 所有后续的元素均在维持二叉搜索树性质的前提下作为任何已存在节点的子节点插入。
返回该二叉搜索树的深度。
一棵二叉树的深度是从根节点到最远叶节点的最长路径所经节点的个数。
示例 1:
输入: order = [2,1,4,3] 输出: 3 解释: 该二叉搜索树的深度为 3，路径为 2->4->3。
示例 2:
输入: order = [2,1,3,4] 输出: 3 解释: 该二叉搜索树的深度为 3，路径为 2->3->4。
示例 3:
输入: order = [1,2,3,4] 输出: 4 解释: 该二叉搜索树的深度为 4，路径为 1->2->3->4。
提示：
n == order.length1 <= n <= 105order是从1到n的整数的一个排列。
思路：
题目已经定死了二叉搜索树的建立方式，这个方式是最简单最自然的。
如果用模拟的方式，二叉搜索树的时间复杂度是O（n^2），就会超时。
实际上，我们只需要知道对于每个数，在他前面的所有数中离他最近的2个数（一个大一个小）是哪两个即可，不需要真的去建树。
那么，如何知道在他前面的所有数中离他最近的2个数是哪两个呢？一种思路是用平衡二叉树即可，不过我自己实现的平衡二叉树时间复杂度没到标准时间复杂度，但是我自己实现的红黑树时间复杂度是可以的，所以我就把上面的红黑树的接口调了一下。
class Solution {
public:
int maxDepthBST(vector<int>& order) {
Treenode* r = NULL;
map<int, int>deep;
int ans = 0;
for (auto k : order) {
auto p = findSmall(r, k), q = findBig(r, k);
int pv = p ? p->val : -1, qv = q ? q->val : -1;
ans = max(ans, deep[k] = max(deep[pv], deep[qv]) + 1);
InsertNode(r, k);
}
return ans;
}
};
扫一扫
3931
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
