C++进阶——红黑树的实现

目录

1、红黑树的概念

1.1 红黑树的定义

1.2 红黑树的规则

1.3 为什么没有一条路径会比其他路径长出两倍

1.4 红黑树的性能

2、红黑树的实现

2.1 红黑树的结构

2.2 红黑树的插入

2.2.1 红黑树插入一个值的大概过程

2.2.2 情况1：变色

2.2.3 情况2：单旋+变色

2.2.4 情况3：双旋+变色

2.2.5 红黑树插入的代码实现

2.3 红黑树的查找

2.4 红黑树的验证

2.5 红黑树的删除

2.6 红黑树的代码实现

2.6.1 RBTree

2.6.2 Test.cpp

---

1、红黑树的概念

1.1 红黑树的定义

红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。通过对从根节点到叶子节点的路径上的节点颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因此它是近似平衡的。

1.2 红黑树的规则

1. 每个节点不是红色就是黑色。

2. 根节点是黑色的。

3. 红色节点的子节点必须是黑色的，即任意一条路径不能有连续的红色结点。

4. 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点。

从根节点开始，有9条路径。

补充说明：在《算法导论》等书籍中，通常会补充一条规则，即每个叶子节点（NIL节点）都是黑色的。这里的叶子节点并不是传统意义上的叶子节点，而是指空节点（NIL节点），有时也称为外部节点。NIL节点的引入是为了方便准确地标识出所有路径。

1.3 为什么没有一条路径会比其他路径长出两倍

根据规则4，从根节点到任意NIL节点的路径上的黑色节点数量是相同的。假设最短路径上的黑色节点数量为bh（black height），那么最短路径的长度就是bh（即全黑的路径）。

根据规则2和规则3，根节点是黑色节点，路径中不能有连续的红色节点。因此，最长路径的节点颜色分布只能是“黑-红-黑-红...”交替出现。假设最短路径的长度为bh，那么最长路径的长度最多为2*bh（即一黑一红交替的路径）。

最短路径和最长路径是极端情况，可能一棵树中都没有。假设任意一条从根到NULL结点路径的长度为x，那么bh<=x<=2*bh。

1.4 红黑树的性能

1. 红黑树的高度近似为 log⁡N。

2. 红黑树的查找、插入、删除等操作的时间复杂度均为 O(log⁡N)。

3. 虽然它的平衡性不如AVL树严格，但在实际应用中，红黑树的旋转次数较少，性能表现良好。红黑树和AVL树的时间复杂度都是 O(log⁡N)，适用于需要高效查找、插入、删除操作的场景。

2、红黑树的实现

