网站导航
> 技术文档 > 玩转红黑树：算法背后的平衡与旋转技巧_红黑树旋转

玩转红黑树：算法背后的平衡与旋转技巧_红黑树旋转

网友: 技术文档 2025-07-30 12:55:56

文章目录

  • 红黑树的规则
  • 红黑树的存储结构
  • 红黑树插入一个值的大概过程以及代码实现
  • 红黑树的调整（旋转部分）
  • 红黑树的调整（颜色部分）
  • 红黑树的插入代码实现
  • 红⿊树的查找
  • 检查红黑树是否平衡

前言：红黑树也是一种旋转树，所以本质也是一颗二叉搜索树，红黑树（Red-Black Tree）是一种自平衡的二叉查找树（BST），它通过一组额外的规则确保树的平衡性，从而保证了在最坏情况下的查找、插入和删除操作的时间复杂度为 O(logn)。

红黑树的规则

  1. 节点颜色：每个节点要么是红色的，要么是黑色的。
  2. 根节点是黑色：树的根节点必须是黑色的。
  3. 红色节点的父节点是黑色的：不能有两个连续的红色节点（即红色节点不能相邻）。
  4. 每个叶子节点（NIL节点）是黑色的：虽然叶子节点没有存储数据，但在树的表示中，它们被视为黑色节点。
    (这个规则来源于《算法导论》等书籍上——每一个叶子结点（NIL）都是黑色的)
    在红黑树（Red-Black Tree）中，NIL节点指的是一种虚拟的“空”节点，它是树中的叶子节点。尽管这些节点本身并不存储数据，它们在红黑树的实现中非常重要，主要用来简化树的结构和算法。
  5. 从任何节点到其每个叶子节点的路径上，必须包含相同数量的黑色节点：这一规则确保了从根到叶子路径的平衡性。
  6. 插入时的修正操作：在插入新节点时，可能会破坏红黑树的性质，需要通过旋转和颜色变化来修复树。

红黑树的存储结构

红黑树的结构主要由 节点 和 树的关系 组成。每个节点包含了数据（键值对）、左右子节点指针、父节点指针和颜色。树通过这些指针将节点连接起来，形成一个具有平衡性质的二叉查找树。

  • 树的基本结构：每个节点都连接着左右子节点和父节点，确保树可以通过这些指针进行遍历、插入和删除操作。
  • 颜色：每个节点的颜色（红色或黑色）用于保证红黑树的平衡性。根据红黑树的性质，树的高度限制和搜索效率可以保持在O(logn) 时间复杂度。
// 枚举值表⽰颜⾊ enum Colour{ RED, BLACK};// 这⾥我们默认按key/value结构实现 template<class K, class V>struct RBTreeNode{ // 这⾥更新控制平衡也要加⼊parent指针  pair<K, V> _kv; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Colour _col; RBTreeNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) {}};template<class K, class V>class RBTree{ typedef RBTreeNode<K, V> Node;public:private: Node* _root = nullptr;};

红黑树插入一个值的大概过程以及代码实现

说明：下图中假设我们把新增结点标识为c(cur)，c的⽗亲标识为p(parent)，p的⽗亲标识为g(grandfather)，p的兄弟标识为u（uncle）。

  1. 插入新节点：按照普通二叉查找树（BST）的方式插入新节点。新节点总是被插入为红色的，以便于稍后进行修复操作。

  2. 修复红黑树性质：插入新节点后，可能会违反红黑树的某些性质，特别是：
    可能会违反“两个红色节点不能相邻”这一规则。
    可能会导致根节点不是黑色的。

bool Insert(const 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 (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//...进行旋转、调整等操作

为了修复这些问题，需要进行颜色调整和树的旋转操作。

红黑树的调整（旋转部分）

红黑树的旋转，底层也是跟AVL树一样，有着右旋、左旋、左右旋、右左旋。不过旋转的次数相对更加少了，

  • 右旋：
void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}
  • 左旋：
void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}

红黑树的调整（颜色部分）

  • 情况1只变⾊，不旋转。（u存在且为红）

c为红，p为红，g为⿊，u存在且为红，则将p和u变⿊，g变红。在把g当做新的c，继续往上更新。
玩转红黑树：算法背后的平衡与旋转技巧_红黑树旋转

