当前位置：首页 > news >正文

源码刨析与插入实现：RBT比AVL强在何处？

news 2025/4/2 6:42:13

0.写在前面

1.红黑树介绍及性质

Introduction：

properties：

2.红黑树的模拟实现

Step 1：RBTree结点的构造

Step 2：构造RBTree类

Step 3: 完成插入函数

Case 1：uncle存在且为红

Case 2：uncle不在或为黑

Step 4: 刨析旋转

左单旋：

右单旋：

Step 5：检查AVL树

IsBalance：

Height：

CheckColour：

3.AVL与红黑树的比较

1. 平衡性质

2. 插入和删除操作的效率

3. 查找操作的效率

4. 空间开销

0.写在前面

AVL树是数据结构中久负盛名的平衡二叉搜索二叉树，前面已经介绍了BInary Search Tree二叉搜索树以及AVL树插入旋转的实现，今天来介绍一下比AVL树性能更加强悍的红黑树（Red-Black Tree）如果没听过这棵树的读者可以了解一下背景：

1.红黑树介绍及性质

Introduction：

红黑树（Red-Black Tree），是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

properties：

（1 每个结点不是红色就是黑色
（2 根节点一定是黑色的
（3 如果一个节点是红色的，则它的两个孩子结点是黑色的
（4 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 （这里的路径指的是从当前结点开始一直到NIL结点，也就是叶子结点结束）
（5 每个叶子结点都是黑色的 (此处的叶子结点指的是空结点)

2.红黑树的模拟实现

由于红黑树的插入和删除都涉及到大量复杂的旋转，由于篇幅有限，本篇重点介绍的是红黑树的插入以及检验是否构成红黑树的部分内容。

Step 1：RBTree结点的构造

思路：

---1--- 先来想想如何存储结点，如果我们使用堆那样的数组是否合适？当然不合适，因为涉及到下标访问的问题，那么还剩下链式结构可以供我们选择了。

---2--- 构造RBTreeNode当然是要方便类外直接进行访问的，因此用struct来构造，来想想一个结点要存储什么？

---3--- 在结点中存储left地址，right地址，还有parent地址，这是典型的三叉链表的特征，以及当前结点的pair，pair可以是多种类型的，因此需要进行泛型编程，运用模板template，这里也可以只储存Key，我们干脆麻烦一点，储存键值对，pair<Key,Value>。

---4--- 先来解决一下结点的颜色问题，如何表示才显得简洁直观而且不容易出错呢？这里枚举enum的优势就体现出来了，用RED和BLACK可以直接表示颜色并且可以方便进行后续修改。

---5--- 最后要写一个构造函数，因为在创造结点的时候可能会用到，记得将left，right置为nullptr，默认将插入的结点颜色设置为RED，这么做的原因是如果设置为BLACK，那么有很大概率会影响路径上的黑色结点个数，从而打破性质4，那么设置为RED是最佳的选择！

enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};

Step 2：构造RBTree类

思路：

---1--- 为了表示RBTreeNode方便一些，在类中typedef一下以便我们来表示。

---2--- 这里的成员变量只需要_root就足够了，存储根结点

---3--- 下面给出RBTree类的大致框架:


template<class K, class V>
class RBTree
{
public:typedef RBTreeNode<K, V> Node;RBTree():_root(nullptr){}/...
private:Node* _root;
};

Step 3: 完成插入函数

思路：

