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

原文发布于微信公众号 - 大数据和云计算技术(jiezhu2007)

原文发表时间:2018-03-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏青蛙要fly的专栏

Android技能树 — 树基础知识小结(一)

现在安卓面试,对于数据结构的问题也越来越多了,也经常看到别人发的面试题都是问什么红黑树,二叉树查找等,所以我们虽然不会马上就会各种难的面试题,但起码树的基础知识...

10630
来自专栏灯塔大数据

每周学点大数据 | No.26外存数据结构——B 树

No.26期 外存数据结构——B 树 小可:看来在磁盘上二叉搜索树对新来的数据插入树中支持得不好,那么究竟怎么解决这个问题呢? Mr. 王:有一个非常经典的...

37070
来自专栏java学习

每日一练(2017/5/17)

Java基础 | 数据库 | Android | 学习视频 | 学习资料下载 课前导读 ●回复"每日一练"获取以前的题目! ●答案公布时间:为每期发布题目的第二...

29960
来自专栏java一日一条

Calendar 详解

究竟什么是一个 Calendar 呢?中文的翻译就是日历,那我们立刻可以想到我们生活中有阳(公)历、阴(农)历之分。它们的区别在哪呢?

9610
来自专栏木子昭的博客

明星程序员被Google挂掉的故事

首先要提一个软件Homebrew Homebrew可能是Mac上最好用的包管理器, 地位相当于Ubuntu的apt, 也相当于命令行版的AppStore ? ...

39450
来自专栏Petrichor的专栏

leetcode: 78. Subsets

12110
来自专栏cmazxiaoma的架构师之路

Java数据结构与算法(3) 寻找中序遍历时的下一个结点

12730
来自专栏一枝花算不算浪漫

Java中常见数据结构List之LinkedList

33750
来自专栏Golang语言社区

完全二叉树判断,简单而复杂

今天有个人问我如何判断一棵树是完全二叉树。我一下子想不出怎么解决这个问题,按照定义, 严蔚敏那本教材上的说法:一个深度为k,节点个数为 2^k - 1 的二叉树...

38830
来自专栏coolblog.xyz技术专栏

TreeMap 源码分析

TreeMap最早出现在JDK 1.2中,是 Java 集合框架中比较重要一个的实现。TreeMap 底层基于红黑树实现,可保证在log(n)时间复杂度内完成 ...

64790

扫码关注云+社区

领取腾讯云代金券