首页 > 其他分享 >【数据结构】B树和B+树

【数据结构】B树和B+树

时间:2023-07-28 20:57:39浏览次数:32  
标签:结点 子树 个数 关键字 数据结构 节点

这部分内容较少,B树要理解基本特性,掌握其建立、插入和删除操作;B+树只需要掌握基本概念即可

1.B树及其基本操作

b树是在平衡二叉树的基础上的衍生概念
(1)B树的定义:m阶B树即为所有结点的平衡因子均等于0m路平衡查找树
复习:m叉树指的是结点的最大子树数目,而不是说m叉树的每个非叶结点都必须是m叉的
image
image
解释:
1.这里先记住B树每个结点最多有m棵子树即可,关于每个结点的关键字个数问题在下面会解释
2.这里说的比较含混(这书写的什么b玩意),根节点不是叶结点指的是根节点中有关键字,即这条定义可以描述为下面这样:
如果根节点没有关键字,则这个根节点下面不会有子树,整个B树为空;如果根节点中有关键字,则其子树个数必然≥2。(这里是因为子树个数等于结点关键字个数+1)
3.

标签:结点,子树,个数,关键字,数据结构,节点
From: https://www.cnblogs.com/satsuki26681534/p/17588871.html

相关文章

  • 5 线性数据结构 参考代码
    P3156[深基15.例1]询问学号#include<cstdio>constintMAXN=2000005;inta[MAXN];intmain(){intn,m;scanf("%d%d",&n,&m);for(inti=0;i<n;++i)scanf("%d",&a[i]);while(m--){int......
  • 数据结构之带头节点的单链表增删改查操作实现
     单链表的定义什么是单链表   单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。   单链表的各个数据元素在物理上可以是离散存放的,每个结点除了存放数据元素外,还要存储指向下一个节点的指针。而顺序表是连续存放的,每个结点中只......
  • 数据结构中队列的存储和应用
    队列:只有两个口进出数据,一个专门进入数据,另一个专门出数据,先进先出,FIFO表 一、顺序队列:存储元素的连续内存的首地址容量队头位置(出队)队尾位置(入队)[元素数量]运算:创建、销毁、清空、出队、入队、队空、队满、队头、队尾、元素数量#inclu......
  • 算法学习(一)—— 如何看待数据结构与算法
    绪言最近在通过阅读K神的《Hello算法》学习数据结构与算法的知识,同时做一些博客笔记记录,方便日后的查找和复习算法数据结构与算法统称算法认识算法算法更多的是一种逻辑,例如:查阅字典的原理与二分查找算法相一致。二分查找体现了分而治之的重要算法思想。整理扑克的过......
  • [数据结构笔记] 线性表
    栈栈是一种后进先出(\(\text{LastInFirstOut,LIFO}\))的线性表,顾名思义,后入栈的元素反而先出栈,其限制是只能在一端插入与删除,就像下面这样,只有一端有开口,另一端则是封死的。\[栈顶\large\begin{array}{c|c|c|c|c|c|c|c|{3}{r@{.}l|}}\hline\\text{}0&1&2&3&4&5&6......
  • Redis数据结构总结
    Redis数据结构  SDS SimpleDynamicString 双向链表 list 字典 dict 整数集合 intset 跳跃表 zskiplist 压缩列表 ziplist ......
  • 数据结构练习笔记——求解由单链表表示的一元多项式的值
    求解由单链表表示的一元多项式的值【问题描述】一个形如\[a_0x^0+a_1x^1+...+a_nx^n\]的一元多项式含有n+1项,每一项由系数和指数唯一确定,可表示成由系数项和指数项构成的一个二元组(系数,指数),一元多项式则可以表示成二元组的集合{(a0,0),(a1,1),(a2,2)...(an,n)},可看成是数据......
  • 数据结构练习笔记——循环队列的基本操作
    循环队列的基本操作【问题描述】根据循环队列的类型定义,完成循环队列的基本操作。主函数中测试队列。【输入形式】一个整数m,表示入队的元素个数【输出形式】第一行:输出队头元素第二行:队列中元素依次出队以空格间隔【样例输入】5【样例输出】113579【样例输入】0【样......
  • 初识C数据结构之“*”和“&”(指针、解引用、取地址、引用)
    这天小阿杰又在看C数据结构——顺序表中几个传参的小小的内容引起了小阿杰大大的疑惑:(教材为严蔚敏老师的《数据结构(C语言版第2版)》)可怜的小阿杰当时只知道&取地址……后来查阅资料才对其中略知一二,那咱们下面就来唠唠。顺便提一下,引用&只在C++中有,C语言......
  • 7.25 day2数据结构优化dp
    战绩:100+100+20+54=374T1据lxl说是为了成绩好看加的题,难度大概cspjT1T2朴素dp然后树状数组优化一下T3赛时脑抽链,写了个dp,一直想优化dp,其实贪心就好了,过程更加简洁,优化很显然先将区间剖分成两段端点\(s_i=s_j\)相同的多条线段将区间每个点吸附到离他右边最近的一个线段......