算法基础7：平衡查找树概述

算法是基础，小蓝同学准备些总结一系列算法分享给大家，这是第7篇《平衡查找树概述》，非常赞！希望对大家有帮助，大家会喜欢！

前面系列文章：

归并排序

#算法基础#选择和插入排序

由快速排序到分治思想

算法基础：优先队列

二分查找

二叉树查找

在上面一篇分享中我们了解了二叉查找树，他有着最多2 节点，在这个基础上我们去了解下二三数和红黑树。

在二叉查找树上基础上，噩梦改如何去优化来解决其查找成本较高的这个问题呢？（二叉查找树的查找平均速率 1.39LgN 二分查找平均速率在 LgN）。于是就想到能否减少二叉查找树的层级，扩大其根节点来达到更高效的查找和插入呢?

所有我们就多出来一种数据结构称之为2-3查找树。具体形态如下图。它因为他下面

可以放2-3个节点，所以他大大减少了树的高度更便于查找和插入了。其数据结构是整个样子的他的左节点小于其根节点，其中间的子节点（要是存在的话）在根节点的二个值之间，其右节点大于根节点。

在2-3上的基础上我们发现了其他性能更好更合适的数据结构，我们队2-3树做了变种下面我们进行举例

B树：

1、根结点至少有两个子女；
2、每个非根节点所包含的关键字个数 j 满足：m/2 - 1 <= j <= m - 1；
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：m/2<= k <= m ；
4、所有的叶子结点都位于同一层。

B-树

1、关键字集合分布在整棵树中；
2、任何一个关键字出现且只出现在一个结点中；
3、搜索有可能在非叶子结点结束；
4、其搜索性能等价于在关键字全集内做一次二分查找；
5、自动层次控制；

B+树：

是一种树数据结构，是一个n叉树，每个节点通常有多个孩子，一颗B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。
B+ 树通常用于数据库和操作系统的文件系统中。
NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。
B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。
B+ 树元素自底向上插入

更多相关文章

随机推荐