分析：因为p和u都是红⾊，g是⿊⾊，把p和u变⿊，左边⼦树路径各增加⼀个⿊⾊结点，g再变红，相当于保持g所在⼦树的⿊⾊结点的数量不变，同时解决了c和p连续红⾊结点的问题，需要继续往上更新是因为，g是红⾊，如果g的⽗亲还是红⾊，那么就还需要继续处理；
如果g的⽗亲是⿊⾊，则处理结束了；
如果g就是整棵树的根，再把g变回⿊⾊。

  • 情况2，单旋 + 变色。（ u不存在或者u存在且为黑）
    c为红，p为红，g为⿊，u不存在或者u存在且为⿊。
    u不存在，则c⼀定是新增结点。
    u存在且为⿊，则c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，符合情况1，变⾊将c从⿊⾊变成红⾊，更新上来的。
    玩转红黑树：算法背后的平衡与旋转技巧_红黑树旋转
    分析：p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解决问题，需要旋转+变⾊。

如果p是g的左，c是p的左，那么以g为旋转点进⾏右单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

如果p是g的右，c是p的右，那么以g为旋转点进⾏左单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

情况3:，双旋+变色 （u不存在或者u存在且为⿊）
c为红，p为红，g为⿊，u不存在或者u存在且为⿊。
u不存在，则c⼀定是新增结点。
u存在且为⿊，则c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，符合情况1，变⾊将c从⿊⾊变成红⾊，更新上来的。
玩转红黑树：算法背后的平衡与旋转技巧_红黑树旋转
分析：p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解
决问题，需要旋转+变⾊。

如果p是g的左，c是p的右，那么先以p为旋转点进⾏左单旋，再以g为旋转点进⾏右单旋，再把c变⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

如果p是g的右，c是p的左，那么先以p为旋转点进⾏右单旋，再以g为旋转点进⾏左单旋，再把c变⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

红黑树的插入代码实现

template<class K, class V>class RBTree{typedef RBTreeNode<K, V> Node;public:bool Insert(const 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 (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){// g// p u//Node* uncle = grandfather->_right;// uncle存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // uncle不存在，或者存在且为黑{if (cur == parent->_left){// 旋转+变色// g// p u//cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// 旋转+变色// g// p u// cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{// g// u pNode* uncle = grandfather->_left;// 叔叔存在且为红，-》变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色// g// u p// cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

红⿊树的查找

按⼆叉搜索树逻辑实现即可，搜索效率为 O(logN)

Node* Find(const K& key){ Node* cur = _root; while (cur) { if (cur->_kv.first < key) { cur = cur->_right; } else if (cur->_kv.first > key) { cur = cur->_left; } else { return cur; } } return nullptr;}

检查红黑树是否平衡

这⾥获取最⻓路径和最短路径，检查最⻓路径不超过最短路径的2倍是不可⾏的，因为就算满⾜这个条件，红⿊树也可能颜⾊不满⾜规则，当前暂时没出问题，后续继续插⼊还是会出问题的。所以我们还是去检查4点规则，满⾜这4点规则，⼀定能保证最⻓路径不超过最短路径的2倍。

  1. 规则1枚举颜⾊类型，天然实现保证了颜⾊不是⿊⾊就是红⾊。
  2. 规则2直接检查根即可
  3. 规则3前序遍历检查，遇到红⾊结点查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲的颜⾊就⽅便多了。
  4. 规则4前序遍历，遍历过程中⽤形参记录跟到当前结点的blackNum(⿊⾊结点数量)，前序遍历遇到⿊⾊结点就++blackNum，⾛到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊结点数量作为参考值，依次⽐较即可。
bool Check(Node* root, int blackNum, const int refNum){ if (root == nullptr) { // 前序遍历⾛到空时，意味着⼀条路径⾛完了  //cout << blackNum << endl; if (refNum != blackNum) { cout << \"存在⿊⾊结点的数量不相等的路径\" << endl; return false; } return true; } // 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了  if (root->_col == RED && root->_parent->_col == RED) { cout << root->_kv.first << \"存在连续的红⾊结点\" << endl; return false; } if (root->_col == BLACK) { blackNum++; } return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);}bool IsBalance(){ if (_root == nullptr) return true; if (_root->_col == RED) return false; // 参考值  int refNum = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { ++refNum; } cur = cur->_left; } return Check(_root, 0, refNum);}
网络标签：

相关问题