RBTree的模拟实现

1：红黑树的概念

红⿊树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表⽰结点的颜⾊，可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍，因⽽是接近平衡的。

1：红黑树的规则

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

2. 根结点是⿊⾊的

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

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

2：红黑树确保最短路径的方法

1:由规则4可知，从根到NULL结点的每条路径都有相同数量的⿊⾊结点，所以极端场景下，最短路径就就是全是⿊⾊结点的路径，假设最短路径⻓度为bh(black height)。

2:由规则2和规则3可知，任意⼀条路径不会有连续的红⾊结点，所以极端场景下，最⻓的路径就是⼀⿊⼀红间隔组成，那么最⻓路径的⻓度为2* bh

3:综合红⿊树的4点规则⽽⾔，理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为x，那么bh <= h <= 2 * bh。

3： 红⿊树的效率

假设N是红⿊树树中结点数量，h最短路径的⻓度，那么, 由此推出，也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径 ，那么时间复杂度还是。2h − 1 <= N < 22∗h − 1h ≈ logN 2 ∗ logNO(logN)红⿊树的表达相对AVL树要抽象⼀些，AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜⾊约束，间接的实现了近似平衡，他们效率都是同⼀档次，但是相对⽽⾔，插⼊相同数量的结点，红⿊树的旋转次数是更少的，因为他对平衡的控制没那么严格。

2：红黑树的模拟实现

1：红黑树的结构

// 枚举值表示颜色
enum Colour
{RED,BLACK
};
// 这里我们默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{// 这里更新控制平衡也要加入parent指针pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _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;
};

2：红黑树的插入

对于红黑树的插入我们一般分成两种情况，一种是叔节点（父节点的兄弟节点）存在为红；第二种是叔节点不存在或者为黑。

第一种情况很好处理，只需要变色就行，第二种情况需要变色加旋转（和AVLTree树的旋转一样，就不过多讲解了）

下面是实现代码

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->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}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* grandparent = parent->_parent;if (parent == grandparent->_left){Node* uncle = grandparent->_right;//uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}//uncle不存在或者uncle为黑else{if (cur == parent->_right){RL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{RR(parent);RL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}else//(parent==grandparent->_right){Node* uncle = grandparent->_left;//uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else//uncle不存在或者为黑{if (cur == parent->_right){RL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{RL(parent);RL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}}_root->_col = BLACK;return true;
}
//右单旋
void RR(Node* pParent)
{Node* subL = pParent->_left;Node* subLR = subL->_right;pParent->_left = subLR;if (subLR != nullptr){subLR->_parent = pParent;}subL->_right = pParent;Node* ppnode = pParent->_parent;pParent->_parent = subL;subL->_parent = ppnode;if (ppnode == nullptr){_root = subL;}else{if (ppnode->_left == pParent){ppnode->_left = subL;}else{ppnode->_right = subL;}}
}
//左单旋
void RL(Node* pParent)
{Node* subR = pParent->_right;Node* subRL = subR->_left;pParent->_right = subRL;if (subRL != nullptr){subRL->_parent = pParent;}subR->_left = pParent;Node* ppnode = pParent->_parent;pParent->_parent = subR;subR->_parent = ppnode;if (ppnode == nullptr){_root = subR;}else{if (ppnode->_left == pParent){ppnode->_left = subR;}else{ppnode->_right = subR;}}
}