平衡二叉搜索树：AVL树和红黑树
AVL 树简介avl树是一种平衡二叉树通过“平衡因子”来实现左右两侧高度差的平衡只允许平衡因子取值为0、1、-1相对于红黑树avl树更接近“绝对平衡”但是对于旋转子树的处理要相对繁琐一些插入方法如果正好插入在较矮的子树那么久不需要旋转处理如果原来两棵子树同样高那么也不需要旋转处理如果插入在原来就较高的子树那么就需要进行旋转处理情况一根节点的左子树的左子树// 10 ----》 8// 8 b a 10// a c c ba是高度为h 1的子树其中包含了我们新插入的节点c子树是高度为h的子树b是高度为h的子树此时对于节点10他的平衡因子是-2需要进行旋转处理。左旋之后高度为h 1的a子树仍然在左边右子树的高度为h 1这样就实现了平衡8节点和10节点的平衡因子都被处理为了0情况二根节点的左子树的右子树// 10 ---- 10 ---- 8// 5 b 8 b 5 10// a 8 5 d a c d b// c d a c这里需要我们将情况一中的c子树进行拆分也就是上面例子中的以8为根节点的子树。a是高度为h的子树b、c是高度为h - 1的子树b是高度为h的子树情况二又可以根据8节点的平衡因子细分为三种情况无论哪种情况区分点在更新平衡因子在旋转上没有区别首先对8节点进行左单旋然后对10节点进行右单旋这样就完成了平衡随后根据前面说的新的节点的插入位置进行讨论更新8、5 10节点的平衡因子还有两种情况完全就是情况一、二的镜像版本没有任何区别这里不再过度赘述了avl树的验证从两个方面考虑一个是绝对高度是否满足左右子树差值不超过1另一个是平衡因子是否符合实际状况递归判断即可avl插入及验证的实现代码templateclassK,classVclassAVLNode{public:AVLNode(pairK,Vkv):kv(kv),bf(0),parent(nullptr),right(nullptr),left(nullptr){}pairK,Vkv;intbf;AVLNode*parent;AVLNode*right;AVLNode*left;};templateclassK,classVclassAVLTree{public:typedefAVLNodeK,VNode;boolinsert(pairK,Vkv){if(_rootnullptr){_rootnewNode(kv);returntrue;}Node*parentnullptr,*cur_root;while(cur){if(cur-kv.firstkv.first){parentcur;curcur-right;}elseif(cur-kv.firstkv.first){parentcur;curcur-left;}else{returnfalse;}}curnewNode(kv);if(cur-kv.firstparent-kv.first){parent-leftcur;}else{parent-rightcur;}cur-parentparent;while(parent){if(parent-leftcur){parent-bf--;}else{parent-bf;}if(parent-bf0){break;}elseif(parent-bf1||parent-bf-1){curparent;parentparent-parent;}elseif(parent-bf2||parent-bf-2){//旋转处理if(parent-bf-2cur-bf-1){RotateR(parent);}elseif(parent-bf-2cur-bf1){RotateLR(parent);}elseif(parent-bf2cur-bf1){RotateL(parent);}elseif(parent-bf2cur-bf-1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}returntrue;}voidRotateR(Node*parent){Node*subLparent-left;Node*subLRsubL-right;Node*grandparentparent-parent;parent-parentsubL;parent-leftsubLR;if(subLR){subLR-parentparent;}subL-rightparent;if(parent_root){_rootsubL;subL-parentnullptr;}else{if(grandparent-leftparent){grandparent-leftsubL;}else{grandparent-rightsubL;}subL-parentgrandparent;}subL-bf0;parent-bf0;}voidRotateL(Node*parent){Node*subRparent-right;Node*subRLsubR-left;Node*grandparentparent-parent;subR-leftparent;parent-parentsubR;parent-rightsubRL;if(subRL){subRL-parentparent;}if(parent_root){_rootsubR;subR-parentnullptr;}else{if(grandparent-leftparent){grandparent-leftsubR;}else{grandparent-rightsubR;}subR-parentgrandparent;}subR-bf0;parent-bf0;}voidRotateLR(Node*parent){Node*subLparent-left;Node*subLRsubL-right;intbfsubLR-bf;RotateL(subL);RotateR(parent);if(bf0){subL-bf0;subLR-bf0;parent-bf0;}elseif(bf1){subL-bf-1;subLR-bf0;parent-bf0;}elseif(bf-1){subL-bf0;subLR-bf0;parent-bf-1;}else{assert(false);}}voidRotateRL(Node*parent){Node*subRparent-right;Node*subRLsubR-left;intbfsubRL-bf;RotateR(subR);RotateL(parent);if(bf0){subR-bf0;subRL-bf0;parent-bf0;}elseif(bf1){subR-bf0;subRL-bf0;parent-bf-1;}elseif(bf-1){subR-bf1;subRL-bf0;parent-bf0;}else{assert(false);}}voidinOrder(){_inOrder(_root);}booltest(){return_test(_root);}private:void_inOrder(Node*root){if(rootnullptr){return;}_inOrder(root-left);coutroot-kv.first root-kv.second root-bfendl;_inOrder(root-right);}int_height(Node*root){if(rootnullptr){return0;}intlh_height(root-left);intrh_height(root-right);returnlhrh?lh1:rh1;}bool_test(Node*root){if(rootnullptr){returntrue;}intdiff_height(root-right)-_height(root-left);if(abs(diff)1){coutbad height: root-kv.firstendl;}if(diff!root-bf){coutbad bf: root-kv.firstendl;returnfalse;}return_test(root-left)_test(root-right);}Node*_rootnullptr;};红黑树简介红黑树也是平衡二叉搜索树的一种实现比avl树的应用更广一些cstl中的map和set都是用的红黑树实现的虽然实现的没有avl树那么的“平衡”但是红黑树在最坏情况下dfs的时间复杂度也是2logN依然和avl树在同一数量级规则每个节点要么是红色要么是黑色根节点必须是黑色黑色节点可以连接但是红色节点不能相互链接而且红色节点的两个子节点如果有的话必须是黑色节点从根节点到任意一个叶子节点的路程中黑色节点的数目都必须是相等的插入方法由上面的规则不难推导出插入节点必须是红色节点否则会导致原来的红黑树第四条规则失效插入的话大类其实根据新插入节点父节点的颜色分为两种一种是原来的节点是黑色这种情况下插入即可另一种是插入节点的父节点是红色。在这种情况下根据叔叔节点的颜色又可以进行区分下面先规定以下三种子树(1)父子树parentp(2)爷爷子树grandparentg(3)叔叔子树uncleu (4)当前子树currentc包含新插入的节点这里和上面只以左右对称的两种情况的其中一种为例子进行演示(为了方便0表示红色1表示黑色):叔叔节点存在为红色// g1 ---- g0// p0 u0 p1 u1// c0 c0只需要变动父亲节点和叔叔节点颜色即可但是这里会出现连锁反应需要继续往上处理让现在的g子树成为下一次的c子树叔叔节点不存在或者叔叔节点为黑色这里又可以根据c节点和p节点的相对位置分为两种情况情况一c是p的左孩子// g1 ---- p1// p0 u1 c0 g0// c0 u1这种情况下进行一个右单旋即可随后修改g、p的颜色情况二c是p的右孩子// g1 ---- g1 ---- c1// p0 u1 c0 u1 p0 g0// c0 p0 u1这种情况需要先对c进行左单旋随后对g1进行右单旋红黑树的验证从两个方面一个是红色节点的连接情况有没有出现两个红色节点相连的情况另一个是各个节点的黑色节点的数目。依旧与avl树类似采取递归的方式处理红黑树的插入及验证实现代码enumColor{RED,BLACK};templateclassK,classVclassRBNode{public:RBNode(pairK,Vkv,enumColorcolRED):kv(kv),color(col){}pairK,Vkv;RBNode*parentnullptr;RBNode*leftnullptr;RBNode*rightnullptr;Color color;};templateclassK,classVclassRBTree{public:typedefRBNodeK,VNode;boolinsert(pairK,Vkv){if(_rootnullptr){_rootnewNode(kv,BLACK);returntrue;}Node*cur_root,*parentnullptr;while(cur){if(cur-kv.firstkv.first){parentcur;curcur-right;}elseif(cur-kv.firstkv.first){parentcur;curcur-left;}else{returnfalse;}}curnewNode(kv);if(kv.firstparent-kv.first){parent-rightcur;}else{parent-leftcur;}cur-parentparent;while(parentparent-colorRED){Node*grandparentparent-parent;if(grandparent-leftparent){Node*unclegrandparent-right;if(uncleuncle-colorRED){parent-coloruncle-colorBLACK;grandparent-colorRED;curgrandparent;parentparent-parent;}else{if(curparent-left){// g// p u// cRotateR(grandparent);parent-colorBLACK;grandparent-colorRED;break;}else{// g// p u// cRotateL(cur);RotateR(parent);cur-colorBLACK;grandparent-colorRED;break;}}}else{Node*unclegrandparent-left;if(uncleuncle-colorRED){parent-coloruncle-colorBLACK;grandparent-colorRED;curgrandparent;parentcur-parent;}else{if(parent-rightcur){// g// u p// cRotateL(grandparent);grandparent-colorRED;parent-colorBLACK;break;}else{// g// u p// cRotateR(parent);RotateL(grandparent);cur-colorBLACK;grandparent-colorRED;break;}}}}_root-colorBLACK;returntrue;}voidRotateR(Node*parent){Node*subLparent-left;Node*subLRsubL-right;Node*grandparentparent-parent;parent-parentsubL;subL-rightparent;parent-leftsubLR;if(subLR){subLR-parentparent;}if(parent_root){_rootsubL;subL-parentnullptr;}else{if(grandparent-leftparent){grandparent-leftsubL;}else{grandparent-rightsubL;}subL-parentgrandparent;}}voidRotateL(Node*parent){Node*subRparent-right;Node*subRLsubR-left;Node*grandparentparent-parent;parent-parentsubR;subR-leftparent;parent-rightsubRL;if(subRL){subRL-parentparent;}if(parent_root){_rootsubR;subR-parentnullptr;}else{if(grandparent-rightparent){grandparent-rightsubR;}else{grandparent-leftsubR;}subR-parentgrandparent;}}voidinOrder(){_inOrder(_root);}voidtest(){if(isBalance(_root)){cout红黑树经检查无误endl;}}private:void_inOrder(Node*root){if(rootnullptr){return;}_inOrder(root-left);coutroot-kv.first root-kv.secondendl;_inOrder(root-right);}boolisBalance(Node*root){if(rootnullptr){returntrue;}if(root-colorRED){returnfalse;}intref0;Node*curroot;while(cur){if(cur-colorBLACK){ref;}curcur-left;}coutrefddddendl;returncheck(root,0,ref);}boolcheck(Node*root,intblacknum,intref){if(rootnullptr){if(blacknum!ref){cout黑色节点数目错误 blacknum refendl;returnfalse;}returntrue;}if(root-colorREDroot-parent-colorRED){cout连续的红色节点endl;returnfalse;}if(root-colorBLACK){blacknum;}returncheck(root-left,blacknum,ref)check(root-right,blacknum,ref);}Node*_rootnullptr;};
)
