初次学习数据结构和算法是几年前的事情了，当时遇到的困难没有记录下来。回过头来复习，记录下学习时遇到的问题。
平衡二叉树（二叉搜索树）（ALV树）
可以保证查询效率。在此之前先学习二叉排序树（BST —— Binary Sort Tree）。
在高度为h的ALV树中，最小节点数 S(h) = S( h – 1 ) + S( h – 2 ) + 1。对于h = 0，S(h) = 1；h = 1，S(h) = 2。
函数S(h)与斐波那契树密切相关。下面给出指定树高度时，最少节点的ALV树：
摘自——《数据结构与算法分析：c语言描述》
初次学习ALV旋转时，总是纠结于 ” 旋转 ” 二字上，想象它具体是如何旋转的，在纸上涂涂画画感觉 ” 旋转 ” 二字并不恰当。
插入结点有可能破坏平衡，旋转的目的是结点插入后，能够维持树的平衡。此处不包含删除！！！删除假设为惰性删除
插入节点会导致某一个节点的左右子树深度差为 2 。只需要将这个最小的不平横子树调整为平衡即可
下面分别举例 LL旋转、RR旋转、LR旋转、RL旋转 （有的地方分类时只分左旋转、右旋转和双旋转）
LL旋转： 新节点的位置在最小不平衡的子树的根节点的左孩子的左子树
维持平衡的方式：
root的左孩子（黄色）替代root（红色）的位置，不必关注具体指针的变化，理解节点的变化，指针的变化自然而然就出来了。
RR旋转：新节点的位置在最小不平衡的子树的根节点的右孩子的右子树。与LL旋转类似，不多赘述。
LR旋转：新节点的位置在最小不平衡的子树的根节点的左孩子的右子树。
维持平衡的方式：让root的左孩子的右孩子（蓝色）取代root
RL旋转：新节点的位置在最小不平衡的子树的根节点的右孩子的左子树。与LR旋转类似，不多赘述。
Original: https://www.cnblogs.com/tyt0o0/p/16676267.html
Author: 长寿奉孝
Title: 平衡二叉树（ALV树）旋转问题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587435/
转载文章受原作者版权保护。转载请注明原作者出处！