C++ 红黑树

上一节我介绍了二叉搜索树家族的AVL树，这里我们来介绍二叉搜索树家族的另一个成员，也是使用最广泛的成员。

1.AVL树与红黑树的区别

• 平衡性质
  • AVL 树：是严格的平衡二叉树，要求任意节点的左右子树高度差的绝对值不超过 1，能保证树的高度始终保持在O(logn)级别，查询效率非常稳定。
  • 红黑树：是一种弱平衡的二叉树，通过节点颜色和一些规则来保证从根节点到叶子节点的最长路径不超过最短路径的 2 倍，虽然不能像 AVL 树那样严格控制高度，但在实际应用中也能提供较为高效的操作。
• 插入和删除操作
  • AVL 树：插入和删除节点后，为了保持平衡，可能需要进行多次旋转操作，调整的频率相对较高，导致其插入和删除操作的时间复杂度相对不稳定。
  • 红黑树：插入和删除操作相对简单，因为它的平衡条件相对宽松，所以在插入和删除时需要进行的调整操作通常比 AVL 树少，这使得红黑树在频繁进行插入和删除操作的场景下，效率可能更高。
• 空间复杂度
  • AVL 树：节点结构相对简单，通常只需要存储数据和左右子节点的指针，不需要额外的空间来存储颜色等信息，所以空间复杂度相对较低。
  • 红黑树：由于需要为每个节点设置颜色属性，因此每个节点需要额外的存储空间来存储颜色信息，这使得红黑树的空间复杂度相对 AVL 树略高。
• 应用场景
  • AVL 树：适用于查询操作非常频繁，对查询效率要求极高，且数据相对稳定，插入和删除操作较少的场景，如数据库索引、编译器的符号表等。
  • 红黑树：在插入和删除操作比较频繁，同时对查询效率也有一定要求的场景中表现出色，如 STL 中的 map、set 等容器，以及 Linux 内核中的进程调度等。

2.红黑树的概念

2.1 红黑树的规则

为了完成红黑树的功能，设计者设计了以下规则来控制

1. 每个结点不是红⾊就是⿊⾊

2. 根结点是⿊⾊的

3. 如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的

红⾊结点。

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

2.2红黑树的效率

3.红黑树的实现

3.1红黑树的结构

enum Colour
{RED,BLACK
};
template<class K,class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _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;
};

3.2 红黑树的插入

3.2.1红⿊树树插⼊⼀个值的⼤概过程

3.2.2情况1：变⾊

3.2.3情况2：单旋+变⾊

3.2.4情况2：双旋+变⾊

3.3红⿊树的插⼊代码实现

#pragma onceenum Colour
{RED,BLACK
};
template<class K,class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _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: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){parent = cur;if (cur->_kv.first > kv.first){cur = cur->_left;}else if(cur->_kv.first<kv.first){cur = cur->_right;}else{return false;}}cur = new Node(kv);cur->_parent = parent;cur->_col = RED;if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}//控制颜色的平衡while (parent && parent->_col == RED){Node* grandparent = parent->_parent;Node* uncle;if (parent == grandparent->_left){uncle = grandparent->_right;}else{uncle = grandparent->_left;}//uncle存在且为红色if(uncle && uncle->_col == RED){grandparent->_col = RED;uncle->_col = BLACK;parent->_col = BLACK;cur = grandparent;}else {if (parent == grandparent->_left){if(cur == parent->_left){RotateR(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{RotateLR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}else{if (cur == parent->_right){RotateL(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{RotateRL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return true;}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;}void InOrder(){_InOrder(_root);}void _InOrder(const Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ' ';_InOrder(root->_right);}void RotateRL(Node* parent){Node* parentR = parent->_right;Node* parentRL = parentR->_left;RotateR(parent->_right);RotateL(parent);}void RotateLR(Node* parent){Node* parentL = parent->_left;Node* parentLR = parentL->_right;RotateL(parent->_left);RotateR(parent);}void RotateR(Node* parent){Node* parentL = parent->_left;Node* parentLR = parentL->_right;Node* parentPa = parent->_parent;if (parentPa){if (parent == parentPa->_left)parentPa->_left = parentL;elseparentPa->_right = parentL;}if (parentLR)parentLR->_parent = parent;parent->_parent = parentL;parent->_left = parentLR;parentL->_right = parent;parentL->_parent = parentPa;}void RotateL(Node* parent){Node* parentR = parent->_right;Node* parentRL = parentR->_left;Node* parentPa = parent->_parent;if (parentPa){if (parent == parentPa->_left)parentPa->_left = parentR;elseparentPa->_right = parentR;}if (parentRL)parentRL->_parent = parent;parent->_parent = parentR;parent->_right = parentRL;parentR->_parent = parentPa;parentR->_left = parent;}private:Node* _root = nullptr;
};

 3.4红⿊树的查找

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;
}

3.5红⿊树的验证

bool IsRBTree()
{return _IsRBTree(_root);
}
bool _IsRBTree(const Node* root)
{if (root == nullptr)return true;if (root->_col == RED)return false;Node* cur = root;int RetNum = 0;while (cur){if (cur->_col == BLACK)RetNum++;cur = cur->_left;}return Check(root, 0, RetNum);
}bool Check(const Node*& root,int BlackNum,int refNum)
{if (root == nullptr){if (BlackNum != refNum){cout << "黑色节点数不匹配" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == BLACK){cout << "红色节点重复" << endl;return false;}if (root->_col == BLACK){BlackNum++;}return Check(root->_left, BlackNum, refNum) && Check(root->_right, BlackNum, refNum);
}