南京网站制作公司排名,网上商城怎么购物,网站批量收录,汕头汽车网站建设红黑树#xff1a;
一种接近平衡的二叉树#xff0c;平衡程度低于搜索二叉树。
特点#xff1a;
1.根节点为黑
2.黑色结点的子结点可以是红色结点或黑色结点。
3.红色结点的子结点只能是黑色结点。
4.每个结点到其所有叶子结点的路径的黑色结点个数相同。
5.指向空的…红黑树
一种接近平衡的二叉树平衡程度低于搜索二叉树。
特点
1.根节点为黑
2.黑色结点的子结点可以是红色结点或黑色结点。
3.红色结点的子结点只能是黑色结点。
4.每个结点到其所有叶子结点的路径的黑色结点个数相同。
5.指向空的结点指向空的那一侧视为指向黑色结点指向nullptr的黑色结点用于明确路径
6.由于上述规则使得红黑树任意结点的左右子树高度差不超过二倍最小是全黑最大是红黑相交又由于黑色结点个数需要一致因此高度不会超过二倍。 模拟实现红黑树
1.红黑树的插入 // 注意为了简单起见本次实现红黑树不存储重复性元素bool Insert(const T data){if (_pHead nullptr){Node* cur new Node(data);_pHead cur;_pHead-_color black;return true;}//有根节点的时候Node* cur new Node(data);Node* news _pHead;Node* parent nullptr;//查找插入位置while (news ! nullptr){if (news-_data data){ parent news;news news-_pRight;}else if (news-_data data){ parent news;news news-_pLeft;}else{return false;}}//确定插入位置是parent的左还是右if (parent-_data data){parent-_pRight cur;cur-_pParent parent;}else{parent-_pLeft cur;cur-_pParent parent;}//开始向上判断//若父节点为黑则可以正常插入无任何影响//父节点为红才进入若父节点为空则cur指向根结点同样退出while (parentparent-_colorred){ Node* grandparent parent-_pParent;//parent为红则一定有父节点if(grandparent-_colorblack){//得到uncleNode* uncle nullptr;if (parent-_data grandparent-_data){uncle grandparent-_pRight;}else{uncle grandparent-_pLeft;}//判断uncle情况if (uncle uncle-_color red){ //UNCLE存在且是红parent-_color uncle-_color black;grandparent-_color red;cur grandparent;parent cur-_pParent;}else{//uncle为黑或者uncle为空if (cur parent-_pLeft parent grandparent-_pLeft){//右旋RotateR(grandparent);//更新颜色parent-_color black;grandparent-_color red;}else if (cur parent-_pRight parent grandparent-_pRight){//左旋RotateL(grandparent);//更新颜色parent-_color black;grandparent-_color red;}//更新后当前子树的根节点为黑无需向上继续判断因此parent-_color可以直接使得退出循环else if(cur parent-_pRight parent grandparent-_pLeft){//先左旋parent再右旋grandparentRotateL(parent);RotateR(grandparent);cur-_color black;grandparent-_color red;break;}else{RotateR(parent);RotateL(grandparent);cur-_color black;grandparent-_color red;break;}}}else{ //此时grandparent和parent颜色均是红报错cout parent-_data出现连续红结点 endl;assert(false);}}_pHead-_color black;}// 左单旋void RotateL(Node* pParent){Node* parent pParent;Node* pr parent-_pRight;Node* prl pr-_pLeft;//记录父节点Node* pp parent-_pParent;//更新指针parent-_pRight prl;if (prl)//判断prl是否存在prl-_pParent parent;pr-_pLeft parent;parent-_pParent pr;if (pp nullptr){//若parent是根节点_pHead pr;pr-_pParent nullptr;}else{ //父节点连接if (pp-_data parent-_data){pp-_pRight pr;pr-_pParent pp;}else{pp-_pLeft pr;pr-_pParent pp;}}}// 右单旋void RotateR(Node* pParent){Node* parent pParent;Node* pl parent-_pLeft;Node* plr pl-_pRight;//记录父节点Node* pp parent-_pParent;//更新指针parent-_pLeft plr;if (plr)//判断prl是否存在plr-_pParent parent;pl-_pRight parent;parent-_pParent pl;if (pp nullptr){//若parent是根节点_pHead pl;pl-_pParent nullptr;}else{ //父节点连接if (pp-_data parent-_data){pp-_pRight pl;pl-_pParent pp;}else{pp-_pLeft pl;pl-_pParent pp;}}} 插入一个结点初始时插入结点为红若为黑则会导致其祖先结点每条路径黑色结点的个数改变修改十分麻烦。若此时父节点为黑则无需进行任何其余操作。
若父节点为红此时会出现连续红色结点的情况不符合红黑树的定义因此需要修改。
修改主要分以下几种情况
1. 此时叔叔结点存在且为红色。
修改方式是将父节点和叔叔结点改成黑色祖先结点改成红色然后将祖先结点视为新插入结点继续向上判断。此时父节点和叔叔结点改成黑色不会受其子节点颜色的影响且对于祖先结点的父节点每条路径的黑色结点的个数没有变化因此仍符合红黑树。 2. 此时叔叔结点为黑色结点或者不存在不存在的情况根据红黑树规则指向空的结点指向空的那一侧视为指向黑色结点因此也可以看做叔叔结点为黑色结点。此时需要进行旋转来修改这棵子树。若祖先结点和父节点以及新插入结点都在同一侧比如父节点是祖先结点左子树新插入结点是父节点的左子树则只需要对祖先结点进行一次旋转旋转完成后将父节点改成黑色祖先结点改成红色即可。若不在同一侧则需要先对父节点进行一次旋转再对祖先结点进行一次旋转旋转完成后新插入结点的颜色为黑祖先结点颜色为红。 在同一侧的旋转一次。 不在同一侧旋转两次。
