建立平衡二叉树的目的,平衡二叉树的概念

平衡二叉树

平衡二叉树(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)。

数据结构基础--二叉树

先序遍历先从二叉树的根开始，然后到左子树，再到右子树。

遍历的结果是：ABDCEF

中序遍历先从左子树开始，然后到根，再到右子树。

遍历的结果是：DBAECF

后序遍历先从左子树开始，然后到右子树，再到根。

遍历的结果是：DBEFCA

打印自己，然后先遍历左节点再遍历右节点

这里的栈用处是为了保存二叉树的结构，以弥补二叉树无法获取父节点的结构特性。

不过需要注意的是后入栈的为左孩子，以保证优先遍历左侧。

第一个栈的处理顺序为，自上而下，自右而左。经过第二个栈的逆序，就变成了自下而上，自左而右。

每次将新节点加入队列时，将nlast更新成新节点。

当当前打印的节点等于last，执行换行并将last更新到下一行nlast。

举个例子(用 ! 分割，用 # 表空):

将序列化字符串转化成数组(比如这里通过 ! 分割)

所以我们需要引入一个变量 setleft 来确定下一次需要构建的节点方向。

每次构建新节点之后，下一次都会尝试构建其左侧节点。

而每次遇到空节点后，都会将顶元素推出，并尝试构建其的右侧节点。

因为他的队列，只负责记录下一次想要处理的节点。

并不需要在意左右与层级倒退，只需要处理节点为空的情况即可。

如下图中第三棵二叉树。

2节点的子树下方，左侧高度为2，右侧高度为0。所以不是一个平衡二叉树。

一旦一侧子节点为空，另一侧若高度大于2，则判定为否

目的都是提高搜索二叉树的效率，调整代价降低。

第一个错误的节点为第一次降序较大的节点

第二个错误的节点为第二次降序较小的节点

第一个错误的节点为此次降序较大的节点

第二个错误的节点为此次降序较小的节点

除最后一层无任何子 节点 外，每一层上的所有结点都有两个子结点二叉树。

从图形形态上看，满二叉树外观上是一个三角形

这种满二叉树的层数为L，节点数为N。

则N = 2^L-1 ,L = log(N+1)

满二叉树的结点要么是叶子结点，度为0，要么是度为2的结点，不存在度为1的结点。

在满二叉树的基础上，最后一层所有的结点都连续集中在最左边，这就是完全二叉树。

先遍历左子树左边界，再遍历右子树左边界。从而判断哪边为满二叉树。

满二叉树侧，N=2^H。非满二叉树侧，递归。

每层只遍历一个节点的子树，总计LogN。

每个子树获取右子树左边界遍，需要经历LogN次计算。

总复杂度O((LogN^2))

如果从下标从1开始存储，则编号为i的结点的主要关系为：

双亲：下取整 （i/2）

左孩子：2i

右孩子：2i+1

如果从下标从0开始存储，则编号为i的结点的主要关系为：

双亲：下取整 （(i-1)/2）

左孩子：2i+1

右孩子：2i+2

2的后序节点为3，2的前驱节点为1

下图中2，1两节点距离为2。3，5节点距离为5

三个情况下最大的结果，就是以head为头节点的整棵树上最远的距离。

Swift 算法实战之路：二叉树

左神牛课网算法课

平衡二叉树的作用

我们知道，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。

平衡二叉搜索树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log2n），大大降低了操作的时间复杂度。

平衡二叉树是什么意思?

什么是平衡二叉树

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

它要么是一 棵空树，要么是它的左右两个子树的高度差的绝对值不超过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的结点。

平衡二叉树概念

我觉得平衡二叉树，不一定必须是二叉搜索树。

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

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

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

为什么要构建平衡二叉树，的主要目的为?

因为正常的二叉排序树弄得不好查找性能近似于O(n)，使用平衡二叉树则可以保证查找性能不超过1.5log2n