社区教育网站建设项目计划书,别人用我公司营业执照备案做网站,网站实名,怎么进行网站设计和改版目录 介绍----什么是红黑树 甲鱼的臀部----规定
分析思考
绘图解析代码实现
节点部分
插入部分分步解析
●父亲在祖父的左#xff0c;叔叔在祖父的右#xff1a;
●父亲在祖父的右#xff0c;叔叔在祖父的左#xff1a;
测试部分
整体代码 介绍----什么是红黑树
红…目录 介绍----什么是红黑树 甲鱼的臀部----规定
分析思考
绘图解析代码实现
节点部分
插入部分分步解析
●父亲在祖父的左叔叔在祖父的右
●父亲在祖父的右叔叔在祖父的左
测试部分
整体代码 介绍----什么是红黑树
红黑树基于二叉搜索树它和AVL树一样避免了二叉搜索树中极端场景单边树的情况保证了检索的效率。红黑树允许最长路径是最短路径的二倍相较于AVL树而言是近似于平衡的状态但是减少了旋转的次数。 甲鱼的臀部----规定
●每个节点都有颜色不是红色就是黑色。
●根节点一定是黑色的。
●不能连续出现两个红色的节点。
●每条路径上的黑色节点数量相同。
●每个空节点都是黑色的。
●最多允许一条路径上的节点是另一条路径上节点的二倍。
分析思考
节点默认颜色应该选红色还是黑色为什么 答插入红色可能会出现连续的红色节点插入黑色会改变当前路径上的黑色节点数。选择默认插入节点为红色的原因是插入后的影响会小一些当父节点是黑色时不用调整。相反的黑色节点的插入一定会违反红黑树的规则。 满足上述特性为什么能保证最长路径不会超过最短路径的2倍 答这里要关注红黑树的两个特性红色节点的孩子节点一定是黑色每条路径的黑色节点树相同。也就说最长路径是红色节点和黑色交替最短路径是全黑节点。这样一来最长路径和最短路径间的差距就控制在了规定范围内。 绘图解析代码实现
节点部分
三叉链结构分别指向左右孩子和父亲节点数据方面存储键值对除此之外还需要一个记录节点颜色的变量。 enum Color
{RED,BLACK
};templateclass K,class V
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pairK, V _kv;Color _color;RBTreeNode(pairK, V kv, Color color RED):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_color(color){}
};
插入部分分步解析
红黑树是二叉搜索树插入节点的规则和二叉搜索的特点一样 typedef RBTreeNodeK,V Node;bool inster(const pairK, 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);cur-_color RED;if (parent-_kv.first kv.first){parent-_left cur;cur-_parent parent;}else{parent-_right cur;cur-_parent parent;}//节点插入后需要检查红黑树的特性有没有被破坏掉//......}
上述我们谈论过新节点的颜色默认为红色的原因那么接下来的插入如果新节点插入后其父节点的颜色是黑色那么直接插入即可。如果其父节点的颜色为红色那么就出现了两个红色节点出现的情况此时就需要进行调整 关注红黑树的处理方法重点关注这样的几个节点cur(新增节点)、parent(父亲节点)、uncle(叔叔节点)、grandfather祖父节点。
当节点的插入违反了红黑树“龟腚”时对应不同的情况分别处理
●父亲在祖父的左叔叔在祖父的右
情况1cur为红parent红色叔叔节点存在且是红色祖父是黑色 如上图所示情况1的处理方法就是将父亲和叔叔的节点变为黑色祖父的节点变为红色。对于祖父为什么要变红是基于这样的考虑我们当前的处理很可能只是在子树当中如果祖父节点保持黑色不变对于子树这两条路径而言增加了黑色节点这样一来就“拆东墙补了西墙”又违反了另一条规则。如果祖父节点是根节点改为红色当然是不合理的我们在最后做下强制处理即可。 注意这种情况可能是局部的处理当祖父节点变红且不是根节点时可能会破坏规则所以针对情况1需要继续向上查找也就是将祖父节点看成新增节点祖父的父亲看做新增节点的父节点继续向上更新检查树结构。 if (uncle uncle-_color RED){//情况1叔叔节点存在且是红色的parent-_color uncle-_color BLACK;grandfater-_color RED;//更新cur和parent的位置cur grandfater;parent cur-_parent;}
情况2cur为红插入或者调整后和父亲祖父为一条直线parent红色叔叔不存在或者叔叔是黑色祖父是红色。
当叔叔不存在时这种情况较好分析新节点插入后左边高左边高度超过右边的2倍进行一次右单旋祖父变成红色父亲变为黑色这颗树调整完毕不管它是不是子树都不会向上影响。 叔叔存在且为黑色观察下图每条路径上的黑色节点数量不相等所以cur的位置应该是从黑色调整为的红色。 注意这里不要受图示的影响感觉uncle路径上的黑节点好像是多一个。调整前后的每条路径数量都是相等的想象小三角中有着不同的结构就可以了。
叔叔的存在与否只是分析的过程不同它们的代码处理方式是一样的 //在一条线上if (parent-_left cur){//情况2叔叔节点不存在或者存在是黑色的//右单旋RotaR(grandfater);parent-_color BLACK;grandfater-_color RED;} 情况3cur为红插入或者调整后和父亲祖父为线一条折parent红色叔叔不存在或者叔叔是黑色祖父是红色。
uncle不存在 uncle存在: if(cur parent-_left){//情况3,叔叔节点存在是黑色的在一条折线上RotaL(parent);RotaR(grandfater);cur-_color BLACK;grandfater-_color RED;}
●父亲在祖父的右叔叔在祖父的左
处理大思路和上述一致只是叔叔和父亲交换了位置不在画图分析列举处理要点 情况1叔叔存在且为红色叔叔和父亲变黑祖父变红。向上继续查找。 if (uncle uncle-_color RED){//情况1叔叔存在且是红色parent-_color uncle-_color BLACK;grandfater-_color RED;//继续向上更新cur grandfater;parent cur-_parent;}
情况2叔叔不存在或者存在为黑色cur的位置和父亲祖父是一条直线右边高以祖父为轴点左单旋。祖父变红父亲变黑。 //在右边插入if (parent-_right cur){//进行一个左单旋RotaL(grandfater);//父亲的颜色变成黑色parent-_color BLACK;//祖父的的颜色变成红色grandfater-_color RED;}
情况3叔叔不存在或者存在为黑色cur的位置和父亲祖父是一条折线先以父亲为轴右单旋在以祖父为轴点左单旋祖父变红cur变黑。 if(cur parent-_left)//左边插入{//右单旋RotaR(parent);//左单旋RotaL(grandfater);//改变颜色grandfater-_color RED;cur-_color BLACK;}
测试部分
因为红黑树是二叉搜索树在测试时很可能会有隐式的错误比较难发现所以需要下面的测试接口对红黑树的特性进行检查检查是否有连续的红色节点出现每条路径上的黑色节点是否相等。
bool check(Node* root,int num,int BLACKNUM){if (root nullptr){if (num ! BLACKNUM){cout 某条路径上的黑色节点和其他路径不相等 endl;return false;}return true;}if (root-_color RED root-_parent-_color RED){cout 连续出现两个红色节点 endl;return false;}if (root-_color BLACK){num;}return check(root-_left, num, BLACKNUM)check(root-_right, num, BLACKNUM);}bool IsBalance(){if (_root nullptr){return false;}//根节点的颜色一定要是黑色if (_root-_color ! BLACK){return false;}Node* ret _root;int _blacknum 0;while (ret){if (ret-_color BLACK){_blacknum;}ret ret-_left;}return check(_root,0,_blacknum);}
整体代码
#include time.h
enum Color
{RED,BLACK
};templateclass K,class V
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pairK, V _kv;Color _color;RBTreeNode(pairK, V kv, Color color RED):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_color(color){}
};template class K,class V
class RBTee
{
public:typedef RBTreeNodeK,V Node;bool inster(const pairK, 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);cur-_color RED;if (parent-_kv.first kv.first){parent-_left cur;cur-_parent parent;}else{parent-_right cur;cur-_parent parent;}//插入的节点默认是红色的while (parent parent-_color RED){Node* grandfater parent-_parent;if (parent grandfater-_left){Node* uncle grandfater-_right;if (uncle uncle-_color RED){//情况1叔叔节点存在且是红色的parent-_color uncle-_color BLACK;grandfater-_color RED;//更新cur和parent的位置cur grandfater;parent cur-_parent;}else {//左边新增if (parent-_left cur){//情况2叔叔节点存在是黑色的在一条线上//右单旋RotaR(grandfater);parent-_color BLACK;grandfater-_color RED;}//右边新增else{//情况3,叔叔节点存在是黑色的在一条折线上RotaL(parent);RotaR(grandfater);cur-_color BLACK;grandfater-_color RED;}//树进行了旋转调整已经平衡跳出循环break;}}else //parent在grandfater的右边{Node* uncle grandfater-_left;if (uncle uncle-_color RED){//情况1叔叔存在且是黑色parent-_color uncle-_color BLACK;grandfater-_color RED;//继续向上更新cur grandfater;parent cur-_parent;}else//uncle的颜色是黑色{//在右边插入if (parent-_right cur){//进行一个左单旋RotaL(grandfater);//父亲的颜色变成黑色parent-_color BLACK;//祖父的的颜色变成红色grandfater-_color RED;}else//左边插入{//右单旋RotaR(parent);//左单旋RotaL(grandfater);//改变颜色grandfater-_color RED;cur-_color BLACK;}break;}}}_root-_color BLACK;return true;}void Inorder(){_Inorder(_root);}bool check(Node* root,int num,int BLACKNUM){if (root nullptr){if (num ! BLACKNUM){cout 某条路径上的黑色节点和其他路径不相等 endl;return false;}return true;}if (root-_color RED root-_parent-_color RED){cout 连续出现两个红色节点 endl;return false;}if (root-_color BLACK){num;}return check(root-_left, num, BLACKNUM)check(root-_right, num, BLACKNUM);}bool IsBalance(){if (_root nullptr){return false;}//根节点的颜色一定要是黑色if (_root-_color ! BLACK){return false;}Node* ret _root;int _blacknum 0;while (ret){if (ret-_color BLACK){_blacknum;}ret ret-_left;}return check(_root,0,_blacknum);}
private:void _Inorder(Node* root){if (root nullptr){return ;}_Inorder(root-_left);cout root-_kv.first : root-_kv.first endl;_Inorder(root-_right);}void RotaL(Node* pparent){Node* subR pparent-_right;Node* subRL subR-_left;pparent-_right subRL;if (subRL){subRL-_parent pparent;}Node* pNode pparent-_parent;pparent-_parent subR;subR-_left pparent;if (pNode nullptr){_root subR;_root-_parent nullptr;}else{if (pNode-_left pparent){pNode-_left subR;}else if (pNode-_right pparent){pNode-_right subR;}subR-_parent pNode;}}void RotaR(Node* pparent){Node* subL pparent-_left;Node* subLR subL-_right;pparent-_left subLR;if (subLR ! nullptr){subLR-_parent pparent;}Node* pNode pparent-_parent;subL-_right pparent;pparent-_parent subL;if (pNode nullptr){_root subL;_root-_parent nullptr;}else{if (pNode-_left pparent){pNode-_left subL;}else{pNode-_right subL;}subL-_parent pNode;}}private:Node* _root nullptr;
};
