B-树是一种常见的数据结构。和他一起的还有B+树。
在这里,需要澄清一下概念。B树,B-树,B+树有什么区别?他们有什么关系呢?
其实,从数据结构来讲只有2种,也就是B-树和B+树。有时候,B-树又称为B树,他们是一个东西。请注意,B-树中间的“-”是连字符,而不是“减号”。英文中是B-Tree,翻译成中文后,也就是B树,有的翻译喜欢把连字符“-”也带着,于是就成了B-树,而B-树被有些读者误读为B减树。
介绍B-树之前,首先看一下一个重要的概念:阶。
一个树的阶,就是这个树中各个节点的子节点个数的最大值。也就是说,如果有的节点有2个子节点,有的节点有4个子节点,最多的有5个子节点,那么,这个树的阶就是5.
从这个角度来讲,二叉树的阶是2.
接下来,我们介绍一下B-树的主要性质。我们假定B-树的阶为m。一个m阶的B-树,要么是一个空树,要么是具有如下性质的树:
1,每个节点最多有m个子节点。最少有m/2(向上取整)个节点。或者这么表述:m/2 <= 子节点个数<= m。但是根节点是例外的,根节点可以最少有2个子节点。
2,每个节点的子节点的个数,比该节点中保存的关键字的个数多1. 也就是,当节点中保存k个关键字时,该节点会有k + 1个子节点(子树)。
3,每个节点中的k个关键字是按照从小到到排列的,分别记为k1,k2,k3,......kk。那么该节点会有k+1个指针,记为p0,p1,p2,......pk。并且,p3所指向的子节点中的所有元素,都大于k3,且都小于k4. 如下图所示。这一点也比较容易理解和记忆,各个指针p整好位于关键字k的插空的位置,所以,插空处的指针指向的子节点的元素的值,就理所当然的应该大于指针左边的元素,小于指针右边的元素。
4,B-树是严格的平衡查找树,它的左右子树的高度是相等的。且叶子节点处于同一层,并且可以用空节点表示。
一个B-树的例子:
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对的支持。如果你想了解更多相关内容请查看下面相关链接
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
RTX 5090要首发 性能要翻倍!三星展示GDDR7显存
三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。
首次推出的GDDR7内存模块密度为16GB,每个模块容量为2GB。其速度预设为32 Gbps(PAM3),但也可以降至28 Gbps,以提高产量和初始阶段的整体性能和成本效益。
据三星表示,GDDR7内存的能效将提高20%,同时工作电压仅为1.1V,低于标准的1.2V。通过采用更新的封装材料和优化的电路设计,使得在高速运行时的发热量降低,GDDR7的热阻比GDDR6降低了70%。
更新日志
- 群星《前途海量 电影原声专辑》[FLAC/分轨][227.78MB]
- 张信哲.1992-知道新曲与精丫巨石】【WAV+CUE】
- 王翠玲.1995-ANGEL【新艺宝】【WAV+CUE】
- 景冈山.1996-我的眼里只有你【大地唱片】【WAV+CUE】
- 群星《八戒 电影原声带》[320K/MP3][188.97MB]
- 群星《我的阿勒泰 影视原声带》[320K/MP3][139.47MB]
- 纪钧瀚《胎教古典音乐 钢琴与大提琴的沉浸时光》[320K/MP3][148.91MB]
- 刘雅丽.2001-丽花皇后·EMI精选王【EMI百代】【FLAC分轨】
- 齐秦.1994-黄金十年1981-1990CHINA.TOUR.LIVE精丫上华】【WAV+CUE】
- 群星.2008-本色·百代音乐人创作专辑【EMI百代】【WAV+CUE】
- 群星.2001-同步过冬AVCD【环球】【WAV+CUE】
- 群星.2020-同步过冬2020冀待晴空【环球】【WAV+CUE】
- 沈雁.1986-四季(2012梦田复刻版)【白云唱片】【WAV+CUE】
- 纪钧瀚《胎教古典音乐 钢琴与大提琴的沉浸时光》[FLAC/分轨][257.88MB]
- 《国语老歌 怀旧篇 3CD》[WAV/分轨][1.6GB]