转载

每日一博 | AVL 树 - scala 实现

二叉查找树已经能够很好的应用到应用程序中，但它们在最坏的情况下性能还是很糟糕。考虑到如图所示这种情况：每日一博 | AVL 树 - scala 实现查找操作的性能完全等同于线性。而AVL树的查找操作，能够保证无论怎么构造它，运行时间一直对数级别的。一起来学习一下AVL树吧。

什么是AVL

AVL (Adelson-Velsky 和 Landis)树,是带有平衡条件的二叉查找树，这个平衡条件必须要容易保持，并且它保证树的深度是O(LogN).

一颗AVL树是其每个节点的左右子树节点高度最多差1的二叉查找树。

每日一博 | AVL 树 - scala 实现

平衡条件

我门上面说，一颗AVL树是其每个节点的左右子树节点高度最多差1的二叉查找树。左右子树的高度最多差1便是AVL树的平衡条件。

当进行插入操作时，我们需要更新通往根节点的所有节点的平衡信息。而插入操作隐含困难的原因在于，可能会破坏AVL树的特性（例如，考虑将6插入到图1的AVL树中将会破坏节点为8的平衡条件）。如果发生这种情形，那么就要考虑在插入完成之后重新回复节点的平衡信息。事实上，总可以通过对树进行简单的修正得到，我们称其为旋转(ratation).

在插入以后，只有那些从插入点到根节点的平衡条件可能变化，因为只有这些节点的字数可能发生变化。当我们沿着这条路路径行进到根节点，可以发现一个节点它的新平衡破坏了AVL树的特性。我们需要在这个节点重新平衡这棵树。

我们把必须重新平衡的节点叫做α。因为平衡条件是高度最多相差1，那么出现不平衡就是α点的高度相差为2。容易看出这种不平衡可能出现在下面这四种情况下：

对α的左儿子的左子树进行一次插入
对α的左儿子的右子树进行一次插入
对α的右儿子的左子树进行一次插入
对α的右儿子的右子树进行一次插入

1和4，2和3 是关于α点的镜像对称。因此理论上讲只有两种情况，当然编程上还是四种情况。

第一种情况是插入发生在外边的情况(即左-左的情况或者右-右的情况)，该情况是通过对树的一次单旋转来完成操作。

第二种情况是插入发生在内部的情形(即左-右的情况或者右-左的情况)，该情况通过稍微复杂点的双旋转操作来处理。

单旋转

下图显示了单旋转如何调整情形1。旋转前的图在左边，旋转后的图在右边。每日一博 | AVL 树 - scala 实现

让我们来分析具体的做法。节点K2不满足平衡条件，因为它的左子树比右子树深两层（图中的虚线表示树的各层）.

为使树恢复平衡，我们把节点X向上移一层，并把Z像下移一层，为此我们重新安排节点以形成一颗等价的树。如上图的右边部分。抽象的形容就是，把把树想象成一棵柔软灵活的树，抓住子节点K1，闭上眼睛使劲的摇动它，这样由于重力的作用，K1就变成了新的根。二叉树的性质告诉我们，在原树中K2>K1，这样在新树中，K2变成了K1的右儿子，Y变成了K2的左子树，而X、Z依然是K1的左子树和K2的右子树。

每日一博 | AVL 树 - scala 实现

让我们演示一个更长的例子，假设从初始的空的AVL树开始依次插入3、2、1,然后再依次插入4-7.

在插入关键字1的时候第一个问题就出现了，AVL性质在根处被破坏，我们在根和其左儿子之间施加单旋转操作来修正问题。下图是旋转之前和之后的两棵树。

每日一博 | AVL 树 - scala 实现

图中虚线连接的两个节点，它们是旋转的主体。下面我们插入关键字4这没有问题，在我们插入关键字5的时候，问题又出现了，平衡条件在关键字3处被破坏，而通过单旋转再次将问题修复。

每日一博 | AVL 树 - scala 实现

接下来插入6，平衡条件在根节点处被打破，因此我们在根处，在2、4之间施加一次单旋转操作。

每日一博 | AVL 树 - scala 实现

我们插入最后的关键字7，它导致另外的旋转。

每日一博 | AVL 树 - scala 实现

双旋转

单旋转对情形2、3无效愿因在于子树Y太深。单旋转没有降低它的深度。

每日一博 | AVL 树 - scala 实现

对于子树Y我们可以假设他有一个根和两棵子树（对应上图的K2、B、C）。

为了平衡期间，我们不能再把K3当成根了，而如上图所示K3和K1之间旋转又解决不了问题，唯一的选择是把K2当成根，这迫K1成为K2的左子树，K3成为K1的右子树，而K2的左子树成为K1的右子树，K2的右子树成为K3的左子树。容易看出最后得到的树满足AVL树的特征。

