AVL树(AVL Tree)
介绍
AVL树是一种自平衡二叉搜索树,它在普通二叉搜索树的基础上增加了平衡因子的概念,保证树的任何节点的左右子树高度差不超过1,保证查找、插入和删除操作的时间复杂度稳定在O(log n)。
AVL树中的几个关键概念:
- 节点(Node):树的基本组成单元,包含数据、左右子节点指针及高度信息
- 平衡因子(Balance Factor):节点左子树高度减去右子树高度的差值
- 高度(Height):从节点到其最远叶子节点的路径长度
- 旋转(Rotation):保持平衡的核心操作,包括左旋、右旋、左右旋和右左旋
核心特性
- 自平衡性:任何节点的左右子树高度差不超过1
- 二叉搜索性质:左子树所有节点值小于父节点,右子树所有节点值大于父节点
- 平衡因子:每个节点都有-1、0或1的平衡因子
- 高度为O(log n):由于严格的平衡要求,树的高度被限制在O(log n)
- 旋转操作:通过四种旋转操作维持树的平衡性
基本操作
1. 查找元素
...