相信很多朋友知道二叉查找树不是严格的O(logN)，导致了在真实场景中没有用武之地，谁也不愿意有O(N)的情况发生，作为一名码农，肯定会希望能把“范围查找”做到地球人都不能优化的地步。当有很多数据灌到我的树中时，我肯定会希望最好是以“完全二叉树”的形式展现，这样我才能做到“查找”是严格的O(logN)，比如把这种”树“调正到如下结构。
这里就涉及到了“树节点”的旋转，也是我们今天要聊到的内容。
一：平衡二叉树（AVL）1：定义父节点的左子树和右子树的高度之差不能大于1，也就是说不能高过1层，否则该树就失衡了，此时就要旋转节点，在编码时，我们可以记录当前节点的高度，比如空节点是-1，叶子节点是0，非叶子节点的height往根节点递增，比如在下图中我们认为树的高度为h=2。
///summary///平衡二叉树节点////summary///typeparamname="K"/typeparam///typeparamname="V"/typeparampublicclassAVLNodeK,V{///summary///节点元素////summarypublicKkey;///summary///增加一个高度信息////summarypublicintheight;///summary///节点中的附加值////summarypublicHashSetVattach=newHashSetV();///summary///左节点////summarypublicAVLNodeK,Vleft;///summary///右节点////summarypublicAVLNodeK,Vright;publicAVLNode(){}publicAVLNode(Kkey,Vvalue,AVLNodeK,Vleft,AVLNodeK,Vright){//KV键值对this.key=key;this.attach.Add(value);this.left=left;this.right=right;}}2：旋转
节点再怎么失衡都逃不过4种情况，下面我们一一来看一下。
左左情况（左子树的左边节点）我们看到，在向树中追加“节点1”的时候，根据定义我们知道这样会导致了“节点3"失衡，满足“左左情况“，可以这样想，把这棵树比作齿轮，我们在“节点5”处把齿轮往下拉一个位置，也就变成了后面这样“平衡”的形式，如果用动画解释就最好理解了。
///summary///第一种：左左旋转（单旋转）////summary///paramname="node"/param///returns/returnspublicAVLNodeK,VRotateLL(AVLNodeK,Vnode){//top：需要作为顶级节点的元素vartop=node.left;//先截断当前节点的左孩子node.left=top.right;//将当前节点作为temp的右孩子top.right=node;//计算当前两个节点的高度node.height=Math.Max(Height(node.left),Height(node.right))+1;top.height=Math.Max(Height(top.left),Height(top.right))+1;returntop;}右右情况（右子树的右边节点）
同样，”节点5“满足”右右情况“，其实我们也看到，这两种情况是一种镜像，当然操作方式也大同小异，我们在”节点1“的地方将树往下拉一位，最后也就形成了我们希望的平衡效果。
///summary///第二种：右右旋转（单旋转）////summary///paramname="node"/param///returns/returnspublicAVLNodeK,VRotateRR(AVLNodeK,Vnode){//top：需要作为顶级节点的元素vartop=node.right;//先截断当前节点的右孩子node.right=top.left;//将当前节点作为temp的右孩子top.left=node;//计算当前两个节点的高度node.height=Math.Max(Height(node.left),Height(node.right))+1;top.height=Math.Max(Height(top.left),Height(top.right))+1;returntop;}左右情况（左子树的右边节点）
从图中我们可以看到，当我们插入”节点3“时，“节点5”处失衡，注意，找到”失衡点“是非常重要的，当面对”左右情况“时，我们将失衡点的左子树进行"右右情况旋转"，然后进行”左左情况旋转“，经过这样两次的旋转就OK了，很有意思，对吧。
#region第三种：左右旋转（双旋转）///summary///第三种：左右旋转（双旋转）////summary///paramname="node"/param///returns/returnspublicAVLNodeK,VRotateLR(AVLNodeK,Vnode){//先进行RR旋转node.left=RotateRR(node.left);//再进行LL旋转returnRotateLL(node);}#endregion右左情况(右子树的左边节点）
这种情况和“情景3”也是一种镜像关系，很简单，我们找到了”节点15“是失衡点，然后我们将”节点15“的右子树进行”左左情况旋转“，然后进行”右右情况旋转“，最终得到了我们满意的平衡。
#region第四种：右左旋转（双旋转）///summary///第四种：右左旋转（双旋转）////summary///paramname="node"/param///returns/returnspublicAVLNodeK,VRotateRL(AVLNodeK,Vnode){//执行左左旋转node.right=RotateLL(node.right);//再执行右右旋转returnRotateRR(node);}#endregion3：添加
如果我们理解了上面的这几种旋转，那么添加方法简直是轻而易举，出现了哪一种情况调用哪一种方法而已。
#region添加操作///summary///添加操作////summary///paramname="key"/param///paramname="value"/param///paramname="tree"/param///returns/returnspublicAVLNodeK,VAdd(Kkey,Vvalue,AVLNodeK,Vtree){if(tree==null)tree=newAVLNodeK,V(key,value,null,null);//左子树if(key.CompareTo(tree.key)0){tree.left=Add(key,value,tree.left);//如果说相差等于2就说明这棵树需要旋转了if(Height(tree.left)-Height(tree.right)==2){//说明此时是左左旋转if(key.CompareTo(tree.left.key)0){tree=RotateLL(tree);}else{//属于左右旋转tree=RotateLR(tree);}}}//右子树if(key.CompareTo(tree.key)0){tree.right=Add(key,value,tree.right);if((Height(tree.right)-Height(tree.left)==2)){//此时是右右旋转if(key.CompareTo(tree.right.key)0){tree=RotateRR(tree);}else{//属于右左旋转tree=RotateRL(tree);}}}//将value追加到附加值中（也可对应重复元素）if(key.CompareTo(tree.key)==0)tree.attach.Add(value);//计算高度tree.height=Math.Max(Height(tree.left),Height(tree.right))+1;returntree;}#endregion4：删除
删除方法跟添加方法也类似，当删除一个结点的时候，可能会引起祖先结点的失衡，所以在每次”结点“回退的时候计算结点高度。
#region删除当前树中的节点///summary///删除当前树中的节点////summary///paramname="key"/param///paramname="tree"/param///returns/returnspublicAVLNodeK,VRemove(Kkey,Vvalue,AVLNodeK,Vtree){if(tree==null)returnnull;//左子树if(key.CompareTo(tree.key)0){tree.left=Remove(key,value,tree.left);//如果说相差等于2就说明这棵树需要旋转了if(Height(tree.left)-Height(tree.right)==2){//说明此时是左左旋转if(key.CompareTo(tree.left.key)0){tree=RotateLL(tree);}else{//属于左右旋转tree=RotateLR(tree);}}}//右子树if(key.CompareTo(tree.key)0){tree.right=Remove(key,value,tree.right);if((Height(tree.right)-Height(tree.left)==2)){//此时是右右旋转if(key.CompareTo(tree.right.key)0){tree=RotateRR(tree);}else{//属于右左旋转tree=RotateRL(tree);}}}/*相等的情况*/if(key.CompareTo(tree.key)==0){//判断里面的HashSet是否有多值if(tree.attach.Count1){//实现惰性删除tree.attach.Remove(value);}else{//有两个孩子的情况if(tree.left!=nulltree.right!=null){//根据平衡二叉树的中顺遍历，需要找到”有子树“的最小节点tree.key=FindMin(tree.right).key;//删除右子树的指定元素tree.right=Remove(tree.key,value,tree.right);}else{//自减高度tree=tree.left==null?tree.right:tree.left;//如果删除的是叶子节点直接返回if(tree==null)returnnull;}}}//统计高度tree.height=Math.Max(Height(tree.left),Height(tree.right))+1;returntree;}#endregion5:测试
平衡二叉树已经有了，来一个范围检索,查找-7-:00:00到-7-:00:00的登陆用户的ID，数据量在w，看看平衡二叉树是如何秒杀对手。
classProgram{staticvoidMain(string[]args){AVLTreeint,intavl=newAVLTreeint,int();DictionaryDateTime,intdic=newDictionaryDateTime,int();AVLTreeDateTime,inttree=newAVLTreeDateTime,int();//wfor(inti=1;i0000;i++){dic.Add(DateTime.Now.AddMinutes(i),i);tree.Add(DateTime.Now.AddMinutes(i),i);}//检索-7-:00:00到-7-:00:00的登陆人数varmin=Convert.ToDateTime("/7/:00:00");varmax=Convert.ToDateTime("/7/:00:00");varwatch=Stopwatch.StartNew();varresult1=dic.Keys.Where(i=i=mini=max).Select(i=dic).ToList();watch.Stop();Console.WriteLine("字典查找耗费时间:{0}ms",watch.ElapsedMilliseconds);watch=Stopwatch.StartNew();varresult2=tree.SearchRange(min,max);watch.Stop();Console.WriteLine("平衡二叉树查找耗费时间:{0}ms",watch.ElapsedMilliseconds);}}#region平衡二叉树节点///summary///平衡二叉树节点////summary///typeparamname="K"/typeparam///typeparamname="V"/typeparampublicclassAVLNodeK,V{///summary///节点元素////summarypublicKkey;///summary///增加一个高度信息////summarypublicintheight;///summary///节点中的附加值////summarypublicHashSetVattach=newHashSetV();///summary///左节点////summarypublicAVLNodeK,Vleft;///summary///右节点////summarypublicAVLNodeK,Vright;publicAVLNode(){}publicAVLNode(Kkey,Vvalue,AVLNodeK,Vleft,AVLNodeK,Vright){//KV键值对this.key=key;this.attach.Add(value);this.left=left;this.right=right;}}#endregionpublicclassAVLTreeK,VwhereK:IComparable{publicAVLNodeK,Vnode=null;#region添加操作///summary///添加操作////summary///paramname="key"/param///paramname="value"/parampublicvoidAdd(Kkey,Vvalue){node=Add(key,value,node);}#endregion#region添加操作///summary///添加操作////summary///paramname="key"/param///paramname="value"/param///paramname="tree"/param///returns/returnspublicAVLNodeK,VAdd(Kkey,Vvalue,AVLNodeK,Vtree){if(tree==null)tree=newAVLNodeK,V(key,value,null,null);//左子树if(key.CompareTo(tree.key)0){tree.left=Add(key,value,tree.left);//如果说相差等于2就说明这棵树需要旋转了if(Height(tree.left)-Height(tree.right)==2){//说明此时是左左旋转if(key.CompareTo(tree.left.key)0){tree=RotateLL(tree);}else{//属于左右旋转tree=RotateLR(tree);}}}//右子树if(key.CompareTo(tree.key)0){tree.right=Add(key,value,tree.right);if((Height(tree.right)-Height(tree.left)==2)){//此时是右右旋转if(key.CompareTo(tree.right.key)0){tree=RotateRR(tree);}else{//属于右左旋转tree=RotateRL(tree);}}}//将value追加到附加值中（也可对应重复元素）if(key.CompareTo(tree.key)==0)tree.attach.Add(value);//计算高度tree.height=Math.Max(Height(tree.left),Height(tree.right))+1;returntree;}#endregion#region计算当前节点的高度///summary///计算当前节点的高度////summary///paramname="node"/param///returns/returnspublicintHeight(AVLNodeK,Vnode){returnnode==null?-1:node.height;}#endregion#region第一种：左左旋转（单旋转）///summary///第一种：左左旋转（单旋转）////summary///paramname="node"/param///returns/returnspublicAVLNodeK,VRotateLL(AVLNodeK,Vnode){//top：需要作为顶级节点的元素vartop=node.left;//先截断当前节点的左孩子node.left=top.right;//将当前节点作为temp的右孩子top.right=node;//计算当前两个节点的高度node.height=Math.Max(Height(node.left),Height(node.right))+1;top.height=Math.Max(Height(top.left),Height(top.right))+1;returntop;}#endregion#region第二种：右右旋转（单旋转）///summary///第二种：右右旋转（单旋转）////summary///paramname="node"/param///returns/returnspublicAVLNodeK,VRotateRR(AVLNodeK,Vnode){//top：需要作为顶级节点的元素vartop=node.right;//先截断当前节点的右孩子node.right=top.left;//将当前节点作为temp的右孩子top.left=node;//计算当前两个节点的高度node.height=Math.Max(Height(node.left),Height(node.right))+1;top.height=Math.Max(Height(top.left),Height(top.right))+1;returntop;}#endregion#region第三种：左右旋转（双旋转）///summary///第三种：左右旋转（双旋转）////summary///paramname="node"/param///returns/returnspublicAVLNodeK,VRotateLR(AVLNodeK,Vnode){//先进行RR旋转node.left=RotateRR(node.left);//再进行LL旋转returnRotateLL(node);}#endregion#region第四种：右左旋转（双旋转）///summary///第四种：右左旋转（双旋转）////summary///paramname="node"/param///returns/returnspublicAVLNodeK,VRotateRL(AVLNodeK,Vnode){//执行左左旋转node.right=RotateLL(node.right);//再执行右右旋转returnRotateRR(node);}#endregion#region是否包含指定元素///summary///是否包含指定元素////summary///paramname="key"/param///returns/returnspublicboolContain(Kkey){returnContain(key,node);}#endregion#region是否包含指定元素///summary///是否包含指定元素////summary///paramname="key"/param///paramname="tree"/param///returns/returnspublicboolContain(Kkey,AVLNodeK,Vtree){if(tree==null)returnfalse;//左子树if(key.CompareTo(tree.key)0)returnContain(key,tree.left);//右子树if(key.CompareTo(tree.key)0)returnContain(key,tree.right);returntrue;}#endregion#region树的指定范围查找///summary///树的指定范围查找////summary///paramname="min"/param///paramname="max"/param///returns/returnspublicHashSetVSearchRange(Kmin,Kmax){HashSetVhashSet=newHashSetV();hashSet=SearchRange(min,max,hashSet,node);returnhashSet;}#endregion#region树的指定范围查找///summary///树的指定范围查找////summary///paramname="range1"/param///paramname="range2"/param///paramname="tree"/param///returns/returnspublicHashSetVSearchRange(Kmin,Kmax,HashSetVhashSet,AVLNodeK,Vtree){if(tree==null)returnhashSet;//遍历左子树（寻找下界）if(min.CompareTo(tree.key)0)SearchRange(min,max,hashSet,tree.left);//当前节点是否在选定范围内if(min.CompareTo(tree.key)=0max.CompareTo(tree.key)=0){//等于这种情况foreach(varitemintree.attach)hashSet.Add(item);}//遍历右子树（两种情况：①:找min的下限②：必须在Max范围之内）if(min.CompareTo(tree.key)0
max.CompareTo(tree.key)0)SearchRange(min,max,hashSet,tree.right);returnhashSet;}#endregion#region找到当前树的最小节点///summary///找到当前树的最小节点////summary///returns/returnspublicAVLNodeK,VFindMin(){returnFindMin(node);}#endregion#region找到当前树的最小节点///summary///找到当前树的最小节点////summary///paramname="tree"/param///returns/returnspublicAVLNodeK,VFindMin(AVLNodeK,Vtree){if(tree==null)returnnull;if(tree.left==null)returntree;returnFindMin(tree.left);}#endregion#region找到当前树的最大节点///summary///找到当前树的最大节点////summary///returns/returnspublicAVLNodeK,VFindMax(){returnFindMin(node);}#endregion#region找到当前树的最大节点///summary///找到当前树的最大节点////summary///paramname="tree"/param///returns/returnspublicAVLNodeK,VFindMax(AVLNodeK,Vtree){if(tree==null)returnnull;if(tree.right==null)returntree;returnFindMax(tree.right);}#endregion#region删除当前树中的节点///summary///删除当前树中的节点////summary///paramname="key"/param///returns/returnspublicvoidRemove(Kkey,Vvalue){node=Remove(key,value,node);}#endregion#region删除当前树中的节点///summary///删除当前树中的节点////summary///paramname="key"/param///paramname="tree"/param///returns/returnspublicAVLNodeK,VRemove(Kkey,Vvalue,AVLNodeK,Vtree){if(tree==null)returnnull;//左子树if(key.CompareTo(tree.key)0){tree.left=Remove(key,value,tree.left);//如果说相差等于2就说明这棵树需要旋转了if(Height(tree.left)-Height(tree.right)==2){//说明此时是左左旋转if(key.CompareTo(tree.left.key)0){tree=RotateLL(tree);}else{//属于左右旋转tree=RotateLR(tree);}}}//右子树if(key.CompareTo(tree.key)0){tree.right=Remove(key,value,tree.right);if((Height(tree.right)-Height(tree.left)==2)){//此时是右右旋转if(key.CompareTo(tree.right.key)0){tree=RotateRR(tree);}else{//属于右左旋转tree=RotateRL(tree);}}}/*相等的情况*/if(key.CompareTo(tree.key)==0){//判断里面的HashSet是否有多值if(tree.attach.Count1){//实现惰性删除tree.attach.Remove(value);}else{//有两个孩子的情况if(tree.left!=nulltree.right!=null){//根据平衡二叉树的中顺遍历，需要找到”有子树“的最小节点tree.key=FindMin(tree.right).key;//删除右子树的指定元素tree.right=Remove(tree.key,value,tree.right);}else{//自减高度tree=tree.left==null?tree.right:tree.left;//如果删除的是叶子节点直接返回if(tree==null)returnnull;}}}//统计高度tree.height=Math.Max(Height(tree.left),Height(tree.right))+1;returntree;}#endregion}
wow,相差98倍，这可不是一个级别啊...AVL神器。
一线码农聊技术一杯咖啡通宵写码