红黑树(创建 插入 测试验证)

一 红黑树的概念与规则

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

  红黑树的性质：

 1. 每个结点不是红色就是黑色

 2. 根节点是黑色的

 3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 

 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点

 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点 个数的两倍？   

这里根据第三条和第四条性质 红黑树理想中最短路径为全黑 数目为  最长路径为一黑一红 数目为最短路径*2  这只是理想状态下  一般是不会造成这种情况  所以最长路径 <= 2*最短路径  

相较于avl树的平衡因子控制 红黑树的颜色控制是更简单的

enum colour 
{red,black
};
template <class K, class V>
struct rbtnode//搜索二叉树不支持修改  中序遍历是有序的
{pair<int, int> _kv;rbtnode<K, V>* _left;rbtnode<K, V>* _right;rbtnode<K, V>* _parent;colour _col;avltnode(const pair<int, int>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};

template<class K, class V>
class rbTree
{typedef rbtnode<K, V> node;
public:rbTree() = default;
private:node* _root = nullptr;
};

二 插入

   接下来考虑插入的结点默认颜色是红的好还是黑的好 

由于规则四限制每条路径上的黑色节点数目必须保持一致  所以如果插入一个黑色节点就破坏了规则  如果插入一颗红色 如果其父亲是黑色那么就没有破坏规则  如果是红色 就破坏了规则  从这点上考虑  所以我们选择插入节点颜色默认为红色  

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);cur->_col = red;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;return true;
}

接下来我们具体的分析一下红黑树的插入规则 

红黑树的改变通过观察红黑树结点的父亲 爷爷 叔叔结点  其中叔叔节点对于进行如何的调整非常重要

情况一 abcde都为空 

我们这里观察的是高度 不是颜色  cur是新增节点  对于两个连续的红色节点 会有两种调整方式 一种是旋转 一种是变色  其中我们优先进行变色  但是要具体决定是根据叔叔节点的情况进行选择的

情况1: cur为红，p为红，g为黑，u存在且为红   这里我们要将叔叔和父亲变黑 同时要将爷爷变红

之后继续向上调整  那么为什么要将爷爷变黑呢  因为如果爷爷是子树节点 那么如果只将父亲和叔叔变黑 那么在这个子树局部路径上就会比其他，路径上多一个黑节点 这样就破坏了规则四 、

 情况2：cur位置不是新增结点 cur之前是黑色 cde是一个拥有一个黑色结点的红黑子树  ab分别是一个红色节点  新增节点是在ab的任意位置

根据上图  新增节点之后  父亲和叔叔都变黑 爷爷变红  之后将爷爷当成cur节点 再次进行判断cur的父亲 爷爷 叔叔结点  

情况二   cur为红，p为红，g为黑，u不存在/u存在且为黑

  情况1  如果u不存在 abcde都为空 cur是新增 

这时无论怎么变颜色 都无法保证路径黑色节点一致 这时就需要用到旋转   对于下图  先对其进行右旋转 之后 将父亲变为黑色 将爷爷节点变为红色 

情况2 如果叔叔存在且为黑   de为空或者为红  c是一个右黑色节点的红黑子树

 cur节点时黑  是由情况一变过来导致变为红色的  ab是一个红色节点  新增节点在ab任意位置上

情况3 进行左单旋之后变色

情况4 进行左旋之后右旋之后进行变色

情况5 进行右旋之后左旋之后进行变色

二  接下来我们写实现代码 

insert插入

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);cur->_col = red;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;return true;
}

1.这就是插入一个搜索二叉树节点的代码  如果是插入根节点 则设置为黑色 如果出入的是其他节点就设置为红色  同时按照比较值大小插入在对应的位置  

2.接下来就进行对于颜色的判断以及维护 

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);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* grandfather = parent->_parent;if (parent == grandfather->_left){node* uncle = grandfather->_right;if (uncle->_col == red){uncle->_col = parent->_col = black;grandfather->_col = red;cur = grandfather;parent = grandfather->_parent;}}}_root->_col = black;return true;
}

