408平衡二叉树是二叉排序树(二叉树二叉排序树和平衡二叉树的关系

平衡二叉树

平衡二叉树(Height-Balanced Binary Search Tree)：他也是一种二叉排序树。平衡二叉树是一颗空树或者其中每个结点的左子树和右子树的高度差最多等于1的二叉排序树.这个解决平衡二叉树的算法是由两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis在1962年共同发明的，所以平衡二叉树也简称为AVL树。

平衡因子： 将二叉树上结点的左子树深度减去右子树高度的值称为平衡因子BF(Balanced Factor).那么平衡二叉树上所有结点的平衡因子只能是-1，0，1.

平衡二叉树实现原理：在构建二叉排序树的过程中，每当插入一个节点值，先检查是否因插入而破环了树的平衡性，如果破坏了就找出最小不平衡子树。在保持二叉排序树的前提下，调整最小不平衡子树种各个结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

原平衡二叉树的平衡被打破后的四种旋转方法：

假设最小不平衡子树的根节点为被破坏结点，新插入的结点叫做破坏节点

1.RR旋转（右单旋）：破坏结点在被破坏节点的右子树的右边，因而叫做RR插入。

2.LL旋转（左单旋）：破坏节点在被破坏节点的左子树的左边，因而叫做LL插入。

3.LR旋转：破坏结点在被破坏节点的左子树的右边，因而叫做LR插入。

4.RL旋转：破坏节点在被破坏节点的右子树的左边，因而叫做RL插入。

上述四种旋转方式是根据结点的插入位置来命名的，有点绕口。我们不妨这样理解：

当进行RR插入时，就进行左旋操作。也就是对被破坏节点进行逆时针旋转，然后根据二叉排序树的特性对一些结点进行调整。

当进行LL插入时，就进行右旋操作。也就是对被破坏节点进行顺时针旋转，然后根据二叉排序树的特性对一些结点进行调整。

当进行RL插入时，就进行双旋操作。也就是先对最小不平衡子树中以被破坏结点为根节点的子树中做一次右旋转操作，以便让bf值和被破坏结点的bf值符号相同。然后对整颗最小不平衡子树做一次左旋转操作。

当进行LR插入时，就进行双旋操作。也就是先对最小不平衡子树中以被破坏结点为根节点的子树中做一次左旋转操作，以便让bf值和被破坏结点的bf值符号相同。然后对整颗最小不平衡子树做一次右旋转操作。

假设n个结点，则一颗平衡二叉树的深度为log以2为底n的对数。因而深度的数量级为logn。所以平衡二叉树的查找，删除，插入时间复杂度都为O(logn)。

【讨论】请问：平衡二叉树和二叉排序树的关系~

二叉排序树（Binary Sort Tree），首先它是一棵树，“二叉”这个描述已经很明显了，就是树上的一根树枝开两个叉，于是递归下来就是二叉树了（下图所示），而这棵树上的节点是已经排好序的，具体的排序规则如下：

若左子树不空，则左子树上所有节点的值均小于它的根节点的值

若右子树不空，则右字数上所有节点的值均大于它的根节点的值

它的左、右子树也分别为二叉排序数（递归定义）

从图中可以看出，二叉排序树组织数据时，用于查找是比较方便的，因为每次经过一次节点时，最多可以减少一半的可能，不过极端情况会出现所有节点都位于同一侧，直观上看就是一条直线，那么这种查询的效率就比较低了，因此需要对二叉树左右子树的高度进行平衡化处理，于是就有了平衡二叉树（Balenced Binary Tree）

所谓“平衡”，说的是这棵树的各个分支的高度是均匀的，它的左子树和右子树的高度之差绝对值小于1，这样就不会出现一条支路特别长的情况。于是，在这样的平衡树中进行查找时，总共比较节点的次数不超过树的高度，这就确保了查询的效率（时间复杂度为O(logn)）

平衡二叉树是二叉排序树吗?

平衡二叉树不是二叉排序树。

平衡树（Balance Tree，BT)指的是，任意节点的子树的高度差都小于等于1。常见的符合平衡树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。

平衡树可以完成集合的一系列操作，?时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。

应用

在智能电网中，与传统路由协议不同，突发性拥塞不再是数据采集的主要风险，风险的新来源是数据流过度集中在网络的关键节点而导致的拥塞。

为此，提出了一种能够实现数据平衡的数据采集路由机制用以克服网络拥塞。该机制抽象出配用通信网络的数学模型。

平衡二叉树是二叉排序树吗

平衡二叉树的前提就一定是二叉排序树，并且每个结点的平衡因子的绝对值小于2，怎么不是呢？更何况一般二叉排序树的关键字不会重复的

平衡二叉树是二叉排序树吗？

平衡二叉树不是二叉排序树。

二叉排序树或者是一颗空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值。

（2）若右子树不空，则右子树所有结点的值均大于或等于它的根结点的值。

（3）左、右子树也分别为二叉排序树。

在任意一颗非空树中：

1）有且仅有一个特定的称为根（Root）的结点；

2）当n1时，其余结点可分为m(m0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。

此外，树的定义还需要强调以下两点：

1）n0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。

2）m0时，子树的个数没有限制，但它们一定是互不相交的。

什么是《平衡二叉树》

平衡二叉树，又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。

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

平衡二叉树的调整方法

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

⑴

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

⑵

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

⑶

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

⑷

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

⑸

计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。