红 黑 树

一、红黑树的概念

在 AVL 树中删除一个结点，旋转可能要持续到根结点，此时效率较低

红黑树也是一种二叉搜索树，通过在每个结点中增加一个位置来存储红色或黑色，并对结点的着色进行限制，使得该二叉搜索树的最长路径不超过最短路径的两倍，即红黑树是一颗近似平衡的二叉搜索树，他不像 AVL 树的平衡那么严格，所以红黑树在插入和删除时，也不需要大量的旋转，并且搜索效率差不了 AVL 多少

红黑树是一颗二叉搜索树并且满足如下规则：

• 每个节点不是红色就是黑色
• 根结点是黑色的
• 每个红结点的左右孩子一定是黑色
• 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点
• 叶结点都是黑色的(这里的叶结点指的是空节点)

根据上述规则可以得到：最短路径：全黑结点的路径，最长路径：一黑一红的路径，所以红黑树可以保证最长路径不超过最短路径的一半

二、红黑树的实现

1. 红黑树的存储结构

// 结点的颜色
enum Color { RED, BLACK };// 红黑树的结点
template<class K, class V>
struct RBTreeNode
{std::pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _color;	// 结点的颜色RBTreeNode<K, V>(const std::pair<K, V>& kv = std::pair<K, V>(K(), V())): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _color(RED)	// 为了方便树的结构调整，新结点默认为红色{}
};// 红黑树
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree<K, V>(): _root(nullptr){}private:Node* _root;
};

2. 红黑树的插入

首先按照二叉搜索树的方式插入结点，保证插入结点之后还是二叉搜索树，为了方便树的结构调整，插入结点默认为为红色，当插入结点完成之后，可能会违反红黑树的性质，此时有三种情况

• 插入结点的父节点是黑色：没有违反红黑树的性质

• 插入结点的父节点是红色，叔节点存在且为红：违反了红黑树的性质，此时需要对父节点和爷爷结点进行变色

由于父节点是红色的，所以爷爷结点一定存在且为黑，变色完之后，如果 g 结点是根结点，则将 g 结点变为黑色，否则将 g 结点所在的子树当做新插入的结点，继续向上调整

• 插入结点的父节点是红色，叔节点不存在或存在且为黑：违反了红黑树的性质，此时需要对爷爷结点所在的子树进行旋转然后再对结点进行变色

由于父节点是红色的，所以爷爷结点一定存在且为黑，变色完之后，子树的根结点是黑色的，不用继续向上调整

u 存在且为黑的情况，一定是由 u 存在且为红的情况继续向上调整而来的

// 右旋
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;if (pparent == nullptr) _root = subL;else{if (pparent->_left == parent) pparent->_left = subL;else pparent->_right = subL;}subL->_parent = pparent;
}// 左旋
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;if (pparent == nullptr) _root = subR;else{if (pparent->_left == parent) pparent->_left = subR;else pparent->_right = subR;}subR->_parent = pparent;
}// 插入
bool Insert(const std::pair<K, V>& kv)
{// 按照二叉搜索树的方式插入结点，保证该树插入结点之后还是二叉搜索树if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else return false;}cur = new Node(kv);if (parent->_kv.first > kv.first) parent->_left = cur;else parent->_right = cur;cur->_parent = parent;// 更新颜色while (parent && parent->_color == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;// u 存在且为红// u 不存在或存在且为黑//		p 为 g 的左，cur 为 p 的左 右单旋//		p 为 g 的左，cur 为 p 的右 先左旋再右旋if (uncle && uncle->_color == RED){grandfather->_color = RED;parent->_color = BLACK;uncle->_color = BLACK;// 继续判断是否违反了红黑树的性质cur = grandfather;parent = grandfather->_parent;}else{if (parent->_left == cur){RotateR(grandfather);grandfather->_color = RED;parent->_color = BLACK;}else{RotateL(parent);RotateR(grandfather);grandfather->_color = RED;cur->_color = BLACK;}}}else{Node* uncle = grandfather->_left;// u 存在且为红// u 不存在或存在且为黑//		p 为 g 的右，cur 为 p 的右 左单旋//		p 为 g 的右，cur 为 p 的左 先右旋再左旋if (uncle && uncle->_color == RED){grandfather->_color = RED;parent->_color = BLACK;uncle->_color = BLACK;// 继续判断是否违反了红黑树的性质cur = grandfather;parent = grandfather->_parent;}else{if (parent->_right == cur){RotateL(grandfather);grandfather->_color = RED;parent->_color = BLACK;}else{RotateR(parent);RotateL(grandfather);grandfather->_color = RED;cur->_color = BLACK;}}}}_root->_color = BLACK;return true;
}