文章目录
- 十七、红黑树
- 1.红黑树的概念
- 红黑树的性质
- 2.红黑树节点的定义
- 3.红黑树的插入
- 4.红黑树的验证
- 5.完整代码+结果演示
- 6.红黑树与AVL树的比较
- 未完待续
十七、红黑树
1.红黑树的概念
红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
红黑树的性质
- 每个结点不是红色就是黑色。
- 根节点是黑色的。
- 如果一个节点是红色的,则它的两个孩子结点是黑色的。(即不存在连续的两个红色节点)
- 对于每个结点,从该结点到其所有后代叶结点的路径上,均包含相同数目的黑色结点。(即每条路径具有相同数量的黑色节点)
- 每个叶子结点都是黑色的(此处的叶子结点指的是 空结点 )。 空节点!!
由以上性质可知:如果存在,红黑树的最短路径是全黑色节点;最长路径则是一个黑色节点一个红色节点交替,所以 红黑树才能确保没有一条路径会比其他路径长出俩倍 。
2.红黑树节点的定义
红黑树节点的定义与AVL树及其相似,唯二的区别就是,红黑树没有平衡因子,红黑树有颜色值。
// 枚举颜色
enum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair<K, V> _kv;// 颜色Color _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};
为什么我们构造函数将颜色值默认设置成红色?因为我们创建的节点有两个孩子,两个孩子都是空节点,都是黑色的,如果创建的节点不把原本的这个位置的黑色空节点给替换掉,那么这条路径就会比其他路径多出一个黑色,违反了红黑树的性质。因此,新创建的节点一定是红色的。
3.红黑树的插入
先打个预防针:光靠区分节点颜色无法保证红黑树的结构,红黑树的插入在特殊情况同样需要 AVL树的旋转 操作。
红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:
Ⅰ:按照二叉搜索的树规则插入新节点。 这步就不再多说,应该都比较熟悉。
bool Insert(const std::pair<K, V>& kv)
{// 空树则创建根节点if (_root == nullptr){_root = new Node(kv);// 红黑树的根节点是黑色的_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;// 找到新节点应该插入的位置while (cur){// 比父节点小, 往左子树找if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}// 比父节点大, 往右子树找else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{// 已经存在该值, 插入失败return false;}}cur = new Node(kv);// 父节点指向新节点if (kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;// 新节点指向父节点cur->_parent = parent;// ------begin------//// 修正结构和颜色//// ------end------// 保证根节点是黑色的_root->_col = BLACK;// 插入成功return true;
}
Ⅱ:检测新节点插入后,红黑树的性质是否造到破坏 。这一步非常重要,算是红黑树的精华所在。红黑树中,我们需要关注叔叔节点(父亲的兄弟)。红黑树的情况复杂,因此我们要对出现的情况进行分类讨论:
约定:cur为当前节点,p为父节点,g为爷爷节点,u为叔叔节点
①cur为红,p为红,g为黑,u存在且为红。由于新插入的节点必定是红色,但是p父节点也是红色,违反了不能出现连续红色的性质,所以我们需要进行修正颜色。由于刚好u叔叔节点是红色,所以最简单的方法就是 将g爷爷节点的黑色平分到它的两个孩子,p节点和u节点, 然后g节点变红即可 。
需要注意的是:由于g节点变成了红色,可能它与它的父节点违反了规则,所以我们需要循环向上判断,直到根节点。
② cur为红,p为红,g为黑,u不存在/u存在且为黑。
说明:u的情况有两种
1.如果u节点不存在,则cur一定是新插入节点,因为如果cur不是新插入节点,那么前面肯定符合红黑树,则则cur和p一定有一个节点的颜色是黑色,此时u若不存在,则两条路径黑色数量不一致,就不满足红黑树的性质,所以u不存在,则cur一定是新插入的节点。
2.如果u节点存在,且为黑色时(红色已在①中讨论),如果cur是新插入节点,则说明原本的树就不符合红黑树性质,所以cur不是新插入的节点。
此时我们可以借助AVL树的旋转来调整结构,然后修改颜色即可。
调整结构:p为g的左孩子,cur为p的左孩子,则进行右单旋转;相反,p为g的右孩子,cur为p的右孩子,则进行左单旋转;
变色:p、g变色 —> p变黑,g变红
③cur为红,p为红,g为黑,u不存在/u存在且为黑。有人会说,这不跟情况②一样吗?并不是,情况②是p和cur在同侧,与u相反,而这里,p和cur并不在同侧,cur的位置偏向u,朝内的。
这个时候怎么办呢?当然还是借助AVL树的思想,我可以在这里进行双旋。先旋转一次,让cur朝向外侧,就变成了情况②,然后再旋转一次即可。
旋转调整结构:p为g的左孩子,cur为p的右孩子,则针对p做左单旋转;相反,p为g的右孩子,cur为p的左孩子,则针对p做右单旋转。
综上所述:我们只需要记住:
叔叔节点存在并且是红色, 则不需要旋转,将爷爷节点的黑色分给父亲和叔叔,爷爷变红即可(需要向上调整)。
叔叔节点不存在或是黑色, 则需要旋转。cur节点朝外就是单旋,朝内就是双旋(旋转后是不需要再向上调整的),然后进行变色处理。
最后可能会将根节点染成红色,插入结束的时候特判一下即可。
修正结构和颜色的代码:
// 修正结构和颜色
// 父亲存在且是红色
while (parent && parent->_col == RED)
{// 爷爷节点Node* grandfather = parent->_parent;// 父亲是爷爷的左if (parent == grandfather->_left){// 叔叔节点Node* uncle = grandfather->_right;// 叔叔节点存在且为红色if (uncle && uncle->_col == RED){// 父节点变黑, 叔叔节点变黑, 爷爷节点变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上修正cur = grandfather;parent = cur->_parent;}// 叔叔节点不存在或为黑色else{// 左左if (cur == parent->_left){// 右单旋 + 修正颜色RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 左右else{// 左单旋父节点RotateL(parent);// 右单旋爷爷节点RotateR(grandfather);// 修正颜色cur->_col = BLACK;grandfather->_col = RED;}// 旋转后退出break;}}// 父亲是爷爷的右else{// 叔叔节点Node* uncle = grandfather->_left;// 叔叔节点存在且为红色if (uncle && uncle->_col == RED){// 父节点变黑, 叔叔节点变黑, 爷爷节点变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上修正cur = grandfather;parent = cur->_parent;}// 叔叔节点不存在或为黑色else{// 右右if (cur == parent->_right){// 左单旋 + 修正颜色RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 右左else{// 右单旋父节点RotateR(parent);// 左单旋爷爷节点RotateL(grandfather);// 修正颜色cur->_col = BLACK;grandfather->_col = RED;}// 旋转后退出break;}}
}
旋转代码:
// 左左 --- 右单旋
void RotateR(Node* parent)
{// 父节点的左孩子Node* subL = parent->_left;// 父节点的左孩子的右孩子Node* subLR = subL->_right;// 父节点的父节点Node* ppnode = parent->_parent;// 修改父节点的指向parent->_left = subLR;parent->_parent = subL;// 修改父节点的左孩子的指向subL->_right = parent;subL->_parent = ppnode;// 如果父节点的左孩子的右孩子存在,则修改其指向if (subLR)subLR->_parent = parent;// 修改父节点的父节点的指向if (parent == _root)_root = subL;else if (parent == ppnode->_left)ppnode->_left = subL;elseppnode->_right = subL;
}// 右右 --- 左单旋
void RotateL(Node* parent)
{// 父节点的右孩子Node* subR = parent->_right;// 父节点的右孩子的左孩子Node* subRL = subR->_left;// 父节点的父节点Node* ppnode = parent->_parent;// 修改父节点的指向parent->_right = subRL;parent->_parent = subR;// 修改父节点的右孩子的指向subR->_left = parent;subR->_parent = ppnode;// 如果父节点的右孩子的左孩子存在,则修改其指向if (subRL)subRL->_parent = parent;// 修改父节点的父节点的指向if (parent == _root)_root = subR;else if (parent == ppnode->_left)ppnode->_left = subR;elseppnode->_right = subR;
}
4.红黑树的验证
我们可以根据红黑树的性质来验证我们写的红黑树代码是否有问题。红黑树的性质主要只有三个:①根节点是黑色。②没有连续的红节点。③每条路径上的黑色节点数量相同。
判断根节点颜色和找出最左侧路径的黑色节点个数:
bool IsRBT()
{// 判断根节点是否是黑色if (_root && _root->_col == RED)return false;// 计算最左路径的黑色节点数量int refBlackNum = 0;Node* cur = _root;while (cur){if(cur->_col == BLACK)refBlackNum++;cur = cur->_left;}// 检查红黑树的性质return Check(_root, 0, refBlackNum);
}
所有路径的黑色节点数量与最左侧路径比较,顺便找连续的两个红色节点:
// 检查红黑树的性质
bool Check(Node* cur, int blackNum, int refBlackNum)
{if (cur == nullptr){// 存在某条路径上黑色节点数量与最左路径的黑色节点数量不相等if (refBlackNum != blackNum){std::cout << "黑色节点的数量不相等" << std::endl;return false;}return true;}// 存在连续的红色节点if (cur->_col == RED && cur->_parent->_col == RED){std::cout << cur->_kv.first << "存在连续的红色节点" << std::endl;return false;}// 该路径黑色节点数量+1if (cur->_col == BLACK)++blackNum;// 递归子树return Check(cur->_left, blackNum, refBlackNum)&& Check(cur->_right, blackNum, refBlackNum);
}
中序遍历:
void _InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);std::cout << root->_kv.first << std::endl;_InOrder(root->_right);
}void InOrder()
{_InOrder(_root);
}
5.完整代码+结果演示
RBTree.h:
#pragma once#include <iostream>
// 枚举颜色
enum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;std::pair<K, V> _kv;// 颜色Color _col;RBTreeNode(const std::pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const std::pair<K, V>& kv){// 空树则创建根节点if (_root == nullptr){_root = new Node(kv);// 红黑树的根节点是黑色的_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;// 找到新节点应该插入的位置while (cur){// 比父节点小, 往左子树找if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}// 比父节点大, 往右子树找else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{// 已经存在该值, 插入失败return false;}}cur = new Node(kv);// 父节点指向新节点if (kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;// 新节点指向父节点cur->_parent = parent;// 修正祖先的颜色while (parent && parent->_col == RED){// 爷爷节点Node* grandfather = parent->_parent;if (parent == grandfather->_left){// 叔叔节点Node* uncle = grandfather->_right;// 叔叔节点存在且为红色if (uncle && uncle->_col == RED){// 父节点变黑, 叔叔节点变黑, 爷爷节点变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上修正cur = grandfather;parent = cur->_parent;}// 叔叔节点不存在或为黑色else{// 左左if (cur == parent->_left){// 右单旋 + 修正颜色RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 左右else{// 左单旋父节点RotateL(parent);// 右单旋爷爷节点RotateR(grandfather);// 修正颜色cur->_col = BLACK;grandfather->_col = RED;}break;}}else{// 叔叔节点Node* uncle = grandfather->_left;// 叔叔节点存在且为红色if (uncle && uncle->_col == RED){// 父节点变黑, 叔叔节点变黑, 爷爷节点变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上修正cur = grandfather;parent = cur->_parent;}// 叔叔节点不存在或为黑色else{// 右右if (cur == parent->_right){// 左单旋 + 修正颜色RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 右左else{// 右单旋父节点RotateR(parent);// 左单旋爷爷节点RotateL(grandfather);// 修正颜色cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 保证根节点是黑色的_root->_col = BLACK;// 插入成功return true;}// 左左 --- 右单旋void RotateR(Node* parent){// 父节点的左孩子Node* subL = parent->_left;// 父节点的左孩子的右孩子Node* subLR = subL->_right;// 父节点的父节点Node* ppnode = parent->_parent;// 修改父节点的指向parent->_left = subLR;parent->_parent = subL;// 修改父节点的左孩子的指向subL->_right = parent;subL->_parent = ppnode;// 如果父节点的左孩子的右孩子存在,则修改其指向if (subLR)subLR->_parent = parent;// 修改父节点的父节点的指向if (parent == _root)_root = subL;else if (parent == ppnode->_left)ppnode->_left = subL;elseppnode->_right = subL;}// 右右 --- 左单旋void RotateL(Node* parent){// 父节点的右孩子Node* subR = parent->_right;// 父节点的右孩子的左孩子Node* subRL = subR->_left;// 父节点的父节点Node* ppnode = parent->_parent;// 修改父节点的指向parent->_right = subRL;parent->_parent = subR;// 修改父节点的右孩子的指向subR->_left = parent;subR->_parent = ppnode;// 如果父节点的右孩子的左孩子存在,则修改其指向if (subRL)subRL->_parent = parent;// 修改父节点的父节点的指向if (parent == _root)_root = subR;else if (parent == ppnode->_left)ppnode->_left = subR;elseppnode->_right = subR;}// 中序遍历void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);std::cout << root->_kv.first << std::endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);}// 检查红黑树的性质bool Check(Node* cur, int blackNum, int refBlackNum){if (cur == nullptr){// 存在某条路径上黑色节点数量与最左路径的黑色节点数量不相等if (refBlackNum != blackNum){std::cout << "黑色节点的数量不相等" << std::endl;return false;}return true;}// 存在连续的红色节点if (cur->_col == RED && cur->_parent->_col == RED){std::cout << cur->_kv.first << "存在连续的红色节点" << std::endl;return false;}// 该路径黑色节点数量+1if (cur->_col == BLACK)++blackNum;// 递归子树return Check(cur->_left, blackNum, refBlackNum)&& Check(cur->_right, blackNum, refBlackNum);}bool IsRBT(){// 判断根节点是否是黑色if (_root && _root->_col == RED)return false;// 计算最左路径的黑色节点数量int refBlackNum = 0;Node* cur = _root;while (cur){if(cur->_col == BLACK)refBlackNum++;cur = cur->_left;}// 检查红黑树的性质return Check(_root, 0, refBlackNum);}
private:Node* _root = nullptr;
};void TestRBTree1()
{//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTree<int, int> t;for (auto e : a){t.Insert(std::make_pair(e, e));}t.InOrder();std::cout << t.IsRBT() << std::endl;
}
test.cpp:
#include "RBTree.h"
#include <iostream>int main()
{TestRBTree1();return 0;
}
结果演示:
6.红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N),红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数,所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红黑树更多。总而言之:红黑树插入效率更高,AVL树查找效率更高。