这里我们首先对parent的颜色进行判断 如果是红色 就说明需要进行维护  如果是黑色就结束 结束维护后将根节点再次设置为黑色 这里是为了防止维护颜色时可能会将根节点变为红色  

情况一 ：这里首先对uncle如果是红色 那么只需要变色维护 将叔叔节点和父亲节点变为黑色 将爷爷节点变为红色  之后将cur节点变为爷爷节点 parent变为爷爷的父节点  之后再次进行循环判断  

情况二 如果判断叔叔节点 不存在   那么就需要进行旋转 这里也需要判断是单旋转还是双旋转 

  这里如果三个节点时直线型 那么就是单旋转之后将父节点变为黑色将爷爷节点变为红色         如果三个节点是折线型那么就双旋转  之后将cur节点变为黑色 将爷爷节点变为红色       

情况三 如果判断叔叔节点存在且为黑色 这里的情况不是直接产生  这里是由于情况一产生并且维护后继续第二次维护cur节点的时候会发生的情况   这里也是分单旋转和双旋转  也是通过cur parent grandfather  三个节点时直线型 则为单旋转如果是折线型就是双选转    单旋转完成后将父节点变为黑色将爷爷节点变为红色    双旋转之后将cur节点变为黑色 将爷爷节点变为红色     

这里我们将情况二和情况三归为一种情况

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);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* grandfather = parent->_parent;if (parent == grandfather->_left){node* uncle = grandfather->_right;if (uncle&&uncle->_col == red){uncle->_col = parent->_col = black;grandfather->_col = red;cur = grandfather;parent = grandfather->_parent;}else//叔叔不存在或叔叔存在且为黑{if (cur == parent->_left){rotater(grandfather);parent->_col = black;grandfather->_col =red;}else{rotatel(parent);rotater(grandfather);cur->_col = black;grandfather->_col = red;}break;}}else {node* uncle = grandfather->_left;if (uncle&&uncle->_col == red){uncle->_col = parent->_col = black;grandfather->_col = red;cur = grandfather;parent = grandfather->_parent;}else//叔叔不存在或叔叔存在且为黑{if (cur == parent->_right){rotatel(grandfather);parent->_col = black;grandfather->_col = red;}else{rotater(parent);rotatel(grandfather);cur->_col = black;grandfather->_col = red;}break;}}}_root->_col = black;return true;
}

   

三 接下来我们对insert代码进行测试

void testrbtree()
{rbTree<int, int> t;int a[] = { 16,3,7,11,9,26,18,14,15 };int b[] = { 4,2,6,1,3,5,15,7,16,14 };for (auto e : a){t.insert({ e,e });}t.inorder();}

这里只能证明它是一个搜索树 平衡还需要另外证明

bool isbalance()
{if (_root == nullptr)return true;if (_root->_col == red){return false;}// 参考值int refNum = 0;node* cur = _root;while (cur){if (cur->_col == black){++refNum;}cur = cur->_left;}return check(_root, 0, refNum);
}
private:bool check(node* root, int blackNum, const int refNum){if (root == nullptr){//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}if (root->_col == red && root->_parent->_col == red){cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == black){blackNum++;}return check(root->_left, blackNum, refNum)&& check(root->_right, blackNum, refNum);} 

 这里的首先计算一路的黑色节点数量用来作为参考值  同时进入check函数来进行检查  在check函数中通过递归来检查整个树的每条路   单检查到空节点的时候开始进行检查  

void testrbtree()
{rbTree<int, int> t;int a[] = { 16,3,7,11,9,26,18,14,15 };int b[] = { 4,2,6,1,3,5,15,7,16,14 };for (auto e : b){t.insert({ e,e });}t.inorder();cout << t.isbalance()<<endl;}

四  红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($log_2 N$)，红黑树不追 求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数， 所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红 黑树更多。