平衡二叉树是什么?能通俗地说一下并举例子吗
发布网友
发布时间：2022-04-14 12:41
共3个回答
懂视网
时间：2022-04-14 17:02
一、2-3-4树介绍 2-3-4树是一种多叉树(multiway tree)，它的每个节点最多有四个子节点和3个数据项，2-3-4 树可以看做是阶为4 的B树。B树是另一种平衡的多叉树，专门用在外部存储中来组织数据(通常是指磁盘驱动器)。B树中的节点可以有几时或几百个。 2-3-4树
一、2-3-4树介绍
2-3-4树是一种多叉树(multiway tree)，它的每个节点最多有四个子节点和3个数据项，2-3-4 树可以看做是阶为4 的B树。B树是另一种平衡的多叉树，专门用在外部存储中来组织数据(通常是指磁盘驱动器)。B树中的节点可以有几时或几百个。
2-3-4树名字中的2、3、4的含义是指一个节点可能含有的子节点数。
有1个数据项的节点总是有2个子节点
有2个数据项的节点总是有3个子节点
有3个数据项的节点总是有4个子节点
简言之，非叶子节点的子节点数总是比它含有的数据项多1
在2-3-4树中不允许一个节点只有一个链接,这与传统的二叉树不同。
二、B树、B+树
二叉树提供了良好的性能，但是当数据有序插入时会失去平衡，2-3-4树和2-3树是一种平衡树,是多路的，而红-黑树（见上一篇文章）是一种二叉平衡树，通过严格的红黑规则保持平衡。B树是一种平衡的多路查找树，可以看做一种扩展的2-3-4树，它的数据项个数和子节点数没有限制(如果结点的元素数量非常多的话那就退化成节点内部的线性查找了)，在文件系统中有所应用，主要用作文件的索引。
B树插入节点要注意从子节点开始分裂,一直上溯到根
B+树是B树的一种变型
B+树中的非叶子节点不是最终指向文件内容的节点，而只是叶子节点中关键字的索引。所有的叶子节点包含了全部关键字的信息，且叶子节点本身依关键字自小而大顺序链接。所以任何关键字的查找都必须走一条从根节点到叶子节点的路(导致每一个数据的查询效率相当)。
总而言之，B 树在提高了磁盘IO 性能的同时并没有解决元素遍历效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历，支持基于范围的查询，而B树不支持range-query 这样的操作（或者说效率太低）。
通过以上介绍，大致将B 树，B+树，B*树总结如下：
● B 树：有序数组+平衡多叉树；
● B+树：有序数组链表+平衡多叉树；
● B*树：一棵丰满的B+树。
B树相关的参考资料http://www.2cto.com/database/201401/272612.html
热心网友
时间：2022-04-14 14:10
它要么是一 棵空树，要么是它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
热心网友
时间：2022-04-14 15:45
平衡二叉树（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 增加？能否减少树的总层数？那减少纵深只能从横向来想办法，这时候可以考虑用多叉树。
