什么是《平衡二叉树》
发布网友
发布时间：2022-03-25 21:21
共5个回答
热心网友
时间：2022-03-25 22:50
常用算法有：红黑树、AVL树、Treap等。
平衡二叉树的调整方法
平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下：
⑴
每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；
⑵
若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；
⑶
判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；
⑷
如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；
⑸
计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。
热心网友
时间：2022-03-26 00:08
(Balanced
binary
tree)
，其严格定义是：
一棵空树是平衡二叉树；若
T
是一棵非空二叉树，其左、右子树为
TL
和
TR
，令
hl
和
hr
分别为左、右子树的深度。当且仅当
①TL
、
TR
都是平衡二叉树；
②
｜
hl
－
hr
｜≤
1；
时，则
T
是平衡二叉树。
热心网友
时间：2022-03-26 01:43
binary
tree）又被称为avl树（有别于avl算法），且具有以下性质：它是一
棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法
平衡二叉树的常用算法有红黑树、avl、treap、伸展树等。
最小二叉平衡树的节点的公式如下
f(n)=f(n-1)+f(n-2)+1
这个类似于一个递归的数列，可以参考fibonacci数列
1是根节点
f(n-1)是左子树的节点数量
f(n-2)是右子数的节点数量。
热心网友
时间：2022-03-26 03:34
但它的概念之所以提出来，就是为了提高搜索效率的
要求二叉树达到平衡，就是要在搜索的时候，不至于沿着某个子树搜索下去
极端不平衡的二叉树，退化成线性表了，搜索就变成“遍历”了
热心网友
时间：2022-03-26 05:42
平衡二叉树（AVL）
那对图 1 进行下改造，把数据重新节点重新连接下，图 2 如下：
图 2 可以看到以下特性：
1. 所有左子树的节点都小于其对应的父节点（4，5，6）<（7）；（4）<（5）；（8）< （9）；
2. 所有右子树上的节点都大于其对应的父节点（8，9，10）>（7）；（6）>（5）；（10）>（9）；
3. 每个节点的平衡因子差值绝对值 <=1；
4. 每个节点都符合以上三个特征。
满足这样条件的树叫平衡二叉树（AVL）树。
问：那再次查找节点 5，需要遍历多少次呢？
由于数据是按照顺序组织的，那查找起来非常快，从上往下找：7-5，只需要在左子树上查找，也就是遍历 2 次就找到了 5。假设要找到叶子节点 10，只需要在右子树上查找，那也最多需要 3 次，7-9-10。也就说 AVL 树在查找方面性能很好，最坏的情况是找到一个节点需要消耗的次数也就是树的层数， 复杂度为 O(logN)
如果节点非常多呢？假设现在有 31 个节点，用 AVL 树表示如图 3：
图 3 是一棵高度为 4 的 AVL 树，有 5 层共 31 个节点，橙色是 ROOT 节点，蓝色是叶子节点。对 AVL 树的查找来看起来已经很完美了，能不能再优化下？比如，能否把这个节点里存放的 KEY 增加？能否减少树的总层数？那减少纵深只能从横向来想办法，这时候可以考虑用多叉树。
