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 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
[编辑] 操作AVL树的基本操作一般涉及运做同在不平衡的二叉查找树所运做的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL 旋转"。 假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a(即a是离插入点最近，且平衡因子绝对值超过1的祖先结点)，则失去平衡后进行进行的规律可归纳为下列四种情况：
[编辑] 插入向AVL树插入可以通过如同它是未平衡的二叉查找树一样把给定的值插入树中，接着自底向上向根节点折回，于在插入期间成为不平衡的所有节点上进行旋转来完成。因为折回到根节点的路途上最多有 1.5 乘 log n 个节点，而每次 AVL 旋转都耗费恒定的时间，插入处理在整体上耗费 O(log n) 时间。 在平衡的二叉排序树Balanced BST上插入一个新的数据元素e的递归算法可描述如下：
[编辑] 删除从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点，接着直接剪除这个叶子节点来完成。因为在旋转成叶子节点期间最多有 log n个节点被旋转，而每次 AVL 旋转耗费恒定的时间，删除处理在整体上耗费 O(log n) 时间。（感觉这样处理之后，有可能这个树就不一定还是AVL树了，正确应该在删除的时候也像插入的时候一样，需要旋转调整的吧） [编辑] 查找在AVL树中查找同在一般BST完全一样的进行，所以耗费 O(log n) 时间，因为AVL树总是保持平衡的。不需要特殊的准备，树的结构不会由于查询而改变。(这是与伸展树查找相对立的，它会因为查找而变更树结构。) [编辑] 参考实现[编辑] 使用高度替代平衡因子在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)) * */ |
|
|
