Content #
由苏联数学家Adelson-Velskii和Landis提出，所以又被称为AVL树。
平衡二叉树或为空树，或为具有以下性质的平衡二叉树：① 左右子树高度差的绝对值不超过1；② 左右子树也是平衡二叉树。节点左右子树的高度之差被称为平衡因子。在二叉查找树中，每个节点的平衡因子的绝对值不超过1即平衡二叉树。例如，一棵平衡二叉树及其平衡因子如下图所示:
在平衡二叉树中进行插入操作时只需从插入节点之父向上检查，发现不平衡便立即调整，调整一次平衡即可；而进行删除操作时需要一直从删除节点之父向上检查，发现不平衡便立即调整，然后继续向上检查，直到树根。