树的平衡：AVL树

4.1 不平衡树的问题

在普通（不平衡）树中添加元素时，可能会发生一些不愉快的现象。

1. 树高增加：

在不平衡树中，树的高度可能达到 n（其中 n 是节点数），这会导致性能下降。

基本操作（查找、插入、删除）的执行时间在最坏情况下会变成 O(n)。

2. 节点分布不均匀：

在不平衡树中，某些子树可能包含的节点数量显著多于其他子树，这导致内存使用不当和处理时间增加。

3. 操作执行时间变长：

在不平衡树中，由于树高增加，查找、插入和删除操作需要更多时间。

不平衡树的例子：

在这个例子中，树实际上变成了一个链表，操作的执行时间变成了线性的。

4.2 AVL树的定义及其属性

AVL树（以其发明者Adelson-Velsky和Landis命名）是一种平衡的二叉搜索树，其中任何节点的左子树和右子树的高度差不超过1。

AVL树的属性：

1. 平衡性：

任何节点的左子树和右子树的高度差不超过1。

这确保了树的高度为 O(log n)，其中 n 是节点数，保证了查找、插入和删除操作的高效执行。

2. 二叉搜索树：

AVL树具备所有二叉搜索树的属性：对于任何节点，左子树中的所有键都小于该节点的键，右子树中的所有键都大于该节点的键。

3. 自动平衡：

在每次插入或删除操作后，进行树的平衡以保持其属性。

4.3 树的平衡示例

旋转是用于在插入或删除节点后恢复AVL树平衡的操作。主要有四种旋转：左旋、右旋、左-右旋和右-左旋。

1. 左旋 (Left Rotation)：

在左旋中，节点 x 上升，右子节点 y 成为其父节点。y 的左子树成为 x 的右子树。

2. 右旋 (Right Rotation)：

在右旋中，节点 x 上升，左子节点 y 成为其父节点。y 的右子树成为 x 的左子树。

3. 左-右旋 (Left-Right Rotation)：

首先在左子节点上执行左旋，然后在该节点上执行右旋。

4. 右-左旋 (Right-Left Rotation)：

首先在右子节点上执行右旋，然后在该节点上执行左旋。

4.4 AVL树中的基本操作

AVL树中的基本操作包括插入、删除和查找。

插入 (Insertion)

需要在AVL树中插入新节点并在需要时平衡它。

步骤：

1. 插入节点：
   • 从树的根节点开始，递归地找到新节点的正确位置，通过比较其值与当前节点。
   • 在找到的位置插入新节点，就像在普通二叉搜索树中一样。
2. 更新高度：
   • 插入后，更新从新节点到树根的所有节点的高度。
3. 平衡树：
   • 检查从新节点到树根路径上的每个节点的平衡。
   • 如果任何节点的平衡被破坏（左子树和右子树的高度差大于1），执行相应的旋转以恢复平衡。

例子：

2. 删除 (Deletion)

需要从AVL树中删除节点并在需要时平衡它。

步骤：

1. 查找并删除节点：

• 从树的根节点开始，递归地找到要删除的节点。
• 像在普通二叉搜索树中一样删除节点：
• 如果节点是叶子节点，直接删除它。
• 如果节点有一个子节点，用其子节点替换节点。
• 如果节点有两个子节点，找到右子树中的最小节点（或左子树中的最大节点），将其值复制到要删除的节点中，并递归地删除右子树中的最小节点。

2. 更新高度：

• 删除后，更新从删除的节点到树根的所有节点的高度。

3. 平衡树：

• 检查从删除的节点到树根路径上的每个节点的平衡。
• 如果任何节点的平衡被破坏，执行相应的旋转以恢复平衡。

例子：

3. 查找 (Search)

需要在AVL树中找到具有指定值的节点。

步骤：

1. 递归查找：

• 从树的根节点开始，递归地将目标值与当前节点比较。
• 如果值小于当前节点，进入左子树。
• 如果值大于当前节点，进入右子树。
• 如果值与当前节点匹配，则返回该节点。

例子：