AVL平衡二叉搜索树

分类: 文章 • 2025-02-24 18:32:10

定义：平衡二叉树或为空树,或为如下性质的二叉排序树:
（1）左右子树深度之差的绝对值不超过1;
（2）左右子树仍然为平衡二叉树.
平衡因子BF=左子树深度－右子树深度.
平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。
如图所示为平衡树和非平衡树示意图：

AVL平衡二叉搜索树