数据结构中，哪种平衡二叉搜索树被称为AVL树？

本文共计5451个文字，预计阅读时间需要22分钟。

一、平衡二叉树+平衡二叉树+亦称平衡二叉搜索树（Self-balancing binary search tree）是一种结构平衡的二叉搜索树。

平衡二叉树由二分搜索树发展而来，在二分搜索树的基础上进行平衡。

一、平衡二叉树

平衡二叉树 也称平衡二叉搜索树（Self-balancing binary search tree）是一种结构平衡的二分搜索树。

 

平衡二叉树由二分搜索树发展而来，在二分搜索树的基础上平衡二叉树需要满足两个条件：

• 1、它的左右两个子树的高度差的绝对值不超过1。
• 2、左右两个子树都是一棵平衡二叉树

平衡因子

某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子（BF,Balance Factor）。平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。如果某一结点的平衡因子绝对值大于1则说明此树不是平衡二叉树。为了方便计算每一结点的平衡因子我们可以为每个节点赋予height这一属性，表示此节点的高度。

 

常见的平衡二叉搜索树有：

• AVL树
• 红黑树
• Treap

二、AVL树

AVL树 是由 G. M. Adelson- V elsky 和 E. M. Landis于1962年提出。AVL树是最早的平衡二叉树。