数据结构与算法——平衡二叉树（AVL Tree）
数据结构与算法——平衡二叉树（AVL Tree）
构建一个二叉排序树时，如果构建序列是完全有序的，则会出现这样的情况：
显然这种情况会使得二叉搜索树退化成链表。当出现这样的情况，二叉排序树的查找也就退化成了线性查找，所以我们需要合理调整二叉排序树的形态，使得树上的每个结点都尽量有两个子结点，这样整个二叉树的高度就会大约在log(n)log(n) 左右，其中 nn 为结点个数。
基本性质
AVL树也称为平衡二叉树，是一种自平衡的二叉排序树，本质上仍然是一颗二叉排序树，只是增加了“平衡”的要求，平衡是指，对AVL树中任何节点的两个子树的高度之差（称为平衡因子）的绝对值不超过 11 。能保证上面这一点，AVL树的高度就能始终保持在 O(logn)O(logn) 级别。