Day-23 AVL Tree

树的高度(height of the tree)

在Binary Search tree中，我们知道我们可以在的时间内，完成Delete, find min, max, largest, smaller等操作。

下面这是一棵完美的二元树

他的树高为

而下面这是一棵高度为的树，也称为一条路径(path)

而我们会称第一棵完美二元搜寻树为平衡的，而下面这一棵高度为的树是不平衡的。

树高的定义为找出树根到叶节点的最长路径长，定义完树高之後，我们可以根树树高来定义这棵树平不平衡，如果这个树的高度为，则我们称这棵树是平衡的，唯有树是平衡的，才可以保证我们上面那一些操作的效率是好的。

而在昨天，我们也提及到了节点的高度，为节点到叶节点的最长路径长，我们也可以以一个公式来表示节点的高度

而为了使上面的公式在任何时候都可以运作，我们定义空节点的高度为-1，好处在於假设有一个叶节点，我们知道他的高度为0，则我们给他两个空节点作为左子节点和右子节点，两者高度皆为-1，这个假设底下，我们带入上面的公式可以得到叶节点的高度为0。

下面将介绍一种特殊的树，可以随时保持在平衡的状态，称为平衡二元搜寻树，为了保证他是平衡的，我们需要在每一个节点多新增一个资讯，也就是节点的高度，透过节点的高度来得知子树的高度，从而保持平衡。

平衡二元搜寻树(AVL Tree)

最简单平衡树的想法就是让左子树和右子树高度一模一样，但这件事情实际上是不可能的，会因为树的节点个数是奇数还是偶数而导致我们无法实现这一件事情。

我们定义AVL Tree为对於每一个左子节点的高度和右子节点的高度，两者之间的差异必须在正负1之间。

以上面这个例子来说，左边的树是一个AVL树，因为左子树的高度为3，右子树高度为2，两者只相差1。
而右边这棵树左子树的高度为3，右子树高度为1，两者相差为2，不符合定义。

AVL树的最糟糕情况会发生在每一个左子树和右子树之间相差的高度多余1，我们可以使用一些方法证明这一件事情，我们假设为构成高度为的AVL树所需要的最少节点个数，我们可以列出递回式来表示

整体树高为右子树高度为，左子树高度为，上方递回式由此而来。
上面这个递回式，看起来是曾相似... 没错，很像斐波那契数列，我们定义斐波那契数列为，则可以得到以下关系
，而又可以表示成,




，表示AVL树的高度上界
可以发现到我们得常数十分接近1，这代表高度和节点数量的关系，更精确地来说，一棵AVL树的高度大约为，接下来要探讨插入节点的问题，当我们插入节点时，可能会破坏掉AVL树的特性，如果特性被破坏，那麽我们必须在插入节点後，执行一些操作让树回复AVL树的特性，而这种操作称为旋转(rotation)。

举个例子，假设我们下方有一棵BST树，旁边数字表示节点的高度

我们试着插入23这个节点，并更新节点的高度

我们会发现到29, 26, 23这里的情况十分的糟糕，且平衡树的条件已被破坏，我们必须使用旋转的方式进行修复

旋转(rotation), 单旋转(single rotation), 双旋转(two rotations)

上面这个就是旋转的操作，我们可以发现到，两棵树使用Inorder走访的结果是相同的，表示都还是具备BST的性质。从左到右我们称为k2的右旋转，右到左称为k1的左旋转。

而上面那张图，我们要做的事情就是对29这个节点进行旋转操作

经过对29旋转操作後，我们又可以重新得到一棵AVL树了。

接着我们再插入55这个节点

我们会发现到，如果我们对50做右旋转，子树的高度会维持一样，无法保持AVL树的特性，而如果我们试着做左旋转，我们会发现情况会回到我们上面插入29的情况

我们可以再做一次旋转

而我们又可以重新得到AVL树了，我们称这种情况为双旋转(two rotations)，有可能我们有时候必须做出多於两次的旋转操作。

插入(insert)节点的情况

前面示范中，我们可以看到插入节点时，可能会违反AVL树的性质，因此我们需要在插入节点後，执行一些旋转的操作，这样才算是完成了整个插入节点的操作，而对於不同的插入情况，我们所需要做的旋转次数也不同，而下面将要归纳不同插入的情况。

• 如果k1的右子树是平衡的或是高度较高的，则对k1左旋转(单次旋转)
  
  k1不是AVL树，但k2是AVL树
• 否则对k3进行右旋转後，再对k1进行左旋转(双旋转)
  

AVL树用於排序

AVL树可以让insert的操作保持在内，而假设一个阵列中有个待排序的元素，则我们可以将个元素插入到AVL树中，然後做inorder遍历，插入n个元素需要的时间，inorder走访需要的时间，因此使用AVL树进行排序时时间复杂度为，和随机化quick sort以及heap sort一样好。

参考资料: geeksforgeeks, Introduction to algorithms 3rd, 图片来自网路