C++进阶——红黑树-开发者社区

一、红黑树的概念

红黑树是一棵二叉搜索树，他的每个节点增加一个数据来存储颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会超出其他路径2倍的长度
1.1 红黑树的规则
每个节点不是红色就是黑色
根节点是黑色的
如果一个节点是红的，他的孩子节点就是黑色的，这意味着任意一条路径不能出现连续的红色节点
对任意一个节点，从该节点到其所有NULL节点的简单路径上，均包含相同数量的黑色节点
当我们能时刻满足这四条规则时，我们就能确保树上没有一条路径会超出其他路径2倍的长度。
1.2 红黑树的效率
假设N是红黑树树中结点数量，h是最短路径长度，则2^h-1<=N<2^(2*h)-1,由此推出：h大约为logN，也就意味着红黑树增删查改最坏也就是走最长路径2*logN，那么时间复杂度还是O（logN）
红黑树的表达相对AVL树要抽象一些，AVL树通过控制高度差直观地控制了平衡。红黑树通过4条规则的约束，实现了近似平衡，它们的效率都是同一档次，但红黑树插入节点时旋转次数更少

二、红黑树的实现

2.1 红黑树的结构
enum Color { RED, BLACK }; template<class K,class V> struct RBTreeNode { pair<K, V> _kv; Color _col; RBTreeNode<K, V>* _parent; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode(const pair<K,V> kv) :_kv(kv) ,_parent(nullptr) ,_left(nullptr) ,_right(nullptr) { } }; template<class K,class V> class RBTree { typedef RBTreeNode<K, V> Node; public: RBTree(Node* root=nullptr) :_root(root) { } private: Node* _root; };
2.2 红黑树的插入
2.2.1 节点插入的大概过程
插入一个值按二叉搜索树规则插入，插入后只需观察是否符合红黑树的四条规则
如果是空树插入，新增节点是黑色节点。如果不是空树，选中节点必须是红色节点，若插入黑色节点，会破坏规则4
非空树插入后，新增节点的父节点如果是黑色，就未破坏规则，插入结束
若父节点是红色的，则违反规则3。据下图：c是红色，p是红色，g必为黑色
2.2.2 情况1：变色
若c、p、u均为红色节点，g为黑色节点，就将p、u变黑，g变红；再将g变为新的c，向上更新
2.2.3 情况2：单旋+变色
c、p为红，g为黑，u不存在或u为黑：
u不存在，c必为新增节点，因为若c为原来的g节点，那么它因为孩子节点变色而变红，原来是黑色节点，但u的分支后面没有黑色节点了，不满足每条分支黑色节点数量相等
u存在且为黑，c一定不是新增节点
2.2.4 情况3：双旋+变色
c、p为红，g为黑，u不存在或存在为黑：
2.3 红黑树的验证
规则1枚举颜色类型，天然保证了颜色只有黑色和红色
规则2可直接验证
规则3前序遍历检查，遇到红色节点就查孩子不太方便，可反过来检查父节点颜色
前序遍历，遍历时用形参记录当前节点到根黑色节点数量，直到空节点，再选任意一条路径黑色节点作为参考值，依次比较

三、全部实现代码

#pragma once #include<iostream> #include<cassert> using namespace std; enum Color { RED, BLACK }; template<class K,class V> struct RBTreeNode { pair<K, V> _kv; Color _col; RBTreeNode<K, V>* _parent; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode(const pair<K,V> kv) :_kv(kv) ,_parent(nullptr) ,_left(nullptr) ,_right(nullptr) { } }; template<class K,class V> class RBTree { typedef RBTreeNode<K, V> Node; public: RBTree(Node* root=nullptr) :_root(root) { } bool Insert(const pair<K, V>& kv) { Node* newnode = new Node(kv); newnode->_col = RED; if (_root == nullptr) { newnode->_col = BLACK; _root = newnode; return true; } Node* pcur = _root; Node* parent = pcur; while (pcur) { parent = pcur; if (pcur->_kv.first < kv.first) pcur = pcur->_right; else if (pcur->_kv.first > kv.first) pcur = pcur->_left; else { delete newnode; return false; } } //开始插入 pcur = newnode; pcur->_parent = parent; if (parent->_kv.first > kv.first) parent->_left = pcur; else parent->_right = pcur; while (parent && parent->_col != BLACK) { Node* g = parent->_parent; Node* u = nullptr; if (g) { if (parent == g->_left)u = g->_right; else u = g->_left; if (u && u->_col == RED && g->_col == BLACK)//情况1：p、c、u、都是红色，g为黑色 { parent->_col = BLACK; u->_col = BLACK; g->_col = RED; pcur = g; parent = g->_parent; } else if (parent==g->_left&&pcur==parent->_left)//情况2：单旋+变色 { RotateR(parent); parent->_col = BLACK; g->_col = RED; break; } else if (parent->_right == pcur && g->_right == parent) { RotateL(parent); parent->_col = BLACK; g->_col = RED; break; } else if (parent->_right==pcur&&g->_left==parent)//情况三：双旋+变色 { RotateL(pcur); RotateR(pcur); pcur->_col = BLACK; g->_col = RED; break; } else if (parent->_left == pcur && g->_right == parent) { RotateR(pcur); RotateL(pcur); pcur->_col = BLACK; g->_col = RED; break; } } } _root->_col = BLACK; return true; } void Print(Node* root) { if (root == nullptr) return; Print(root->_left); cout << root->_kv.first << ":" << root->_kv.second << " "; Print(root->_right); } Node* root() { return _root; } Node* Find(const K& key) { Node* pcur = _root; while (pcur) { if (pcur->_kv.first > key) pcur = pcur->_left; else if (pcur->_kv.first < key) pcur = pcur->_right; else return pcur; } return nullptr; } bool Isrbtree(Node* root) { if (_root == nullptr)return true; if (root->_col != BLACK)return false; int refnum = 0; Node* cur = root; while (cur != nullptr) { if (cur->_col == BLACK)refnum++; cur = cur->_left; } return Preorder(root,0,refnum); } private: bool Preorder(Node* root, int num, const int ref) { if (root == nullptr) { return num == ref; } if (root->_col == RED && root->_parent->_col != BLACK) { cout << "出现连续红色节点！" << endl; return false; } if (root->_col == BLACK) return Preorder(root->_left, num + 1, ref) && Preorder(root->_right, num + 1, ref); if (root->_col == RED) return Preorder(root->_left, num, ref) && Preorder(root->_right, num, ref); } void RotateR(Node* cur) { Node* parent = cur->_parent; Node* grandpa = parent->_parent; parent->_left = cur->_right; parent->_parent = cur; if (cur->_right) cur->_right->_parent = parent; if (grandpa) { if (grandpa->_right == parent) grandpa->_right = cur; else grandpa->_left = cur; } else _root = cur; cur->_parent = grandpa; cur->_right = parent; } void RotateL(Node* cur) { Node* parent = cur->_parent; Node* grandpa = parent->_parent; parent->_right = cur->_left; parent->_parent = cur; if (cur->_left) { cur->_left->_parent = parent; } if (grandpa) { if (grandpa->_right == parent) grandpa->_right = cur; else grandpa->_left = cur; } else _root = cur; cur->_parent = grandpa; cur->_left = parent; } Node* _root; };