AVL树

来自"NOCOW"

本文在GNU自由文档许可证之条款下提供

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在1962年的论文 "An algorithm for the organization of information" 中发表了它。

节点的平衡因子是它的右子树的高度减去它的左子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

目录

• 1 操作
  • 1.1 插入
  • 1.2 删除
  • 1.3 查找
• 2 参考实现
• 3 使用高度替代平衡因子
• 4 平衡因子的推算

[编辑] 操作

AVL树的基本操作一般涉及运做同在不平衡的二叉查找树所运做的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL 旋转"。

假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a(即a是离插入点最近，且平衡因子绝对值超过1的祖先结点)，则失去平衡后进行进行的规律可归纳为下列四种情况：

1. 单向右旋平衡处理RR：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作；
2. 单向左旋平衡处理LL：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作；
3. 双向旋转（先左后右）平衡处理LR：由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
4. 双向旋转（先右后左）平衡处理RL：由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

[编辑] 插入

向AVL树插入可以通过如同它是未平衡的二叉查找树一样把给定的值插入树中，接着自底向上向根节点折回，于在插入期间成为不平衡的所有节点上进行旋转来完成。因为折回到根节点的路途上最多有 1.5 乘 log n 个节点，而每次 AVL 旋转都耗费恒定的时间，插入处理在整体上耗费 O(log n) 时间。

在平衡的二叉排序树Balanced BST上插入一个新的数据元素e的递归算法可描述如下：

