avl树左旋右旋的理解

我就是我 2022-08-01 02:48 81阅读 0赞

一直没搞懂非平衡二叉树变平衡二叉树时左旋右旋，今天下定决心搞懂，然后在众多博客中终于找到了这样一篇，非常形象，记录如下：

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

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

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

[![avl树旋转的图形描述。][avl]][avl_avl]

以上内容转自[维基百科AVL树][AVL]

从图中可以比较形象的看出所谓左旋右旋的旋转支点是三个主节点中大小居中的那个节点，左旋就是左边的节点降下来，右旋就是右边的节点降下来，都成为中间节点的子树。

左右双旋分解就是先将左侧节点降为左子树，右边节点将为右子树。当然中间有合并子树的过程，这里没有细说。

高度为h的AVL树，节点数N最多![2^h -1][2_h -1]； 最少![\\frac \{ \\Phi ^\{h+2\}\} \{\\sqrt\{5\}\} -1][frac _ _Phi _h_2_ _sqrt_5_ -1] ( 其中![\\Phi = \\frac \{1 + \\sqrt\{5\} \} \{2\} = 1.618][Phi _ _frac _1 _ _sqrt_5_ _ _2_ _ 1.618] )N是h的斐波那契数列。

[Link 1]: http://zh.wikipedia.org/wiki/%E8%87%AA%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91
[Link 2]: http://zh.wikipedia.org/w/index.php?title=%E5%AD%90%E8%8A%82%E7%82%B9&action=edit&redlink=1
[Link 3]: http://zh.wikipedia.org/w/index.php?title=%E9%AB%98%E5%BA%A6%E5%B9%B3%E8%A1%A1%E6%A0%91&action=edit&redlink=1
[O]: http://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7
[Link 4]: http://zh.wikipedia.org/wiki/%E6%A0%91%E6%97%8B%E8%BD%AC
[G.M. Adelson-Velsky]: http://zh.wikipedia.org/w/index.php?title=Georgii_Adelson-Velsky&action=edit&redlink=1
[E.M. Landis]: http://zh.wikipedia.org/w/index.php?title=Yevgeniy_Landis&action=edit&redlink=1
[Link 5]: http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91
[avl]: http://upload.wikimedia.org/wikipedia/commons/c/c7/Tree_Rebalancing.png
[avl_avl]: http://zh.wikipedia.org/wiki/File:Tree_Rebalancing.png
[AVL]: http://zh.wikipedia.org/wiki/AVL%E6%A0%91#.E6.8F.92.E5.85.A5
[2_h -1]: http://upload.wikimedia.org/math/2/b/3/2b3bdb8bb9b99bb338b4a6455f431307.png
[frac _ _Phi _h_2_ _sqrt_5_ -1]: http://upload.wikimedia.org/math/d/5/f/d5fe1a3ee691062fc4ce9c4d3a2e6dc0.png
[Phi _ _frac _1 _ _sqrt_5_ _ _2_ _ 1.618]: /images/20220731/c98a86018a664ce09638c7cf8ce68837.png