数据结构：红黑树的原理和实现"/>
数据结构：红黑树的原理和实现
文章目录
- 红黑树的概念
- 红黑树的性质
- 红黑树的模拟实现
- 红黑树的平衡问题
- 整体实现和测试
本篇用于进行红黑树的拆解和模拟实现，为之后的map和set的封装奠定基础
红黑树的概念
红黑树也是一种二叉搜索树，但是在每一个节点的内部新增了一个用以表示该节点颜色的值，有黑色和红色两种，通过对任何一条从根到叶子的路径上的各个节点着色方式的限制，红黑树可以保证没有一条路径可以比其他路径长出两倍，因此是平衡的
红黑树的基本模式如下图所示
红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
为什么红黑树具有最长路径中节点的个数不超过最短路径个数的2倍？
其实原因在于红黑树的性质，在红黑树中可以存在两个相同黑色节点连在一起，但是绝对不会存在两个连在一起的红色节点，并且每个路径上的黑色节点数量是相同的，基于这两点原因，在红黑树中最长的路径不过是一个红节点穿插一个黑节点…而最短的路径就是所有黑节点是一个接着一个，基于这样的原因就可以保证上面的性质了
红黑树的模拟实现
基本的定义
enum Color
{RED,BLEAK
};template<class K, class V>
struct BSTreeNode
{BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;BSTreeNode<K, V>* _parent;pair<K, V> _kv;Color _col;BSTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};
为什么这里在定义信息的时候，默认值使用的是RED？
由于红黑树的性质可以知道，一条路径中的黑节点的数量是确定的，当插入的是一个红色节点时，最多会影响的是当前路径的信息，但是如果插入的是一个黑色节点，那么势必会引起整个树中所有完整的路径中的异常，会破坏红黑树中的平衡
红黑树的平衡问题
在插入新节点后，红黑树的平衡可能会受到破坏，下面分情况来进行讨论
定义：当前节点为cur，父亲节点为parent，祖父节点为grandparent，叔叔节点为uncle，而红黑树的插入问题重点看叔叔
1. 如果双亲节点是黑色
最简单的一种情况，不需要做任何处理，只需要插入即可
2. cur为红色，parent为红色，grandfather为黑色，uncle存在并且是红色
此时，出现了两个红色节点相继出现的情况，这种情况是不被允许的，因此要做出调整：把parent和uncle都改成黑色，同时将grandfather改成红色
此时需要继续进行情况讨论，如果grandfather是根节点，那么就意味着此时调整已经完毕了，不需要再进行调整，因此把根节点置为黑色，而如果grandfather不为根节点，并且上面一个节点还是红色，那么此时又有两个红色节点相继出现了，此时就需要继续进行调整，把grandfather当成cur，然后进行调整即可
3. cur为红色，parent为红色，grandfather为黑色，uncle不存在或者是黑色
根据uncle的情况来进行分析：
- 如果uncle节点不存在，那么就说明cur一定是新插入的节点，这是因为路径下的黑色节点必定要相同，此时又有两种情况，可能插入在parent的左右两边
- 如果uncle节点存在，并且是黑色，那么就意味着cur节点一定是黑的，现在体现为红色是因为cur子树在调整的过程中把cur的节点变成红色了，如果cur是新插入节点，那么红黑树原来就是错的，因为下面的场景不存在
所以一定是这样的情景：
而此时cur并不是新插入的节点，新插入节点是cur的左右子树中的一个，现在体现为红色是因为下面子树的调整把cur变成红色了，它原来是黑色的
那么此时就要进行旋转了：令grandparent右旋即可完成降高度的效果，再进行变色即可
因此将上述的过程都综合起来，就可以完成代码的实现了
bool insert(const pair<K, V>& kv){Node* cur = _root;Node* parent = nullptr;// 根据搜索二叉树的基本逻辑完成if (_root == nullptr){_root = new Node(kv);}else{// 插入数据while (cur){if (cur->_kv.second > kv.second){// 插入元素小于当前节点元素，插入到左边parent = cur;cur = cur->_left;}else if (cur->_kv.second < kv.second){// 插入元素大于当前节点元素，插入到右边parent = cur;cur = cur->_right;}else{return false;}}// 此时parent指向最后一个节点，cur为空cur = new Node(kv);if (parent->_kv.second > cur->_kv.second){// 如果插入节点小于它的父亲，就插入到左边parent->_left = cur;cur->_parent = parent;}else if (parent->_kv.second < cur->_kv.second){// 如果插入节点大于它的父亲，就插入到右边parent->_right = cur;cur->_parent = parent;}else{return false;}}// 至此，普通二叉搜索树的插入已经完成，该进行红黑树的高度调整了// 终止条件是parent为空，或者parent已经是黑色了，就意味着不需要调整了// parent是红色，意味着grandparent一定存在while (parent && parent->_col == RED){// 更变的核心是舅舅，因此要先找到舅舅// 整体来说还有两种情况，parent可能是grandparent的左或者右，舅舅就是另外一边Node* grandparent = parent->_parent;if (parent == grandparent->_left){Node* uncle = grandparent->_right;// 1. 舅舅存在，并且是红色if (uncle && uncle->_col == RED){// g// p u// c// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 向上处理cur = grandparent;parent = cur->_parent;}// 2. 舅舅不存在else{// 如果cur是左孩子if (cur == parent->_left){// g// p// c// 对grandparent进行右旋RotateR(grandparent);// 变色cur->_col = grandparent->_col = RED;parent->_col = BLACK;}// 如果cur是右孩子else{// g g// p --> c --> c// c p p g// 对parent左旋，对grandparent右旋RotateL(parent);RotateR(grandparent);// 变色cur->_col = BLACK;parent->_col = grandparent->_col = RED;}// 更新之后parent和grandparent顺序乱了，而且也不需要继续调整了，直接breakbreak;}}// parent是grandparent的右孩子，相同的逻辑再进行一次else{Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 继续往上处理cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right){// g// p// cRotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{// g// p // cRotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}// 不管上面怎么变都无所谓，只需要保证根节点是黑的就可以了_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}
整体实现和测试
enum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Color _col;
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree():_root(nullptr){}bool insert(const pair<K, V>& kv){Node* cur = _root;Node* parent = nullptr;// 根据搜索二叉树的基本逻辑完成if (_root == nullptr){_root = new Node(kv);}else{// 插入数据while (cur){if (cur->_kv.second > kv.second){// 插入元素小于当前节点元素，插入到左边parent = cur;cur = cur->_left;}else if (cur->_kv.second < kv.second){// 插入元素大于当前节点元素，插入到右边parent = cur;cur = cur->_right;}else{return false;}}// 此时parent指向最后一个节点，cur为空cur = new Node(kv);if (parent->_kv.second > cur->_kv.second){// 如果插入节点小于它的父亲，就插入到左边parent->_left = cur;cur->_parent = parent;}else if (parent->_kv.second < cur->_kv.second){// 如果插入节点大于它的父亲，就插入到右边parent->_right = cur;cur->_parent = parent;}else{return false;}}// 至此，普通二叉搜索树的插入已经完成，该进行红黑树的高度调整了// 终止条件是parent为空，或者parent已经是黑色了，就意味着不需要调整了// parent是红色，意味着grandparent一定存在while (parent && parent->_col == RED){// 更变的核心是舅舅，因此要先找到舅舅// 整体来说还有两种情况，parent可能是grandparent的左或者右，舅舅就是另外一边Node* grandparent = parent->_parent;if (parent == grandparent->_left){Node* uncle = grandparent->_right;// 1. 舅舅存在，并且是红色if (uncle && uncle->_col == RED){// g// p u// c// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 向上处理cur = grandparent;parent = cur->_parent;}// 2. 舅舅不存在else{// 如果cur是左孩子if (cur == parent->_left){// g// p// c// 对grandparent进行右旋RotateR(grandparent);// 变色cur->_col = grandparent->_col = RED;parent->_col = BLACK;}// 如果cur是右孩子else{// g g// p --> c --> c// c p p g// 对parent左旋，对grandparent右旋RotateL(parent);RotateR(grandparent);// 变色cur->_col = BLACK;parent->_col = grandparent->_col = RED;}// 更新之后parent和grandparent顺序乱了，而且也不需要继续调整了，直接breakbreak;}}// parent是grandparent的右孩子，相同的逻辑再进行一次else{Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 继续往上处理cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right){// g// p// cRotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{// g// p // cRotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}// 不管上面怎么变都无所谓，只需要保证根节点是黑的就可以了_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}void inorder(){_inorder(_root);cout << endl;}bool isbalance(){return _isbalance(_root);}private:bool _check(Node* root, int blacknum, const int RefVal){// 判断黑色路径数量是否相等if (root == nullptr){if (blacknum != RefVal){cout << "黑色节点数量不相等" << endl;return false;}return true;}// 判断是否有连续的红色节点if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col == BLACK){blacknum++;}return _check(root->_left, blacknum, RefVal)&& _check(root->_right, blacknum, RefVal);}// 判断红黑树是否平衡bool _isbalance(Node* root){// 如果根节点是红的，说明错了if (root->_col == RED){cout << "根节点是红色" << endl;return false;}// 统计一下路径中有多少黑色节点int RefVal = 0;Node* cur = root;while (cur){if (cur->_col == BLACK)RefVal++;cur = cur->_left;}// 判断路径中的黑色节点是否相等return _check(root, 0, RefVal);}void _inorder(Node* root){if (root == nullptr)return;_inorder(root->_left);cout << root->_kv.second << " ";_inorder(root->_right);}Node* _root = nullptr;
};
int main()
{const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}RBTree<int, int> t;for (auto e : v){cout << "Insert:" << e << "->";t.insert(make_pair(e, e));cout << t.isbalance() << endl;}cout << t.isbalance() << endl;return 0;
}
更多推荐
数据结构：红黑树的原理和实现
发布评论