Question

平衡二叉树是什么意思?

Answer 1

什么是平衡二叉树
简单说就是平衡二叉排序树，也就是首先是二叉排序树，然后还是平衡的。可以这样理解

它要么是一 棵空树，要么是它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
平衡二叉树比其他二叉树有什么好处
首先平衡二叉树是特殊的二叉排序树，他的结点元素间存在着偏序关系。

其次相对于一般的二叉排序树，平衡二叉树的左右子树的深度差也有不超过1层的约束。

这样使得平衡树是同种元素序列情况下的深度最小的二叉排序树。这可以减少二叉树元素查找的深度，从而提升平均查找效率。
平衡二叉树定义
所谓平衡二叉树是指树中任一结点的左、右子树高度大致相同。平衡二叉树有很多种绩著名的是由前苏联数学家Adelse—Velskil和Landis在1962年提出的，称为AVL树。平衡二叉树(AVL树)定义如下：平衡二叉树或者是一棵空树，或者是具有以下性质的二叉排序树：(1)它的左子树和右子树的高度之差绝对值不超过1；(2)它的左子树和右子树都是平衡二叉树。
数据结构平衡二叉树图9.12中的(e)和(g)啥意思
这个e和g就是在平衡二叉树产生不平衡时，做了平衡化的旋转得到
红黑树和平衡二叉树 区别
红黑树和之前所讲的AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。自从红黑树出来后，AVL树就被放到了博物馆里，据说是红黑树有更好的效率，更高的统计性能。

红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。AVL树的复杂比起红黑树来说简直是小巫见大巫。红黑树是真正的变态级数据结构。
平衡二叉树的平衡因子是什么
基本上就是左子树高了1层就加1，右子树高就-1，然后左右一样高就为0
为什么要构建平衡二叉树，的主要目的为? 5分
因为正常的二叉排序树弄得不好查找性能近似于O(n)，使用平衡二叉树则可以保证查找性能不超过1.5log2n
什么是平衡二叉树
平衡二叉树，又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。

常用算法有：红黑树、AVL树、Treap等。

平衡二叉树的调整方法

平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下：

⑴ 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；

⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；

⑶ 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；

⑷ 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；

⑸ 计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。
平衡二叉树概念
我觉得平衡二叉树，不一定必须是二叉搜索树。

但它的概念之所以提出来，就是为了提高搜索效率的

要求二叉树达到平衡，就是要在搜索的时候，不至于沿着某个子树搜索下去

极端不平衡的二叉树，退化成线性表了，搜索就变成“遍历”了