文章目录
- 概念
- 满足的条件性质
- 实现
- 红黑树的定义
- 红黑树节点
- 插入操作
- 情况一
- 情况二
- 情况三
- Insert()总代码
- 其余操作
- 左右单旋
- RotateL 左单旋
- RotateR 右单旋
- prevCheck 红黑树性质检测
- isBalance 红黑树平衡判断
- InOrder 中序遍历
- 完整代码
概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
满足的条件性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
- 所有叶子节点（ NIL节点，空节点 ）是黑色的。
这些性质保证了红黑树的高度不会超过 2log(n+1) ，其中 n 是树中节点的个数。因此，红黑树可以在O(log n)时间内完成插入、删除、查找等操作，是一种非常高效的数据结构。
这里提一下 NIL节点 ：
nil 节点就是空节点，在红黑树的实现中，nil 节点代替二叉树中的 NULL：叶子节点的左节点和右节点指针都指向 nil 节点；只一个子树的节点，其另外一个子节点指针也指向 nil 节点；根节点的父节点也指向 nil 节点。
当我们从红黑树中删除一个节点时，需要考虑其子树的平衡问题，否则可能导致树不平衡，进而破坏红黑树性质。如果该节点只有一个子节点，我们需要将该节点的子节点替代该节点的位置。如果该节点没有子节点，则在其位置插入一个NIL节点，起到保持红黑树平衡的作用。
实现
红黑树的定义
// 枚举类型 标明颜色
// 节点颜色
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){}
};// 红黑树定义
template <class K, class V>
struct RBTree
{//typedef节点typedef RBTreeNode<K, V> Node;
public:// 关键：插入操作bool Insert(const pair<K, V> kv){}// 中序遍历void InOrder(){_InOrder(_root);cout << endl;}// 判断平衡bool IsBalance(){}private:// 中序遍历void _InOrder(Node* root){}// 检查红黑树// 会先判断当前节点是否为nullptr// 如果是，则说明检查到叶节点，记录当前节点中黑色节点的数量，并且与之前的比较// 如果不相等，则输出错误信息并返回false。如果相等，则返回true。bool prevCheck(Node* root, int blackNum, int& benchmark){}// 左单旋void RotateL(Node* parent){}// 右单旋void RotateR(Node* parent){}private:Node* _root = nullptr;
};
红黑树节点
- _left：表示当前节点的左子节点指针；
- _right：表示当前节点的右子节点指针；
- _parent：表示当前节点的父节点指针；
- _kv：表示当前节点存储的键值对；
- _col：表示当前节点的颜色，用于约束红黑树的性质。
- 构造函数：用于初始化成员变量；
// 枚举类型 标明颜色
// 节点颜色
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){}
};
插入操作
我们将插入操作分为三个部分进行：
1. 判断根节点是否为空，如果为空，则直接将新节点作为根节点创建并返回true
// 第一部分
// 1. 判断根节点是否为空，如果为空，则直接将新节点作为根节点创建并返回true。
if (_root == nullptr)
{_root = new Node(kv);_root->_col = BLACK; //根节点为黑色return true;
}
2. 在树中寻找待插入节点要插入的位置，当遍历到叶子节点时，将新节点加入到该叶子节点的左边或右边，成为该叶子节点的子节点。
- 由于红黑树本身是一种平衡二叉树，在插入操作中先进行平衡二叉树一样的操作，第二部分就是进行平衡二叉树的节点插入操作。
// 第二部分
// 2. 在树中寻找待插入节点要插入的位置，当遍历到叶子节点时，将新节点加入到该叶子节点的左边或右边，成为该叶子节点的子节点。Node* parent = nullptr;
Node* cur = _root;
// 如果cur->_kv.first小于kv.first，则将cur指向右子节点，并且parent指向cur；否则将cur指向左子节点，并且parent指向cur。
// 如果插入的键值已存在，则直接返回false
while (cur)
{// 插入节点大，向右插入if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}// 插入节点小，向左插入else if (kv.first < cur->_kv.first) {parent = cur;cur = cur->_left;}else {return false;}
}// 判断kv应该插入parent的左边or右边
cur = new Node(kv);
if (kv.first > parent->_kv.first) {parent->_right = cur;
}
else {parent->_left = cur;
}cur->_parent = parent;
3. 当新节点的父节点是红色，而叔节点是黑色（或者不存在），并且新节点是其父节点的左子节点，则需要进行右旋，然后进行变色操作，使之平衡。
对于红黑树的平衡我们分为三种情况：
首先我们令 插入的节点为
cur，父节点为parent，parent的父节点为grandparent，父节点同一层的另一个节点（grandparent的另一个子节点）为uncle
情况一
情况一：
- 当新节点的父节点和叔节点都是红色时，需要将父节点和叔节点变为黑色，将祖父节点变为红色，并将新节点指向祖父节点，然后继续向上处理。
即 cur为红色，parent为红色，grandparent为黑色，uncle存在且为红色
if (uncle && uncle->_col == RED)
{// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;
}
// 根节点变为黑色
_root->_col = BLACK;
情况二
情况二：
- 当新节点的父节点是红色，而叔节点是黑色（或者不存在），并且新节点是其父节点的右子节点，则需要进行左旋，变成第三种情况。
即 cur为红色，parent为红色，grandparent为黑色，uncle不存在 / 存在且为黑色，且cur为parent的右子节点
u不存在
u存在且为黑色
// 情况二 : cur为红，p为红，g为黑，u不存在 / u为黑
// -> 右单旋+变色 -> 右单旋+p变黑，g变红
if (cur == parent->_left)
{// 右单旋 祖父节点RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;
}
情况三
情况三：
- 当新节点的父节点是红色，而叔节点是黑色（或者不存在），并且新节点是其父节点的左子节点，则需要进行右旋，然后进行变色操作，使之平衡。
即 cur为红色，parent为红色，grandparent为黑色，uncle不存在 / 存在且为黑色，且cur为parent的左子节点
u不存在
u存在且为黑
// 情况三 : cur为红，p为红，g为黑，u不存在 / u存在且为黑
// 双旋 + 变色
if (cur == parent->_right)
{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;
}
Insert()总代码
- 根据上文分析的三种情况总结并补充其余细节写出插入操作的总实现
bool Insert(const pair<K, V> kv)
{// 二叉平衡树的插入操作// 1. 判断根节点是否为空，如果为空，则直接将新节点作为根节点创建并返回true。if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK; //根节点为黑色return true;}// 2. 在树中寻找待插入节点要插入的位置，当遍历到叶子节点时，将新节点加入到该叶子节点的左边或右边，成为该叶子节点的子节点。Node* parent = nullptr;Node* cur = _root;// 根据 kv.first 的大小逐步向左或右寻找合适的插入位置:// 如果cur->_kv.first小于kv.first，则将cur指向右子节点，并且parent指向cur；否则将cur指向左子节点，并且parent指向cur。// 如果插入的键值已存在，则直接返回falsewhile (cur){// 插入节点大，向右插入if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}// 插入节点小，向左插入else if (kv.first < cur->_kv.first) {parent = cur;cur = cur->_left;}else {return false;}}// 判断cur应该插入parent的左边or右边cur = new Node(kv);if (kv.first > parent->_kv.first) {parent->_right = cur;}else {parent->_left = cur;}cur->_parent = parent;// 3. 插入新节点后，需要通过旋转和变色实现红黑树的自平衡。// 如果新节点的父节点是黑色的，则直接插入不需要调整。如果父节点是红色的，则需要进行适当的旋转和变色使之平衡。while (parent && parent->_col == RED) {// 定义祖父节点Node* grandfather = parent->_parent;assert(grandfather);assert(grandfather->_col == BLACK); //根据红黑树的性质，此时grandparent节点应该是黑色的// 平衡主要看 uncle节点if (parent == grandfather->_left) {Node* uncle = grandfather->_right;// 情况一 : uncle 存在且为红 -> 变色+继续向上处理if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{// 情况二 : cur为红，p为红，g为黑，u不存在 / u为黑// -> 右单旋+变色 -> 右单旋+p变黑，g变红if (cur == parent->_left){// 右单旋 祖父节点RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 情况三 : cur为红，p为红，g为黑，u不存在 / u存在且为黑// 双旋 + 变色else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}// (parent == grandfather->_right)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;}break;}}}// 根节点为黑色// 返回true;_root->_col = BLACK;return true;
}
其余操作
左右单旋
这里不再进行旋转的详细解释，具体在下面的文章中：
AVLTree 的插入旋转操作
RotateL 左单旋
void RotateL(Node* parent)
{// 保存父节点右子树的左子树 subRLNode* subR = parent->_right;Node* subRL = subR->_left;// 将 parent 的右子树指向 subRLparent->_right = subRL;if (subRL)subRL->_parent = parent;// 调整 subR 和 parent 的关系subR->_left = parent;parent->_parent = subR;// 如果此时 parent 是根节点，修改根节点为 subRif (_root == parent){_root = subR;subR->_parent = nullptr;}else{// 将 parent 的父节点 ppNode 指向 subRNode* ppNode = parent->_parent;if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}
}
RotateR 右单旋
// 右单旋：以 parent 为轴心，将其左子树 subL 向右旋转（右子树不变）
void RotateR(Node* parent)
{// 保存父节点左子树的右子树 subLRNode* subL = parent->_left;Node* subLR = subL->_right;// 将 parent 的左子树指向 subLRparent->_left = subLR;if (subLR){subLR->_parent = parent;}// 调整 subL 和 parent 的关系subL->_right = parent;parent->_parent = subL;// 如果此时 parent 是根节点，修改根节点为 subLif (_root == parent){_root = subL;subL->_parent = nullptr;}else{// 将 parent 的父节点 ppNode 指向 subLNode* ppNode = parent->_parent;if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}
}
prevCheck 红黑树性质检测
- 红黑树的性质检验函数 prevCheck，其功能是检查红黑树的各个节点是否符合红黑树的特征。
// 检查红黑树
// 会先判断当前节点是否为nullptr
// 如果是，则说明检查到叶节点，记录当前节点中黑色节点的数量，并且与之前的比较
// 如果不相等，则输出错误信息并返回false。如果相等，则返回true。
bool prevCheck(Node* root, int blackNum, int& benchmark)
{if (root == nullptr){// 如果benchmark的值为0，说明之前没有记录过当前红黑树路径中的黑色节点数量// 这时将benchmark的值设置为当前黑色节点的数量。if (benchmark == 0) {benchmark = blackNum;return true;}// 如果当前路径上的黑色节点数量与之前记录的benchmark不相等，输出错误信息并返回falseif (blackNum != benchmark) {cout << "某条路径的黑色节点数量不相等" << endl;return false;}else { // 当前路径上的黑色节点数量与之前记录的benchmark相等，返回truereturn true;}}// 遇到黑色节点，++blackNumif(root->_col==BLACK){++blackNum;}// 遇到连续的红节点，则证明有错if (root->_col == RED && root->_parent->_col == RED){cout << "error: 存在连续的红色节点" << endl;return false;}return prevCheck(root->_left, blackNum, benchmark)&& prevCheck(root->_right, blackNum, benchmark);
}
isBalance 红黑树平衡判断
- 红黑树的平衡性检验函数 IsBalance。
bool IsBalance()
{if (_root == nullptr)return true;if (_root->_col == RED){cout << "false: 根节点为红色" << endl;return false;}// 黑色节点数量 基准值int benchmark = 0;// 也可行 ↓/*Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}*/return prevCheck(_root, 0, benchmark);
}
InOrder 中序遍历
public:
void InOrder()
{_InOrder(_root);cout << endl;
}private:
void _InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);
}
完整代码
gitee - RBTree代码
