平衡二叉树（AVL）

一、平衡二叉树的基本概念

1. 定义：
   • 平衡二叉树是一棵二叉排序树，其任何节点的两个子树的高度差（平衡因子）的绝对值不超过1。
   • 平衡因子（Balance Factor，BF）：节点的左子树高度减去右子树高度的值。在AVL树中，平衡因子的取值只能为-1、0或1。
2. 目的：
   • 保持二叉排序树的平衡，使得查找、插入和删除操作的时间复杂度均为O(logn)。

二、平衡二叉树的性质

1. 高度平衡：
   • 平衡二叉树的任意节点的左右子树都是平衡二叉树，且高度差不超过1。
2. 查找效率：
   • 在平衡二叉树中查找一个节点，最多需要比较$$log_2N$$次（其中 N是树中节点的数量），保证了较高的查找效率。

三、平衡二叉树的调整方法

1. 失衡类型：
   • 在插入或删除节点后，平衡二叉树可能会出现失衡。失衡分为四种类型：左左失衡（LL）、左右失衡（LR）、右右失衡（RR）和右左失衡（RL）。
2. 调整方法：
   • 单旋转：
   • 左左失衡（LL）：对失衡节点进行右旋。

• 右右失衡（RR）：对失衡节点进行左旋。

• 双旋转：
• 左右失衡（LR）：先对失衡节点的左子节点进行左旋，再对失衡节点进行右旋。

• 右左失衡（RL）：先对失衡节点的右子节点进行右旋，再对失衡节点进行左旋。

四、平衡二叉树的插入操作

1. 插入过程：
   • 首先按照二叉排序树的插入规则，将新节点插入到适当的位置。
   • 然后从插入节点开始，向上回溯，检查每个节点的平衡因子。
   • 如果发现失衡，则根据失衡类型进行相应的旋转调整。
   【注意】①LR和RL旋转时，新节点究竟是插入C的左子树还是插入C的右子树，不影响旋转过程。
   ②每次的调整对象都是最小不平衡子树，也就是插入路径上的理解点最近的平衡因子的绝对值大于1的结点作为根的因子。
   
   例：{15,3,7,10,9,8}构造一棵平衡二叉树
   
2. 时间复杂度：
   • 插入操作的时间复杂度为O(logn)，因为在最坏情况下，需要回溯到根节点并进行一次或多次旋转。

五、平衡二叉树的删除操作

1. 删除过程：
   • 首先按照二叉排序树的删除规则，删除指定节点。
   • 然后从删除节点开始，向上回溯，检查每个节点的平衡因子。
   • 如果发现失衡，则根据失衡类型进行相应的旋转调整。
2. 时间复杂度：
   • 删除操作的时间复杂度也为O(logn)，原因与插入操作相同。

六、平衡二叉树的查找操作

• 平衡二叉树的查找操作与二叉排序树相同，从根节点开始，根据目标值与当前节点值的比较结果，决定向左子树或右子树移动，直到找到目标值或遍历到叶子节点。