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