国外网站打开速度慢的原因,象山seo的优化,上海浦东做网站公司,wordpress整站源码文章目录 红黑树概念规则为什么最长路径不超过最短路径的二倍#xff1f;红黑树的时间复杂度红黑树的结构插入叔叔节点情况的讨论只变色(叔叔存在且为红)抽象的情况变色单旋#xff08;叔叔不存在或叔叔存在且为黑#xff09;变色双旋#xff08;叔叔不存在或叔叔存在且为黑… 文章目录 红黑树概念规则为什么最长路径不超过最短路径的二倍红黑树的时间复杂度红黑树的结构插入叔叔节点情况的讨论只变色(叔叔存在且为红)抽象的情况变色单旋叔叔不存在或叔叔存在且为黑变色双旋叔叔不存在或叔叔存在且为黑 判断是不是红黑树代码 红黑树
概念
红黑树保证了最长的路径不超过最短路径的二倍
规则
根节点是黑色的每个节点不是红色就是黑色如果有一个节点是红的那么它的两个孩子都是黑的就是说一条路径不会有两个连续的红色节点不会出现红红其他情况可以出现红黑黑黑黑红对于每个节点到其空节点上的简单路径每一条路径上都有相同数量的黑色节点
为什么最长路径不超过最短路径的二倍
最短路径就是全黑最长路径就是一黑一红的组合假设每条路径有x个黑色的节点 最短x 最长2*x 这是最极端的场景其它的场景都在最短和最长之间 比如下面这幅图 最短3 最长4 最长路径不超过最短路径的2倍
路径的条数要算到走到空的场景9条路径 其它书里可能出现下面的图 这样是为了计算路径的条数更加方便防止算错 加了这样的空节点也不违反规则
红黑树的时间复杂度
假设节点个数为N 用极端的场景来算 红黑树最短路径的高度为2^h-1 N, h log(N1) 最长路径的高度为2^2h-1 N,h (log(N1))/2
其实最快可以近似为logN,最慢可以近似为2*logN 整体上时间复杂度还是logN,只是没有AVL树那么接近logN
红黑树的结构
// 枚举红黑树的颜色
enum Colour
{RED,BLACK
};// 按Key/Value的模式实现
templateclass K,class V
class RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Colour _col;RBTreeNode(const pairK,V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};templateclass K,class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:private:Node* _root nullptr;
};插入
插入红色节点还是黑色节点呢
插入红色节点可能违反规则3红色节点的父亲可能是红色节点父亲是黑色节点就不用管插入时黑色节点必然会违反规则4每条路径上都要有相同数量的黑色节点
按二叉搜索树的规则插入不违反上面的4条规则如果是空树插入则插入黑色节点。如果是非空树插入必然插入红色因为黑色违反规则4插入红色节点如果父亲是黑色节点不违反规则插入结束插入红色节点如果父亲是红色节点违反规则3。 插入节点c必然是红色父亲节点p也是红色因为之前也要遵循红黑树的规则所以爷爷节点g也要是黑色是红色之前就违反规则了。所以c,p,g三个节点的颜色是固定的。 先在关键看叔叔节点u了u可以是红色也可以是黑色所以要分情况讨论叔叔节点的颜色。
叔叔节点情况的讨论
只变色(叔叔存在且为红)
c为红p为红g为黑u存在且为红。将p变黑因为红红违反了规则3p必须变红。u也变黑g变红。把g当做c继续向上更新需要继续向上更新是因为如果g的父亲还是红色就需要继续向上处理如果g的父亲是黑色就处理结束如果g就是整棵树的根再把g变为黑色。
抽象的情况
叔叔存在且为红a和b是抽象出来的子树a和b要满足下面的模版爷爷的两个孩子都是红色才满足只变色 抽象的情况: bh(black height),bh 0 bh 1 bh 2
变色单旋叔叔不存在或叔叔存在且为黑
p,c是红g是黑u不存在或者u存在且为黑
u不存在c只能是新增节点如果c不是新增节点的话它只能是之前变色变过来的那它之前就是黑色黑色节点的数量就不对。右旋把父亲节点变黑g变红u存在且为黑c一定不是新增如果c是新增那么新增前黑色的数量不对c之前就是黑色的现在变成了红色因为进行了变色。右旋父亲变为黑色爷爷变为红色不用继续往上更新因为黑黑可以红黑也可以就不用管了。
变色双旋叔叔不存在或叔叔存在且为黑
p,c是红g是黑u不存在或者u存在且为黑
u不存在c只能是新增节点如果c不是新增节点的话它只能是之前变色变过来的那它之前就是黑色黑色节点的数量就不对。u存在且为黑c一定不是新增如果c是新增那么新增前黑色的数量不对c之前就是黑色的现在变成了红色因为进行了变色。左单旋然后右单旋父亲节点不变色cur节点由红色变成黑色grandfather节点由黑色变成红色。不用继续往上更新因为黑黑可以红黑也可以就不用管了。 关键看叔叔
判断是不是红黑树
用4个规则进行判断满足这四个规则就满足最长路径不超过最短路径的两倍。
规则1枚举了颜色就实现了节点不是黑色就是红色规则2直接检查根的颜色是不是黑色就可以了规则3不能是连续的红色节点遇到红色节点就检查孩子不太方便如果孩子不存在就更不方便了并且孩子可能有两个。但是检查父亲节点的颜色就方便多了遇到红色节点就检查父亲节点的颜色。规则4是每条路径的黑色节点的数量必须相同。用前序遍历检查用形参blacknum记录到当前节点的黑色节点的数量遇到黑色节点就走到空就计算完一条路径的黑色节点的数量。用任意一条的黑色节点的数量作为参考值依次比较。
// 判断红黑树是否平衡
bool IsBalance()
{// 根节点是空if (_root nullptr)return true;// 根节点非空且是红色if (_root-_col RED)return false;// 算出一条路径上黑色节点的个数作为参考值Node* cur _root;// 参考值int blacknum 0;while (cur){if (cur-_col BLACK){blacknum;}// 就走最左边的一条路径cur cur-_left;}return Check(_root,0,blacknum);
}private:
bool Check(Node* root, int blacknum, const int refnum)
{// refnum参考值if (root nullptr){// 当前路径走完了if (blacknum ! refnum){cout 存在黑色节点的数量不相等的路径 endl;return false;}return true;}// 规则3if (root-_col RED root-_parent-_col RED){cout 存在连续两个红节点 endl;return false;}if (root-_col BLACK){blacknum;}return Check(root-_left, blacknum, refnum) Check(root-_right, blacknum, refnum);
}代码
#pragma once
#includeiostream
using namespace std;// 枚举红黑树的颜色
enum Colour
{RED,BLACK
};// 按Key/Value的模式实现
templateclass K,class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Colour _col;RBTreeNode(const pairK,V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};templateclass K,class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:bool Insert(const pairK, 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 if (parent-_kv.first kv.first){parent-_left cur;}// 链接父亲节点cur-_parent parent;// parent是红色,出现了连续的红色节点,需要向上调整// 调整之后cur是根,cur的parent是nullptrwhile (parentparent-_col RED){Node* grandfather parent-_parent;if (grandfather-_left parent){// g// p uNode* uncle grandfather-_right;if (uncle uncle-_col RED){// 变色是为了处理连续的红节点,保证黑节点的数量不变,// 向上继续调整是因为grandfather的节点可能是黑节点就结束,// 可能是红节点就继续向上处理parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else{// uncle不存在或uncle存在且为黑// g// p u// c// 右单旋if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// 双旋// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else{// g// u pNode* uncle grandfather-_left;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上更新cur grandfather;parent cur-_parent;}else{// uncle不存在或者存在且是黑// g// u p// c// 左单旋if (parent-_right cur){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p// c// 双旋RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}// 无论如何结束之后根都是黑色的_root-_col BLACK;return true;}// 右单旋,旋转点是parentvoid RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;// b可能为空树if (subLR ! nullptr)subLR-_parent parent;// 记录parent的parentNode* pParent parent-_parent;subL-_right parent;parent-_parent subL;// 1. 10是这棵树的总根if (parent _root){_root subL;subL-_parent nullptr;}else{// 2. 10是这棵树的局部根// pParent左可能是parent,右也可能是parentif (pParent-_left parent){pParent-_left subL;}else{pParent-_right subL;}subL-_parent pParent;}}// 左单旋,旋转点是parentvoid RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;// b不是空树if (subRL)subRL-_parent parent;// 记录父亲节点的父亲节点Node* pParent parent-_parent;subR-_left parent;parent-_parent subR;// 1. 10是这棵树的总根if (_root parent){_root subR;subR-_parent nullptr;}else{// 2. 10是这棵树的局部根if (pParent-_left parent){pParent-_left subR;}else{pParent-_right subR;}subR-_parent pParent;}}void InOrder(){_InOrder(_root);cout endl;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return nullptr;}bool IsBalance(){// 根节点是空if (_root nullptr)return true;// 根节点非空且是红色if (_root-_col RED)return false;// 算出一条路径上黑色节点的个数作为参考值Node* cur _root;// 参考值int blacknum 0;while (cur){if (cur-_col BLACK){blacknum;}// 就走最左边的一条路径cur cur-_left;}return Check(_root,0,blacknum);}private:bool Check(Node* root, int blacknum, const int refnum){// refnum参考值if (root nullptr){// 当前路径走完了if (blacknum ! refnum){cout 存在黑色节点的数量不相等的路径 endl;return false;}return true;}// 规则3if (root-_col RED root-_parent-_col RED){cout 存在连续两个红节点 endl;return false;}if (root-_col BLACK){blacknum;}return Check(root-_left, blacknum, refnum) Check(root-_right, blacknum, refnum);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}int _Height(Node* root){if (root nullptr)return 0;int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}int _Size(Node* root){if (root nullptr)return 0;return _Size(root-_left) _Size(root-_right) 1;}private:Node* _root nullptr;
};#define _CRT_SECURE_NO_WARNINGS#includeRBTree.hvoid TestRBTree1()
{RBTreeint, int t;// 常规的测试用例//int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e,e });}t.InOrder();cout t.IsBalance() endl;
}int main()
{TestRBTree1();return 0;
}
