红黑树结合图示理解以及简单实现插入

红黑树的性能是优于AVL的因为AVL比较严格而红黑树是相对平衡AVL是logN红黑树如果全黑就是logN如果全是一黑一红就是2logN但是当代CPU其实logN和2logN差别不大但是AVL的logN需要付出较大的代价每一次插入如果进行旋转还有调平衡因子所以总体而言红黑树是大哥1. 红黑树性质每个结点为红色或黑色根节点为黑色红色节点的孩子只能是黑色每条路径的黑色节点数量相同路径直到NIL节点并且包括NIL节点每个NIL叶子结点为黑色NIL节点是度为零节点的左右孩子也就是NULL下图公有11条路径有几个NIL就有几条路径可以做到最长路径长度不超过最短路径长的的2倍可以想象一下红色节点的父节点和孩子节点只能是红色而一条路径上最短是全黑最长是一红一黑交替而每条路径的黑色节点数量相同下图最短路径全黑最长路径一黑一红交替接着我们考虑新插入的节点为红色还是黑色如果是黑色因为每条路径的黑色节点数量相同那每条路径都要调整如果是红色如果插入之后的父节点为红色要调整如果是黑色就不需要调整综上是红色2. 插入思路新插入的节点cur如果父结点为空说明插入节点为根节点根变黑即可如果父节点为黑色不影响无需调整如果和父节点parent同时为红色granfather一定是黑色不然原本就不是红黑树这时候要调整只能是父亲变黑因为如果cur变黑就会影响所有路径接着考虑cur的uncle如果uncle为红色那parent和uncle同时变黑grandfather延伸出来的两条路径黑色节点1grandfather变红grandfather延伸出来的两条路径黑色节点-1打平了就解决问题了下一步就是迭代往上调整为什么呢因为grandfather由黑致红可能影响上层调整思路和上面一致举例uncle为红向上迭代uncle为黑或者uncle不存在2.1 插入抽象图看一下抽象图如果uncle为红色abcde均有零个黑节点c/d/e有一个黑节点各四种情况插入有四种一共是4^4256下图没有展示curgrandfather之后向上迭代的过程假设某一次迭代uncle为黑色以c和uncle作为根的路径均有n个黑节点共同做grandfather的孩子旋转染色调整的parent为根的所有路径黑节点数量不仅相同还和插入前grandfather延伸的所有路径黑节点数量相同根据grandfatherparent和cur位置关系判断如何旋转其实和AVL旋转时构成的斜线和折线一个套路因为旋转本就是针对二叉搜索树而AVL和红黑树都是二叉搜索树区别是AVL要调平衡因子红黑树要根据情况进行染色我感觉红黑树整个大逻辑首先插入默认为红色因为如果是黑色会影响全部路径插入红色影响一个路径那么现在要遵守规则不能出现红红如果插入之后没有父节点说明插入的是根直接将当前节点染成黑色如果父节点是黑色万事大吉无需调整如果父结点是红色这时候肯定有祖父节点因为只有根结点没爹而根结点是黑色且祖父节点是黑色不然祖父和父结点构成红红那么插入之前就不是红黑树因为出现了红红所以要调整现在不确定的诗uncle(也就是组父节点的另一个儿子)如果uncle为红色这时候考虑把grandfather占据的黑节点数量给到parent和unclegrandfather变红这种情况下既保证了grandfather延伸的两条路径黑色节点数量不变又解决了parent和cur红红的问题但现在相当于锅由grandfather来背了grandfather由黑变红grandfather是黑的时候没问题但变成红可能就有问题了所以curgrandfather继续往上迭代因为这个时候和插入节点cur面临的问题是一致的如果uncle不存在或者uncle为黑uncle为黑不可能是第一次插入的情况至少是curgranfather迭代一次出现因为uncle为黑parent为红能够插入在parent的左右孩子节点说明parent没孩子这时候parent和uncle两条路径的黑节点数量不一致不能像uncle为红色那样处理因为没有uncle可以直接染黑或者只染黑parent就会导致parent和uncle路径黑节点数量不一致这时候cur和parent是红色grandfather是黑色我们把这三个调整为根节点是黑色左右节点是红色如果单旋根节点就是parent如果双旋双旋cur比parent大不能直接旋要先旋成一条斜线再旋根节点就是cur相当于把红节点分散在两边2.2 插入代码实现#pragmaonceenumColor{RED,BLACK};templateclassK,classVstructBRTreeNode{BRTreeNode*_left;BRTreeNode*_right;BRTreeNode*_parent;pairK,V_kv;Color _col;BRTreeNode(constpairK,Vkv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}};templateclassK,classVclassBRTree{typedefBRTreeNodeK,VNode;public:BRTree():_root(nullptr){}boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);_root-_colBLACK;returntrue;}Node*cur_root;Node*parentnullptr;//找while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}elsereturnfalse;}//找到了curnewNode(kv);cur-_colRED;//默认插入为红色节点虽然构造的时候给的是RED但是解耦吧if(parent-_kv.firstkv.first)parent-_rightcur;elseparent-_leftcur;cur-_parentparent;while(parentparent-_colRED){//parent存在if(parent-_colRED){//parent为红色parent肯定有爹只有根节点没爹根节点为黑色Node*grandfatherparent-_parent;if(grandfather-_leftparent){//分情况讨论如果parent是grandfather的左节点Node*unclegrandfather-_right;//uncle为grandfather的右节点if(uncleuncle-_colRED){//如果uncle节点存在且uncle节点为红色parent-_coluncle-_colBLACK;//parent和uncle均染黑grandfather染红//这样相当于把矛盾转移本来是parent和cur红红现在把grandfather延伸出来的两条路径// grandfather占的黑节点数量给到parent和unclegrandfather变红这样curgrandfather// 往上迭代转化为和cur插入一样的问题grandfather-_colRED;curgrandfather;parentcur-_parent;}else{//uncle不存在或者uncle为黑色这个地方一定是curgrandfather至少迭代一次之后的cur第一次插入不可能是这种情况//旋转染色if(parent-_leftcur){// g// p// cRotateR(grandfather);parent-_colBLACK;grandfather-_colRED;}else{//parent-_right cur// g// p// cRotateL(parent);RotateR(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}else{//grandfather-_right parentNode*unclegrandfather-_left;//uncle为grandfather的右节点if(uncleuncle-_colRED){//如果uncle节点存在且uncle节点为红色parent-_coluncle-_colBLACK;//parent和uncle均染黑grandfather染红//这样相当于把矛盾转移本来是parent和cur红红现在把grandfather延伸出来的两条路径// grandfather占的黑节点数量给到parent和unclegrandfather变红这样curgrandfather// 往上迭代转化为和cur插入一样的问题grandfather-_colRED;curgrandfather;parentcur-_parent;}else{//uncle不存在或者uncle为黑色这个地方一定是curgrandfather至少迭代一次之后的cur第一次插入不可能是这种情况//旋转染色if(parent-_rightcur){// g// p// cRotateL(grandfather);parent-_colBLACK;grandfather-_colRED;}else{//parent-_right cur// g// p// cRotateR(parent);RotateL(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}}}_root-_colBLACK;returntrue;}boolRotateL(Node*parent){_rotatecount;Node*curparent-_right;Node*curleftcur-_left;Node*ppnodeparent-_parent;parent-_rightcurleft;if(curleft)curleft-_parentparent;cur-_leftparent;parent-_parentcur;if(ppnode){if(ppnode-_leftparent)ppnode-_leftcur;elseppnode-_rightcur;}else{_rootcur;}cur-_parentppnode;returntrue;}boolRotateR(Node*parent){_rotatecount;Node*curparent-_left;Node*currightcur-_right;Node*ppnodeparent-_parent;parent-_leftcurright;if(curright)curright-_parentparent;cur-_rightparent;parent-_parentcur;if(ppnode){if(ppnode-_rightparent)ppnode-_rightcur;elseppnode-_leftcur;}else_rootcur;cur-_parentppnode;returntrue;}intHeight(){returnHeight(_root);}intHeight(Node*root){if(rootnullptr)return0;intleftHeightHeight(root-_left);intrightHeightHeight(root-_right);returnleftHeightrightHeight?leftHeight1:rightHeight1;}boolIsBalance(){return_IsBalance(_root);}bool_IsBalance(Node*root){if(rootnullptr)returntrue;if(root-_colRED)returnfalse;intbenchmark0;Node*curroot;while(cur){if(cur-_colBLACK)benchmark;curcur-_left;}returnCheckColor(root,0,benchmark);}boolCheckColor(Node*root,intblacknum,intbenchmark){if(rootnullptr){if(blacknum!benchmark)returnfalse;returntrue;}if(root-_colBLACK)blacknum;if(root-_colREDroot-_parentroot-_parent-_colRED){coutroot-_kv.first出现连续红色节点endl;returnfalse;}returnCheckColor(root-_left,blacknum,benchmark)CheckColor(root-_right,blacknum,benchmark);}voidInOrder(){_InOrder(_root);coutendl;}void_InOrder(Node*root){if(rootnullptr)return;_InOrder(root-_left);coutroot-_kv.first ;_InOrder(root-_right);}int_rotatecount0;private:Node*_root;};test.cpp//测试AVL和BRTree的效率#includeiostream#includeassert.h#includevector#includestringusingnamespacestd;#includeBRTree.h#includeAVLTree.hintmain(){size_t N1000000;vectorintv;srand(time(0));for(inti0;iN;i){v.push_back(rand()i);}AVLTreeint,intt;BRTreeint,intbrt;for(autoe:v){t.Insert(make_pair(e,e));brt.Insert(make_pair(e,e));}coutt.IsBalance()endl;coutt.Height()endl;coutt._rotatecountendl;coutbrt.IsBalance()endl;coutbrt.Height()endl;coutbrt._rotatecountendl;return0;}输出122446907127371743牛刀小试关于红黑树以下说法正确的是A.空树不是红黑树因为红黑树要求根节点必须为黑色而空树中没有根节点B.红黑树也是二叉搜索树因此其按照前序遍历可以得到有序序列C.红黑树是一棵真正平衡的二叉树D.红黑树最长路径中节点个数可能会等于最短路径中节点个数的两倍DA空树是红黑树B.中序C.二叉树不要求严格平衡红黑树的插入算法复杂度最坏情况是 A.O(n)B.O(log(n))C.O(nlog(n))D.其他都不对B.树高接近logN下面关于红黑树的特性说法错误的是A.红黑树最左侧节点一定是最小的最右侧节点一定是最大的B.红黑树在实现时必须要有头结点C.红黑树中可能会出现连在一起的黑色节点D.红黑树的旋转不需要依靠平衡因子B关于AVL树和红黑树的区别说法不正确的是A.AVL树和红黑树保证平衡性的方式不同B.AVL树和红黑树都是平衡树因此查找的时间复杂度都是O(log_2N)C.AVL树和红黑树的性质遭到破坏时都需要进行旋转D.AVL树和红黑树中序遍历都可以得到有序序列因为它们都是二叉搜索树C红黑树不一定需要旋转