红黑树的学习

本文主要是介绍红黑树的学习，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.2 红黑树的性质

enum Colour
{Red, Black
};
template<class K,class V>
struct  RBTreeNode
{pair<K,V> _kv;RBTreeNode<K, V>* left;RBTreeNode<K, V>* right;RBTreeNode<K, V>* parent;Colour col;RBTreeNode(const pair<K, V> _data):_kv(_data), left(nullptr), right(nullptr), parent(nullptr){}
};template<class K,class V>
class RBTree
{typedef RBTreeNode<K,V> Node;
private:
Node* root;
}

1.4 红黑树结构

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了

与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft

域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点

1.5 红黑树的插入

<1>: 我们默认插入的时候 都是红色结点 ，这是为什么？如果每次插入是黑色结点，我都得协调每条路径的黑色结点，如果是红色，我只需要考虑，它的父亲是不是红色结点，在进行调色

<2>. 如果父亲结点是红色，那么我们有两种情况

第一种：叔叔（父亲的兄弟结点，也就是父亲的父亲，它的除了父亲的孩子）存在且为红色结点，那么我们就需要把叔叔和父亲一起调成黑色，接着再往上调整父亲的父亲的结点颜色

第二种  爷爷是黑色的  叔叔 不存在 或者 是黑色结点 那么我们就要进行旋转了，旋转之后进行调整颜色

同样我们这里的旋转也分为单旋转还是双旋

首先介绍第一种情况

cur为新插入的结点，然后父亲和叔叔都是红色，我们把他两变成黑色，然后g结点改成红色，再把g结点给cur赋值，再进行调色

！第二种情况叔叔是黑色的只有在第一种情况往上调整的时候才会出现，也就是说直接插入是不会存在这种情况的

  假设cur是新插入的结点，那么第二层，一个黑的一个红的，都不符合简单路径黑色结点数量一致。

然后我们这时候就要旋转了，这时候一眼就能看出来，右旋转，g 结点变红，p成根，变成黑色，旋转就不用再往上改颜色了。

我们来举个双旋的例子，其实有了AVL树的学习，这些一眼就能看出来怎么旋转

我们这个还有略微不同，AVL树是在旋转里面就进行了平衡因子的修正，我们呢是在旋转完之后，我们再进行调色。总结一下：情况二 单旋是祖孙三代在同一条线上，双旋是祖孙三带两个在一条线上。所以我们根据是从上到左下角的线呢，还是从上到右下角的线呢。进行右旋或者左旋，左右旋或者是右左旋（这几个顺序是一以对应的，或者前面的对前面，或者后面的对后面）

bool insert(const pair<K, V>& kv)
{if (root == nullptr){root = new Node(kv);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{cout << "已经重复了" << endl;return false;}}cur = new Node(kv);cur->col = Red;if (parent->_kv.first > kv.first){parent->left = cur;}else{parent->right = cur;}cur->parent = parent;while (parent && parent->col == Red){Node* grandfather = parent->parent;Node* uncle = nullptr;//  g//u   p//      cif (parent == grandfather->right){uncle = grandfather->left;if (uncle && uncle->col == Red)//叔叔是红色的 ，就改变颜色{parent->col = uncle->col = Black;grandfather->col = Red;cur = grandfather;//改完色之后 更新成爷爷为插入的结点了parent = cur->parent;}else//uncle 为黑色 或者 不存在 就看单旋还是双旋{//统一一根线是单旋 if (cur == parent->right){grandfather->col = Red;parent->col = Black;RotateL(grandfather);	 }//   g// u   p//   celse{RotateR(parent);RotateL(grandfather);cur->col = Black;grandfather->col = Red;}break;}}else{//   g//  p  u//cuncle = grandfather->right;if (uncle && uncle->col == Red)//叔叔是红色的 ，就改变颜色{parent->col = uncle->col = Black;grandfather->col = Red;cur = grandfather;//改完色之后 更新成爷爷为插入的结点了parent = cur->parent;}else//uncle 为黑色 或者 不存在 就看单旋还是双旋{//统一一根线是单旋 if (cur == parent->left){grandfather->col = Red;parent->col = Black;RotateR(grandfather);}//   g// p   u//   celse{RotateL(parent);RotateR(grandfather);cur->col = Black;grandfather->col = Red;}break;}}}root->col = Black;return true;}
void RotateL(Node* parent)
{Node* subR = parent->right;Node* subRL = subR->left;parent->right = subRL;if (subRL)subRL->parent = parent;Node* PParent = parent->parent;subR->left = parent;parent->parent = subR;if (PParent){subR->parent = PParent;if (PParent->left == parent)PParent->left = subR;elsePParent->right = subR;}else{subR->parent = nullptr;root = subR;}}void RotateR(Node* parent)
{Node* subL = parent->left;Node* subLR = subL->right;parent->left = subLR;if (subLR)subLR->parent = parent;Node* PParent = parent->parent;subL->right = parent;parent->parent = subL;if (PParent == nullptr){root = subL;}else{if (PParent->right == parent)PParent->right = subL;elsePParent->left = subL;}subL->parent = PParent;}

1.6红黑树的验证 红黑树的检测分为两步：

	bool _IsBalance(Node* _root){if (_root == nullptr)return true;if (_root->col == Red)return false;Node* cur = _root;int  count = 0;while (cur){if (cur->col==Black){count++;}cur = cur->left;}return check(count, 0, _root);}bool check(int count, int num, Node* _root){if (_root == nullptr){if (count != num){cout << "路径长度不一致" << endl;cout << count << "::" << num << endl;return false;}return true;}if (_root->col == Red){if (_root->parent->col == Red){cout<<"连续红色"<<endl;return false;}}if (_root->col == Black){num++;}return check(count, num, _root->left) && check(count, num, _root->right);}

这篇关于红黑树的学习的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！