---1--- 简单来说，前面的步骤与BST二叉搜索树的插入步骤大相径庭，通过每个节点的值进行比较来确定新的节点要插入的位置。(注意这里存储的是键值对，pair要按照pair.first来作为key进行比较）

---2--- 当cur在往下走之前要记得保存上一结点的位置，方便后面的调整，在找到nullptr时来进行插入，请注意如果根节点为空时，将新插入的结点作为根节点，并且为了满足性质2，将根节点的颜色改为BLACK后返回true。（请注意prev，cur以及_root的parent是否正确。）

---3--- 下面进行红黑树的调整和旋转：！！！重要

首先需要知道一共分为三种情况：下面将cur的父亲作为parent，parent的父亲作为grandfather，如果存在的话，将grandfather另一个孩子结点作为uncle。

//uncle存在且为红色，这时只需要改变颜色
//uncle存在且为黑色，这时需要改变颜色并进行旋转调整
//uncle不存在，这时同样需要改变颜色并进行调整

由于情况2/3非常相似，合并为一种大类情况进行处理：

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

Case 1：uncle存在且为红

思路：

---1--- 这种情况，只需要将grandfather改为红色，将uncle和parent改为黑色，插入的结点默认为红色

---2--- 在进行完上述操作之后，就符合了红黑树的性质，随后需要继续向上调整

Case 2：uncle不在或为黑

思路：

---1--- 这里就要分为两种情况，如果grandfather，parent和cur在同侧的话，就要进行单旋，如果为异侧，那么需要需要进行双旋。

---2--- 旋转完成需要对颜色进行调整，只有将旋转后位于父亲位置的parent/grandfather/cur（三者都可能位于父亲结点，具体情况具体分析）设置为BLACK，其余的两者设置为RED才能使红黑树保持平衡，并且调整完后无需继续向上更新，因为已经达到平衡。

整合：

---1--- 先将要插入的值与每个结点的值进行比较，按照BST二叉搜索树的方式找到正确的插入位置，随后进行调整变色旋转

---2--- 确定grandfather，parent和cur之后，可以分为两大类：parent在grandfather左&parent在grandfather右，随后可以确定uncle

---3--- 其次根据uncle的存在情况和颜色情况进行两种处理，这里要注意的是第二种情况中的旋转：

        如果p在g左，c在p左，那么就进行右单旋，随后将p设为BLACK，g设为RED

  如果p在g左，c在p右，那么就进行左右双旋，随后将c设为BLACK，g设为RED

        如果p在g右，c在p右，那么就进行左单旋，随后将p设为BLACK，g设为RED

如果p在g右，c在p左，那么就进行右左双旋，随后将c设为BLACK，g设为RED

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 (parent == grandfather->_left){Node* uncle = grandfather->_right;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else // u不存在 或 存在且为黑{if (cur == parent->_left){//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else // parent == grandfather->_right{Node* uncle = grandfather->_left;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

Step 4: 刨析旋转

（请注意双旋就是由不同的单旋操作完成的，就不再赘述双旋部分操作）

左单旋：

思路：

---1--- 如图，新节点插入在了根节点的右子树的右子树，很明显右子树比左子树高

---2--- 那么此时就需要将左子树向下按1，让两边的子树保持平衡，将root设置为parent，parent->_right设置为cur，cur->_left设置为curleft，这时需要将curleft连接在parent->_right，将parent连接到cur->_left上

---3--- 接下来要对一些细节进行处理，如果parent为根节点，那么旋转后需要更新根节点

---4--- 如果curleft不存在，就不需要更改curleft的父亲了，否则需要更改

---5--- 别忘记了对parent，cur，curleft的父亲进行更改，对parent需要将其parent提前保存在ppnode中，对于cur，别忘记在最后更改其父亲结点，否则在调试时需要花费大量时间！

//左单旋
void RotateL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;Node* ppnode = parent->_parent;parent->_right = curleft;cur->_left = parent;//这里curleft有可能是不存在的，那么需要特殊判断一下if (curleft){curleft->_parent = parent;}//parent有可能为根结点，根节点需要改变，判断一下cur->_parent = ppnode;if (parent == _root){_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}}parent->_parent = cur;
}

右单旋：

思路：（与左单旋仅仅只有部分不同）

---1--- 如图新节点插入在了根节点的左子树的左子树，很明显左子树比右子树高2

---2--- 那么此时就需要将左子树向下按1，让两边的子树保持平衡，将root设置为parent，parent->_left设置为cur，cur->_right设置为curright，这时需要将curright连接在parent->_left，将parent连接到cur->_right上

---3--- 接下来要对一些细节进行处理，如果parent为根节点，那么旋转后需要更新根节点

---4--- 如果curright不存在，就不需要更改curright的父亲了，否则需要更改

---5--- 别忘记了对parent，cur，curleft的父亲进行更改，对parent需要将其parent提前保存在ppnode中，对于cur，别忘记在最后更改其父亲结点，否则在调试时需要花费大量时间！

//右单旋
void RotateR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;Node* ppnode = parent->_parent;parent->_left = curright;cur->_right = parent;//这里curleft有可能是不存在的，那么需要特殊判断一下if (curright){curright->_parent = parent;}//parent有可能为根结点，根节点需要改变，判断一下cur->_parent = ppnode;if (parent == _root){_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}}parent->_parent = cur;
}

Step 5：检查红黑树

写完了红黑树树的插入函数，如果要检查是否正确，该怎么办？请补充接下来三个函数：