1. 若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增1；
2. 若e的关键字和BBST的根结点的关键字相等，则不进行；
3. 若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加(+1)时，分别就下列不同情况处理之：
   1. BBST的根结点的平衡因子为-1(右子树的深度大于左子树的深度，则将根结点的平衡因子更改为0，BBST的深度不变；
   2. BBST的根结点的平衡因子为0（左、右子树的深度相等）：则将根结点的平衡因子更改为1，BBST的深度增1；
   3. BBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）：则若BBST的左子树根结点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；
4. 若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加(+1)时，分别就不同情况处理之。

[编辑] 删除

从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点，接着直接剪除这个叶子节点来完成。因为在旋转成叶子节点期间最多有 log n个节点被旋转，而每次 AVL 旋转耗费恒定的时间，删除处理在整体上耗费 O(log n) 时间。（感觉这样处理之后，有可能这个树就不一定还是AVL树了，正确应该在删除的时候也像插入的时候一样，需要旋转调整的吧）

[编辑] 查找

在AVL树中查找同在一般BST完全一样的进行，所以耗费 O(log n) 时间，因为AVL树总是保持平衡的。不需要特殊的准备，树的结构不会由于查询而改变。(这是与伸展树查找相对立的，它会因为查找而变更树结构。)

[编辑] 参考实现

[AVL C++ && 陈启峰——PASCAL版]

[编辑] 使用高度替代平衡因子

在linux早期的内核中，AVL树便是用存储高度来判别树是否平衡的，这样的好处是能直接的得到任一节点的高度，旋转时的更新也更容易（参看下面的推算）。使用高度替代平衡因子的实现：AVL C++ Alternative Height Based

[编辑] 平衡因子的推算

在AVL树的旋转过程中，平衡因子（高度）的改变可以通过旋转的类型推算得到。下面的推算是从本人的code中摘取的注释，其中：

* bf(N) 节点N的平衡因子(balance factor)* h(N)  节点N的高度    (height) * No    旋转前的节点N  (old node)* Nn    旋转后的节点N  (new node)

* 高度和平衡因子保持不变的节点用数字 1, 2, 3...表示

/* LL: right rotate

*  *       (N)                (L)*      /   \              /   *    (L)    3    ==>     1    (N)  *   /   \                    /   *  1     2                  2     3*** how to get bf(Nn) ? ** bf(No) = h(Lo)-h(3)* bf(Nn) = h(2)-h(3)* bf(No)-bf(Nn) = h(Lo)-h(2)*               = max(h(1), h(2))+1-h(2)*               = max(h(1)-h(2), 0)+1*               = max(bf(Lo), 0)+1** bf(Nn) = bf(No)-(max(bf(Lo), 0)+1)** Result:** bf(N) -= max(bf(bf(Lo), 0)+1*

* how to get bf(Ln) ?* * bf(Lo) = h(1)-h(2)* bf(Ln) = h(1)-h(Nn)* bf(Ln)-bf(Lo) = h(2)-h(Nn)*               = h(2)-max(h(2), h(3))-1*               = min(0, h(2)-h(3))-1*               = min(0, bf(Nn))-1** bf(Ln) = bf(Lo)+(min(0, bf(Nn))-1)** Result:** bf(L) += min(0, bf(Nn))-1*

* how to get height ?** h(Nn) = max(h(2), h(3))+1* h(Ln) = max(h(1), h(Nn))+1**/

/* RR: left rotate

**    (N)                (R)*   /   \              /   *  1    (R)    ==>   (N)    3*      /   \        /   *     2     3      1     2**

* how to get bf(Nn) ? ** bf(No) = h(1)-h(Ro)* bf(Nn) = h(1)-h(2)* bf(No)-bf(Nn) = h(2)-h(Ro)*               = h(2)-max(h(2), h(3))-1*               = min(0, h(2)-h(3))-1*               = min(0, bf(Ro))-1** bf(Nn) = bf(No)-(min(0, bf(Ro))-1)** Result:** bf(N) -= min(0, bf(Ro))-1*

* how to get bf(Rn) ?* * bf(Ro) = h(2)-h(3)* bf(Rn) = h(Nn)-h(3)* bf(Rn)-bf(Ro) = h(Nn)-h(2)*               = max(h(1), h(2))+1-h(2)*               = max(h(1)-h(2), 0)+1*               = max(bf(Nn), 0)+1** bf(Rn) = bf(Ro)+(max(bf(Nn), 0)+1)** Result:* * bf(R) += max(bf(Nn), 0)+1*

* how to get height ?* * h(Nn) = max(h(1), h(2))+1* h(Rn) = max(h(Nn), h(3))+1**/

/* LR: left-right rotate

* *          (N)                (LR)*         /   \               /   *       (L)    4   ==>      (L)   (N)  *      / \                  / \   / *     1  (LR)              1   2 3   4*        / *       2   3**  note that left-right rotate could be implemented as a call to *  left_rotate(L) followed by a call to right_rotate(N).*

* how to get bf(Ln) ?* * bf(Lo) = h(1)-h(LRo)* bf(Ln) = h(1)-h(2)* bf(Lo)-bf(Ln) = h(2)-h(LRo)*               = h(2)-max(h(2), h(3))-1*               = min(0, h(2)-h(3))-1*               = min(0, bf(LRo))-1** bf(Ln) = bf(Lo)-(min(0, bf(LRo))-1)** Result:* * bf(L) -= min(0, bf(LRo))-1*

* how to get bf(Nn) ? ** bf(No) = h(Lo)-h(4)* bf(Nn) = h(3)-h(4)* bf(No)-bf(Nn) = h(Lo)-h(3)*               = max(h(1), max(h(2), h(3))+1)+1-h(3)*               = max(h(1)-h(3), max(h(2)-h(3), 0)+1)+1*               = max(h(1)-h(3), max(bf(LRo), 0)+1)+1* bf(Ln) = h(1)-h(2)* bf(LRo) = h(2)-h(3)* h(1)-h(3) = bf(Ln)+bf(LRo)** bf(Nn) = bf(No)-(max(bf(Ln)+bf(LRo), max(bf(LRo), 0)+1)+1)** Result:* * bf(N) -= max(bf(Ln)+bf(LRo), max(bf(LRo), 0)+1)+1*

* how to get bf(LRn) ? ** bf(LRo) = h(2)-h(3)* bf(LRn) = h(Ln)-h(Nn)* bf(LRn)-bf(LRo) = h(Ln)-h(2)+h(3)-h(Nn)*               = max(h(1), h(2))+1-h(2)+h(3)-max(h(3), h(4))-1*               = max(h(1)-h(2), 0)+min(0, h(3)-h(4))*               = max(bf(Ln), 0)+min(0, bf(Nn))** bf(LRn) = bf(LRo)+(max(bf(Ln), 0)+min(0, bf(Nn)))** Result:* * bf(LR) += max(bf(Ln), 0)+min(0, bf(Nn))**/

/* right-left rotate

* *          (N)                  (RL)*         /   \                 /   *        1     (R)     ==>    (N)   (R)  *             /  \            / \   / *           (RL)  4          1   2 3   4*           / *          2   3**  note that right-left rotate could be implemented as a call to *  right_rotate(R) followed by a call to left_rotate(N).** how to get bf(Rn) ?* * bf(Ro) = h(RLo)-h(4)* bf(Rn) = h(3)-h(4)* bf(Ro)-bf(Rn) = h(RLo)-h(3)*               = max(h(2), h(3))+1-h(3)*               = max(h(2)-h(3), 0)+1*               = max(bf(RLo), 0)+1** bf(Rn) = bf(Ro)-(max(bf(LRo), 0)+1)** Result:* * bf(R) -= max(bf(LRo), 0)+1*

* how to get bf(Nn) ? ** bf(No) = h(1)-h(Ro)* bf(Nn) = h(1)-h(2)* bf(No)-bf(Nn) = h(2)-h(Ro)*               = h(2)-max(max(h(2), h(3))+1, h(4))-1*               = min(h(2)-max(h(2), h(3))-1, h(2)-h(4))-1*               = min(min(0, h(2)-h(3))-1, h(2)-h(4))-1*               = min(min(0, bf(RLo))-1, h(2)-h(4))-1* bf(Rn) = h(3)-h(4)* bf(RLo) = h(2)-h(3)* h(2)-h(4) = bf(Rn)+bf(RLo)** bf(Nn) = bf(No)-(min(min(0, bf(RLo))-1, bf(Rn)+bf(RLo))-1)** Result:* * bf(N) -= min(bf(Rn)+bf(RLo), min(bf(RLo), 0)-1)-1*

* how to get bf(RLn) ?** bf(RLo) = h(2)-h(3)* bf(RLn) = h(Nn)-h(Rn)* bf(RLn)-bf(RLo) = h(Nn)-h(2)+h(3)-h(Rn)*               = max(h(1), h(2))+1-h(2)+h(3)-max(h(3), h(4))-1*               = max(h(1)-h(2), 0)+min(0, h(3)-h(4))*               = max(bf(Nn), 0)+min(0, bf(Rn))** bf(RLn) = bf(RLo)+(max(bf(Nn), 0)+min(0, bf(Rn)))** Result:* * bf(RL) += max(bf(Nn), 0)+min(0, bf(Rn))*

*/