我们继续在前面例子的基础上以倒序插入10-16，接着插入8，再插入9.插入16很容易这并不破坏树的平衡,插入15会引起节点7处的高度不平衡，这属于情形3，需要通过右-左双旋转来解决。如图：

每日一博 | AVL 树 - scala 实现

下面我们来插入14，它也需要一个双旋转。此时修复树的旋转还是右-左双旋转

每日一博 | AVL 树 - scala 实现

如果现在插入13那么在根处就会出现不平衡，由于13不在4-7之间，我们知道只要一次单旋转就行.

每日一博 | AVL 树 - scala 实现

插入12也需要一次双旋转

每日一博 | AVL 树 - scala 实现

插入11、10都需要进行单旋转，接着我们插入8不需要进行旋转，这样就建成了一颗近乎理想的平衡树

每日一博 | AVL 树 - scala 实现

最后我们插入9，在节点10发生不平衡，这里满足情形2，对左儿子的右子树进行一次，需要一次双旋转。

每日一博 | AVL 树 - scala 实现

总结

现在让我们对上面的讨论做出总结，除几种情形外，编程的细节是相当简单的。为将节点X插入AVL树T中，我们递归的将X插入到T的子树中。如果子树的高度不变，那么插入完成；如果出现高度不平衡，那么找到不平衡点，做适当的单旋转或者双旋转，更新这些高度，从而完成插入。

scala实现

``` sealed trait AVLTree[+A] extends Serializable { def balance: Int

def depth: Int

def contains[B >: A](x: B)(implicit ordering: Ordering[B]): Boolean

def insert[B >: A](x: B)(implicit ordering: Ordering[B]): AVLTree[B]

def rebalance[B >: A]: AVLTree[B]

}

/* * 叶子节点 / case object Leaf extends AVLTree[Nothing] {

override val balance: Int = -1 override val depth: Int = 0

override def contains[B >: Nothing](x: B)(implicit ordering: Ordering[B]): Boolean = false

override def insert[B >: Nothing](x: B)(implicit ordering: Ordering[B]): AVLTree[B] = { Node(x, Leaf, Leaf) }

override def rebalance[B >: Nothing]: AVLTree[B] = this

}

case class Node[A](value: A, left: AVLTree[A], right: AVLTree[A]) extends AVLTree[A] { override def balance: Int = right.depth - left.depth

override def depth: Int = math.max(left.depth, right.depth)

override def contains[B >: A](x: B)(implicit ordering: Ordering[B]): Boolean = ???

override def insert[B >: A](x: B)(implicit ordering: Ordering[B]): AVLTree[B] = { val cmp = ordering.compare(x,value) if (cmp<0){ Node(value, left.insert(x),right).rebalance } else if (cmp > 0){ Node(value, left, right.insert(x)).rebalance } else { this } }

override def rebalance[B >: A] = { if (-2 == balance){ if (1 == left.balance){ doubleRightRotation } else { rightRotation } } else if(2 == balance) { if (-1 == right.balance){ doubleLeftRotation }else { leftRotation } } else { this } }

/ * 5 * / 6 * 6 ---- 左单旋转 ---> / / * / 5 7 * 7 * * 在节点5 发生不平衡 5的右节点成为新的根节点 / private def leftRotation[B >: A] = { if (Leaf != right) { val r = right.asInstanceOf[Node[A]] Node(r.value, Node(value, left, r.left), r.right) } else { sys.error("should not happen.") } }

/ * 7 * / 6 * 6 ---- 右单旋转 ---> / / * / 5 7 * 5 * * 在节点7 发生不平衡 7的左节点成为新的根节点 / private def rightRotation[B >: A] = { if (Leaf != left) { val l = left.asInstanceOf[Node[A]] Node(l.value, l.left, Node(value, l.right, right)) } else { sys.error("should not happen.") }

}

/ * 左双旋转 * * 5 5 * / / 6 * 7 ----step1 ---> 6 ---step2---> / / * / / 5 7 * 6 7 * * 在节点5处不平衡 * step1 : 节点5的右节点做一次右旋转 * step2 : 左旋转 * / private def doubleLeftRotation[B >: A] = { if (Leaf != right) { val r = right.asInstanceOf[Node[A]] val rightRotated = r.rightRotation Node(rightRotated.value, Node(value, left, rightRotated.left), rightRotated.right) } else { sys.error("should not happen.") } }

/ * 右双旋转 * * 7 7 * / / 6 * 5 ----step1 ---> 6 ---step2---> / / * / / 5 7 * 6 5 * * 在节点7处不平衡 * step1 : 节点7的左节点做一次左旋转 * step2 : 右旋转 * / private def doubleRightRotation[B >: A] = { if (Leaf != left) { val l: Node[A] = left.asInstanceOf[Node[A]] val leftRotated = l.leftRotation Node(leftRotated.value, leftRotated.left, Node(value, leftRotated.right, right)) } else sys.error("Should not happen.") }

}

```