如何从键集10,20,5,4,3,2,30,40构建AVL树？求分步指导
2026-6-12
AVL树构建分步指南（键序列：10, 20, 5, 4, 3, 2, 30, 40）
AVL树的核心规则是每个节点的左右子树高度差（平衡因子）绝对值≤1，平衡因子定义为左子树高度 - 右子树高度。以下是逐个插入键的完整流程，包含失衡判断与旋转操作：
步骤1：插入10
树仅包含根节点10，左右子树高度均为0，平衡因子为0，完全平衡。
10
步骤2：插入20
按二叉搜索树（BST）规则，20作为10的右子节点。
- 10的平衡因子：
0 - 1 = -1（绝对值≤1，平衡）
10 \ 20
步骤3：插入5
5作为10的左子节点。
- 10的平衡因子：
1 - 1 = 0（平衡）
10 / \ 5 20
步骤4：插入4
4作为5的左子节点。
- 5的平衡因子：
1 - 0 = 1 - 10的平衡因子：
2 - 1 = 1（绝对值≤1，平衡）
10 / \ 5 20 / 4
步骤5：插入3
3作为4的左子节点，此时触发失衡：
- 4的平衡因子：
1 - 0 = 1（高度2） - 5的平衡因子：
2 - 0 = 2（高度3） - 10的平衡因子：
3 - 1 = 2（绝对值>1，LL型失衡：失衡节点的左子树平衡因子为1）
旋转操作：对10执行右旋
- 将5提升为新根节点
- 原根10变为5的右子节点
- 5的右子树（空）转为10的左子树
旋转后树结构：
5 / \ 4 10 / \ 3 20
所有节点平衡因子绝对值均≤1，恢复平衡。
步骤6：插入2
2作为3的左子节点，触发失衡：
- 3的平衡因子：
1 - 0 = 1（高度2） - 4的平衡因子：
2 - 0 = 2（绝对值>1，LL型失衡）
旋转操作：对4执行右旋
- 将3提升为5的左子节点，替代4的位置
- 原节点4变为3的右子节点
- 3的右子树（空）转为4的左子树
旋转后树结构：
5 / \ 3 10 / \ \ 2 4 20
恢复平衡。
步骤7：插入30
30作为20的右子节点，触发失衡：
- 20的平衡因子：
0 - 1 = -1（高度2） - 10的平衡因子：
0 - 2 = -2（绝对值>1，RR型失衡：失衡节点的右子树平衡因子为-1）
旋转操作：对10执行左旋
- 将20提升为5的右子节点，替代10的位置
- 原节点10变为20的左子节点
- 20的左子树（空）转为10的右子树
旋转后树结构：
5 / \ 3 20 / \ / \ 2 4 10 30
恢复平衡。
步骤8：插入40
40作为30的右子节点，检查平衡因子：
- 30的平衡因子：
0 - 1 = -1 - 20的平衡因子：
1 - 2 = -1 - 5的平衡因子：
2 - 2 = 0
所有节点平衡因子绝对值均≤1，无需旋转，最终AVL树结构为：
5 / \ 3 20 / \ / \ 2 4 10 30 \ 40
内容的提问来源于stack exchange，提问作者shakir Sumon
相关产品推荐
相关产品推荐