2.1 红黑树的结构

	enum Color{RED,BLACK};template<class K,class V>struct RBTreeNode{pair<K,V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _col;RBTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){ }};template<class K,class V>class RBTree{typedef RBTreeNode<K, V> Node;public://...private:Node* _root = nullptr;};

2.2 红黑树的插入

2.2.1 红黑树插入一个值的大概过程

1. 按二叉搜索树的规则插入一个值。

2. 如果是向空树中插入，新节点应为黑色节点(即根节点，规则2，根节点是黑色的)。

如果是向非空树中插入，新节点必须是红色节点，因为插入黑色新节点会破坏规则4，而规则4较难维护。

3. 在非空树中插入后，新节点必须是红色节点。如果其父节点是黑色的，则未违反任何规则，插入操作结束。

4. 在非空树中插入后，新节点必须是红色节点。如果其父节点是红色的，则违反了规则3。

若新节点cur为红色，其父节点parent也为红色，则祖父节点grandfather必为黑色，因为插入就是红黑树，不会出现连续的红节点。这三个节点的颜色已确定，关键在于考察叔叔节点uncle的情况。

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

2.2.2 情况1：变色

叔叔存在且为红。

p和u变黑，g变红，

再c = g，c如果是根，c变黑，操作结束，如果是局部子树的根，继续向上判断。

如果p是g的右，操作相同。

注意：无所谓c是p的左或右，因为是c的p,g,u变色。

2.2.3 情况2：单旋+变色

叔叔存在且为黑，或叔叔不存在。bh(black height)为路径上黑色节点的数量。

对g进行右旋，将p(根)变黑，g变红。                                              对g进行左旋，其他操作相同。

旋转后，子树根节点是黑色，且满足规则3，4，操作结束。

2.2.4 情况3：双旋+变色

叔叔存在且为黑，或叔叔不存在。bh(black height)为路径上黑色节点的数量。

先对p进行左旋，再对g进行右旋，将c(根)变黑，g变红。          先对p进行右旋，再对g进行左旋，相同操作相同。            

旋转后，子树根节点是黑色，且满足规则3，4，操作结束。

2.2.5 红黑树插入的代码实现

		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 (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 = new Node(kv);if (kv.first > parent->_kv.first)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (parent&&parent->_col == RED){Node* grandfather = parent->_parent;Node* uncle;if (parent == grandfather->_left){//    g//  p   uuncle = 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{//    g//  u   puncle = 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;}}}if (parent == nullptr)_root->_col = BLACK;return true;}

2.3 红黑树的查找

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

2.4 红黑树的验证

1. 规则1通过枚举颜色类型来天然保证颜色要么是黑色要么是红色。

2. 规则2只需直接检查根节点即可满足条件。

3. 规则3采用前序遍历进行检查，当遇到红色节点时，检查其孩子节点不太方便，因为孩子节点有两个且不一定都存在。相反，遇到红色节点，检查父节点的颜色更方便。

4. 规则4使用前序遍历，在遍历过程中通过形参记录从根节点到当前节点的黑色节点数量（blackNum）。每遇到黑色节点，++blackNum。当遍历到空节点时，就计算出了一条路径上的黑色节点数量。然后，可以将任意一条路径的黑色节点数量作为参考值，依次进行比较即可。

		bool IsBalance(){if (_root->_col != BLACK)return false;Node* cur = _root;int refNum = 0;while (cur){if (cur->_col == BLACK)++refNum;cur = cur->_left;}return _IsBalance(_root, 0, refNum);}bool _IsBalance(Node* root, int blackNum, const int refNum){if (root == nullptr){if (blackNum != refNum)return false;elsereturn true;}if (root->_col == RED && root->_parent->_col == RED)return false;if (root->_col == BLACK)++blackNum;return _IsBalance(root->_left, blackNum, refNum) && _IsBalance(root->_right, blackNum, refNum);}

2.5 红黑树的删除

红黑树的删除本章节不做讲解，有兴趣的同学可参考：《算法导论》或者《STL源码剖析》中讲解。

2.6 红黑树的代码实现

2.6.1 RBTree

#pragma once#include <iostream>
#include <assert.h>using namespace std;namespace Lzc
{enum Color{RED,BLACK};template<class K,class V>struct RBTreeNode{pair<K,V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _col;RBTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){ }};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 (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 = new Node(kv);if (kv.first > parent->_kv.first)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (parent&&parent->_col == RED){Node* grandfather = parent->_parent;Node* uncle;if (parent == grandfather->_left){//    g//  p   uuncle = 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{//    g//  u   puncle = 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;}}}if (parent == nullptr)_root->_col = BLACK;return true;}void RotateR(Node* parent){Node* pParent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;subL->_parent = pParent;if (pParent == nullptr) // 当pParent == nullptr时,_root == parent{_root = subL;}else{if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;}}void RotateL(Node* parent){Node* pParent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;subR->_parent = pParent;if (pParent == nullptr)_root = subR;else{if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;}}Node* Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_kv.first)cur = cur->_right;else if (key < cur->_kv.first)cur = cur->_left;elsereturn cur;}return nullptr;}void InOrder(){_InOrder(_root);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}bool IsBalance(){if (_root->_col != BLACK)return false;Node* cur = _root;int refNum = 0;while (cur){if (cur->_col == BLACK)++refNum;cur = cur->_left;}return _IsBalance(_root, 0, refNum);}~RBTree(){Destroy(_root);_root = nullptr;}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}int _Height(Node* root){if (root == nullptr)return 0;int LeftHeight = _Height(root->_left);int RightHeight = _Height(root->_right);return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;}int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}bool _IsBalance(Node* root, int blackNum, const int refNum){if (root == nullptr){if (blackNum != refNum)return false;elsereturn true;}if (root->_col == RED && root->_parent->_col == RED)return false;if (root->_col == BLACK)++blackNum;return _IsBalance(root->_left, blackNum, refNum) && _IsBalance(root->_right, blackNum, refNum);}Node* _root = nullptr;};
}

2.6.2 Test.cpp

#include"RBTree.h"
#include<vector>
#include<time.h>namespace Lzc
{void TestRBTree1() {RBTree<int, int> rbt;// 常规的测试用例int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例// int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a) {rbt.Insert({ e, e });}rbt.InOrder();cout << rbt.IsBalance() << endl;}// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等void TestRBTree2() {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);}// 测试插入性能size_t begin2 = clock();RBTree<int, int> rbt;for (auto e : v) {rbt.Insert(make_pair(e, e));}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;// 测试平衡性、高度和大小cout << "IsBalance:" << rbt.IsBalance() << endl;cout << "Height:" << rbt.Height() << endl;cout << "Size:" << rbt.Size() << endl;// 测试查找性能size_t begin1 = clock();// 查找已存在的值/*for (auto e : v) {rbt.Find(e);}*/// 查找随机值for (size_t i = 0; i < N; i++) {rbt.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;}}int main()
{Lzc::TestRBTree1();//Lzc::TestRBTree2();return 0;
}