AVL树
- AVL树定义:AVL树是一种自平衡二叉搜索树,每个节点都有一个平衡因子(左子树高度减去右子树高度),其值为 -1、0 或 +1。
- 节点旋转:为保持平衡,AVL树通过左旋、右旋、左-右旋和右-左旋四种旋转操作调整树的结构。
- 操作复杂度:在AVL树上执行插入、删除和搜索操作的时间复杂度均为O(log n),使其适用于大型数据库和索引记录。
AVL 树是一种自平衡二叉搜索树,其中每个节点维护额外的信息,称为平衡因子,其值为 -1、0 或 +1。
AVL 树以其发明者 Georgy Adelson-Velsky 和 Landis 的名字命名。
平衡因子