上一篇我们聊过,二叉查找树不是严格的O(logN),导致了在真实场景中没有用武之地,谁也不愿意有O(N)的情况发生,
作为一名码农,肯定会希望能把“范围查找”做到地球人都不能优化的地步。
当有很多数据灌到我的树中时,我肯定会希望最好是以“完全二叉树”的形式展现,这样我才能做到“查找”是严格的O(logN),
比如把这种”树“调正到如下结构。
这里就涉及到了“树节点”的旋转,也是我们今天要聊到的内容。
一:平衡二叉树(AVL)
1:定义
父节点的左子树和右子树的高度之差不能大于1,也就是说不能高过1层,否则该树就失衡了,此时就要旋转节点,在
编码时,我们可以记录当前节点的高度,比如空节点是-1,叶子节点是0,非叶子节点的height往根节点递增,比如在下图
中我们认为树的高度为h=2。
1 #region 平衡二叉树节点 2 /// <summary> 3 /// 平衡二叉树节点 4 /// </summary> 5 /// <typeparam name="K"></typeparam> 6 /// <typeparam name="V"></typeparam> 7 public class AVLNode<K, V> 8 { 9 /// <summary>10 /// 节点元素11 /// </summary>12 public K key;13 14 /// <summary>15 /// 增加一个高度信息16 /// </summary>17 public int height;18 19 /// <summary>20 /// 节点中的附加值21 /// </summary>22 public HashSet<V> attach = new HashSet<V>();23 24 /// <summary>25 /// 左节点26 /// </summary>27 public AVLNode<K, V> left;28 29 /// <summary>30 /// 右节点31 /// </summary>32 public AVLNode<K, V> right;33 34 public AVLNode() { }35 36 public AVLNode(K key, V value, AVLNode<K, V> left, AVLNode<K, V> right)37 {38 //KV键值对39 this.key = key;40 this.attach.Add(value);41 42 this.left = left;43 this.right = right;44 }45 }46 #endregion
2:旋转
节点再怎么失衡都逃不过4种情况,下面我们一一来看一下。
① 左左情况(左子树的左边节点)
我们看到,在向树中追加“节点1”的时候,根据定义我们知道这样会导致了“节点3"失衡,满足“左左情况“,可以这样想,把这
棵树比作齿轮,我们在“节点5”处把齿轮往下拉一个位置,也就变成了后面这样“平衡”的形式,如果用动画解释就最好理解了。
1 #region 第一种:左左旋转(单旋转) 2 /// <summary> 3 /// 第一种:左左旋转(单旋转) 4 /// </summary> 5 /// <param name="node"></param> 6 /// <returns></returns> 7 public AVLNode<K, V> RotateLL(AVLNode<K, V> node) 8 { 9 //top:需要作为顶级节点的元素10 var top = node.left;11 12 //先截断当前节点的左孩子13 node.left = top.right;14 15 //将当前节点作为temp的右孩子16 top.right = node;17 18 //计算当前两个节点的高度19 node.height = Math.Max(Height(node.left), Height(node.right)) + 1;20 top.height = Math.Max(Height(top.left), Height(top.right)) + 1;21 22 return top;23 }24 #endregion
② 右右情况(右子树的右边节点)
同样,”节点5“满足”右右情况“,其实我们也看到,这两种情况是一种镜像,当然操作方式也大同小异,我们在”节点1“的地方
将树往下拉一位,最后也就形成了我们希望的平衡效果。
1 #region 第二种:右右旋转(单旋转) 2 /// <summary> 3 /// 第二种:右右旋转(单旋转) 4 /// </summary> 5 /// <param name="node"></param> 6 /// <returns></returns> 7 public AVLNode<K, V> RotateRR(AVLNode<K, V> node) 8 { 9 //top:需要作为顶级节点的元素10 var top = node.right;11 12 //先截断当前节点的右孩子13 node.right = top.left;14 15 //将当前节点作为temp的右孩子16 top.left = node;17 18 //计算当前两个节点的高度19 node.height = Math.Max(Height(node.left), Height(node.right)) + 1;20 top.height = Math.Max(Height(top.left), Height(top.right)) + 1;21 22 return top;23 }24 #endregion
③左右情况(左子树的右边节点)
从图中我们可以看到,当我们插入”节点3“时,“节点5”处失衡,注意,找到”失衡点“是非常重要的,当面对”左右情况“时,我们将
失衡点的左子树进行"右右情况旋转",然后进行”左左情况旋转“,经过这样两次的旋转就OK了,很有意思,对吧。
1 #region 第三种:左右旋转(双旋转) 2 /// <summary> 3 /// 第三种:左右旋转(双旋转) 4 /// </summary> 5 /// <param name="node"></param> 6 /// <returns></returns> 7 public AVLNode<K, V> RotateLR(AVLNode<K, V> node) 8 { 9 //先进行RR旋转10 node.left = RotateRR(node.left);11 12 //再进行LL旋转13 return RotateLL(node);14 }15 #endregion
④右左情况(右子树的左边节点)
这种情况和“情景3”也是一种镜像关系,很简单,我们找到了”节点15“是失衡点,然后我们将”节点15“的右子树进行”左左情况旋转“,
然后进行”右右情况旋转“,最终得到了我们满意的平衡。
1 #region 第四种:右左旋转(双旋转) 2 /// <summary> 3 /// 第四种:右左旋转(双旋转) 4 /// </summary> 5 /// <param name="node"></param> 6 /// <returns></returns> 7 public AVLNode<K, V> RotateRL(AVLNode<K, V> node) 8 { 9 //执行左左旋转10 node.right = RotateLL(node.right);11 12 //再执行右右旋转13 return RotateRR(node);14 15 }16 #endregion
3:添加
如果我们理解了上面的这几种旋转,那么添加方法简直是轻而易举,出现了哪一种情况调用哪一种方法而已。
1 #region 添加操作 2 /// <summary> 3 /// 添加操作 4 /// </summary> 5 /// <param name="key"></param> 6 /// <param name="value"></param> 7 /// <param name="tree"></param> 8 /// <returns></returns> 9 public AVLNode<K, V> Add(K key, V value, AVLNode<K, V> tree)10 {11 if (tree == null)12 tree = new AVLNode<K, V>(key, value, null, null);13 14 //左子树15 if (key.CompareTo(tree.key) < 0)16 {17 tree.left = Add(key, value, tree.left);18 19 //如果说相差等于2就说明这棵树需要旋转了20 if (Height(tree.left) - Height(tree.right) == 2)21 {22 //说明此时是左左旋转23 if (key.CompareTo(tree.left.key) < 0)24 {25 tree = RotateLL(tree);26 }27 else28 {29 //属于左右旋转30 tree = RotateLR(tree);31 }32 }33 }34 35 //右子树36 if (key.CompareTo(tree.key) > 0)37 {38 tree.right = Add(key, value, tree.right);39 40 if ((Height(tree.right) - Height(tree.left) == 2))41 {42 //此时是右右旋转43 if (key.CompareTo(tree.right.key) > 0)44 {45 tree = RotateRR(tree);46 }47 else48 {49 //属于右左旋转50 tree = RotateRL(tree);51 }52 }53 }54 55 //将value追加到附加值中(也可对应重复元素)56 if (key.CompareTo(tree.key) == 0)57 tree.attach.Add(value);58 59 //计算高度60 tree.height = Math.Max(Height(tree.left), Height(tree.right)) + 1;61 62 return tree;63 }64 #endregion
4:删除
删除方法跟添加方法也类似,当删除一个结点的时候,可能会引起祖先结点的失衡,所以在每次”结点“回退的时候计算结点高度。
1 #region 删除当前树中的节点 2 /// <summary> 3 /// 删除当前树中的节点 4 /// </summary> 5 /// <param name="key"></param> 6 /// <param name="tree"></param> 7 /// <returns></returns> 8 public AVLNode<K, V> Remove(K key, V value, AVLNode<K, V> tree) 9 {10 if (tree == null)11 return null;12 13 //左子树14 if (key.CompareTo(tree.key) < 0)15 {16 tree.left = Remove(key, value, tree.left);17 18 //如果说相差等于2就说明这棵树需要旋转了19 if (Height(tree.left) - Height(tree.right) == 2)20 {21 //说明此时是左左旋转22 if (key.CompareTo(tree.left.key) < 0)23 {24 tree = RotateLL(tree);25 }26 else27 {28 //属于左右旋转29 tree = RotateLR(tree);30 }31 }32 }33 //右子树34 if (key.CompareTo(tree.key) > 0)35 {36 tree.right = Remove(key, value, tree.right);37 38 if ((Height(tree.right) - Height(tree.left) == 2))39 {40 //此时是右右旋转41 if (key.CompareTo(tree.right.key) > 0)42 {43 tree = RotateRR(tree);44 }45 else46 {47 //属于右左旋转48 tree = RotateRL(tree);49 }50 }51 }52 /*相等的情况*/53 if (key.CompareTo(tree.key) == 0)54 {55 //判断里面的HashSet是否有多值56 if (tree.attach.Count > 1)57 {58 //实现惰性删除59 tree.attach.Remove(value);60 }61 else62 {63 //有两个孩子的情况64 if (tree.left != null && tree.right != null)65 {66 //根据平衡二叉树的中顺遍历,需要找到”有子树“的最小节点67 tree.key = FindMin(tree.right).key;68 69 //删除右子树的指定元素70 tree.right = Remove(tree.key, value, tree.right);71 }72 else73 {74 //自减高度75 tree = tree.left == null ? tree.right : tree.left;76 77 //如果删除的是叶子节点直接返回78 if (tree == null)79 return null;80 }81 }82 }83 84 //统计高度85 tree.height = Math.Max(Height(tree.left), Height(tree.right)) + 1;86 87 return tree;88 }89 #endregion
5: 测试
不像上一篇不能在二叉树中灌有序数据,平衡二叉树就没关系了,我们的需求是检索2012-7-30 4:00:00 到 2012-7-30 5:00:00
的登陆用户的ID,数据量在500w,看看平衡二叉树是如何秒杀对手。
wow,相差98倍,这个可不是一个级别啊...AVL神器。
联系客服