算法基础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+ 树元素自底向上插入

 

 

猜你喜欢

#大数据和云计算机技术社区#博客精选（2017）

猜一猜全球未来5朵云会是谁？

NoSQL 还是 SQL ？这一篇讲清楚

阿里的OceanBase解密

#大数据和云计算技术#: "四有"社区介绍

大数据和云计算技术周报（第27期）

新数仓系列：Hbase周边生态梳理（1）

《大数据架构详解》第2次修订说明

云观察系列：漫谈运营商公有云发展史

云观察系列：百度云的一波三折

云观察系列：阿里云战略观察

超融合方案分析系列（7）思科超融合方案分析

加入技术讨论群

《大数据和云计算技术》社区群人数已经2500+，欢迎大家加下面助手微信，拉大家进群，自由交流。

喜欢钉钉扫码下面的群：

喜欢QQ群的，可以扫描下面二维码：

欢迎大家通过二维码打赏支持技术社区（英雄请留名，社区感谢您，打赏次数超过85+）：