数据结构: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 数据结构:完全二叉树 数据结构:二叉查找树