【数据结构】红黑树（RBTree）

news/2024/7/27 11:18:19/文章来源:https://blog.csdn.net/m0_73865858/article/details/136352322

介绍

概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

性质

每个结点不是红色就是黑色。
根节点是黑色的。
如果一个节点是红色的，则它的两个孩子结点是黑色的。（不能出现连续红色）
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

红黑树的插入调整

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论

情况一： cur为红，p为红，g为黑，u存在且为红

在这里插入图片描述
u存在且为红，p，u变黑，g变红。
如果gg为黑，则不用处理了，gg为红，令g为cur，继续向上处理

情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑（一定由情况一变化调整而来）

在这里插入图片描述

p为g的左孩子，cur为p的左孩子，则进行右单旋
p为g的右孩子，cur为p的右孩子，则进行左单旋

情况三：比情况二多了次旋转而已

在这里插入图片描述
代码：

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 (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//u存在且为红，变色处理，并继续往上处理if (uncle && uncle->_col == RED){parent->_col = BlACK;uncle->_col = BlACK;grandfather->_col = RED;//continue to modifycur = grandfather;parent = cur->_parent;}//u不存在或u存在且为黑，旋转+变色else{//   g//  p  u//cif (cur == parent->_left){RotateR(grandfather);parent->_col = BlACK;grandfather->_col = RED;}else{//	  g//  p   u//    cRotateL(parent);RotateR(grandfather);parent->_col = RED;grandfather->_col = RED;cur->_col = BlACK;}break;}}else{Node* uncle = grandfather->_left;//u存在且为红，变色处理，并继续往上处理if (uncle && uncle->_col == RED){parent->_col = BlACK;uncle->_col = BlACK;grandfather->_col = RED;//continue to modifycur = grandfather;parent = cur->_parent;}//u不存在或u存在且为黑，旋转+变色else{//   g//  u  p//       cif (cur == parent->_right){RotateL(grandfather);parent->_col = BlACK;grandfather->_col = RED;}else{//	  g//  u   p//    cRotateR(parent);RotateL(grandfather);parent->_col = RED;grandfather->_col = RED;cur->_col = BlACK;}break;}}_root->_col = BlACK;}return true;}

红黑树的拷贝构造

RBTree(const RBTree& rb){_root = CopyTree(rb._root, nullptr);}Node*  CopyTree(Node* rbroot,Node* parent){if (rbroot == nullptr)return nullptr;Node* newroot = new Node(rbroot->_kv);newroot->_col = rbroot->_col;newroot->_parent = parent;newroot->_left = CopyTree(rbroot->_left, newroot);newroot->_right = CopyTree(rbroot->_right, newroot);return newroot;}

set和map

RBTree的Iterator

template<class T,class Ref,class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator != (const Self & s){return _node != s._node;}Self& operator++(){if (_node->_right){//1.右不为空，找右子树的最左节点Node* subleft = _node->_right;while (subleft->_left){subleft = subleft->_left;}_node = subleft;}else{//2.右为空，沿着到根的路径，找孩子是父亲左的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node->_left){//左不为空，找左子树的最右节点Node* subright = _node->_left;while (subright->_right){subright = subright->_right;}_node = subright;}else{//左为空，找孩子是父亲的右的祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};
template<class K,class T,class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T, T&, T*> iterator;typedef __RBTreeIterator<const T, const T&, const T*> const_iterator;iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}