数据结构：AVL树 gaunthan Posted on Jan 5 2017 ? Searching ? ? Data Structures ? ## 定义 AVL 树是最先发明的自平衡二叉查找树，它得名于它的发明者Adelson-Velskii 和 Landis。所谓的平衡条件是：**任何节点的深度均不能过深**。 一棵 AVL 树是其每个节点的左子树和右子树的高度最多差1的二叉查找树（空树的高度定义为-1）。 除去可能的插入操作外，所有的树操作都可以以时间$O(logN)$运行。当进行插入操作时，需要更新通向根结点路径上的那些结点的所有平衡信息，因为插入一个结点有可能会破坏AVL树的特性。在插入以后，只有那些从插入点到根结点的路径上的结点的平衡状态可能被改变，因为只有这些结点的子树可能会发生变化。 当沿着这条路径上行到根结点并更新平衡信息时，可以找到一个结点，它破坏了AVL的特性。在第一个这样的结点处进行几步调整，可使这棵树重新平衡，并再次满足AVL树的特性。 ## 关键操作 ### 单旋转 假设插入位置在子树X处。如下图，可见子树X已经长出一层，这使得它比子树 Z 深出 2 层，因此破坏了 AVL 特性：  这样的操作只需要一部分指针改变，结果得到另外一棵二叉查找树，它是AVL树，因为X向上移动了一层，Y停在原来的水平上，而Z下移一层。K2和K1不仅满足AVL要求，而且它们的子树都恰好在同一高度上。不仅如此，整个树的新高度与插入前原树的高度相同，而插入操作却使得子树X长高了。因此，通向根节点的路径高度不需要进一步的修正，因此也不需要进一步的旋转。这意味着只需进行一次调整操作就使得树重新平衡。 上图的这种待平衡的情况被称为左/左平衡，即如果插入点在树的左孩子的左子树，则进行一次单旋转就可使树重新平衡，注意旋转操作是向右边旋转的，简称右旋。 而如果插入点在树的右孩子的右子树，则被称为右/右平衡，它与左/左是镜像的关系，因此只需一次左旋即可。 ### 双旋转 当插入点在内部的时候，如下图：  由于子树Y太深，单旋转没有减低它的深度。解决这个问题的双旋转在下图给出：  上图的这种情况被称为左/右平衡，即插入点在左孩子的右子树。这种情况下需要进行双旋转操作：先左旋，后右旋。 对于插入点在右孩子的左子树的情况，即右/左平衡，其与左/右平衡呈镜像关系，因此也是需要一次双旋转操作：先右旋，后左旋。 ## 实现 我有实现一个比较完整的程序来操作AVL树，以供学习。代码和程序已经放到了我的Github上：[AvlTreeLab](https://github.com/gaunthan/AvlTreeLab)。 赏 Wechat Pay Alipay 数据结构：完全二叉树 数据结构：二叉查找树
