B 树和 2-3-4 树之间的区别

2024-04-04

B 树和 2-3-4 树有什么区别?

另外,你如何找到每个的最大和最小高度?


...链接到维基百科 http://en.wikipedia.org/wiki/2-3-4_tree and引用:

“2-3-4 树是 4 阶 B 树。”

A 2-3-4 is a B-tree.
它被称为 2-3-4 树,因为非叶、非根节点的子节点数量为 2,3 或 4。
如果是6,就可以称为3-4-5-6树,简称3-6树。
由于子节点的最小数量是最大子节点数量的一半,因此通常可以跳过前者并讨论有序 B 树m.
B 树的阶数定义为节点可以拥有的子节点的最大数量。
正如我们所见,在 2-3-4 树中,最大值为 4。

最坏和最好情况的高度由下式给出B树的一般公式 http://en.wikipedia.org/wiki/B_tree#Best_case_and_worst_case_heights.

Best case: logmn. (all nodes are full)
Worst case: logm/2n. (all nodes are half-empty)

where

  • m是树的顺序 - 一个节点可以拥有的子节点的最大数量,在本例中为 4 - 并且
  • n是树中的条目数

“B树可以有任意数字的顺序”- 是的,但是对于 B 树的特定子类,您可以提前修复该数字。这就像谈论一般的蝴蝶与谈论蝴蝶帝王蝶 http://en.wikipedia.org/wiki/Monarch_butterfly。 B 树是一类数据结构,就像蝴蝶是一类昆虫一样。帝王蝶 http://en.wikipedia.org/wiki/Monarch_butterfly是蝴蝶的子类,就像 2-3-4 树是 B 树的子类一样。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

B 树和 2-3-4 树之间的区别 的相关文章

  • 应用对数来导航树

    我曾经知道一种使用对数从树的一片叶子移动到树的下一个 有序 叶子的方法 我认为它涉及获取 当前 叶子的位置值 排名 并将其用作从根向下到新目标叶子的新遍历的种子 一直使用对数函数测试来确定是否沿着右或左节点向下到达叶子 我已经不记得如何运用
  • 如何考虑子类型的多态性

    里氏替换原则指出 超类型的不变量必须保留在子类型中 我对这个原理和多态性的交叉特别感兴趣 事实上 特别是子类型多态性 参数多态性和 Haskell 类型类似乎就是这种情况 因此 我知道当函数的参数是逆变且返回类型是协变时 函数是子类型 我们
  • Scheme (Lisp) 中树的深度反转

    我对Scheme中的基本树数据结构进行了深度逆向 define deep reverse t cond null t not pair t t else cons deep reverse cdr t deep reverse car t
  • 为什么我们需要检测链表中的循环

    我看到很多关于如何检测链表中的循环的问答 但我想了解的是我们为什么要这样做 换句话说 检测链表中的循环的实际用例是什么 在现实生活中 您可能永远不需要检测链表中的循环 但是执行此操作的算法很重要 我在现实生活中多次使用它们 例如 我经常会递
  • Python - 在大型数据集上计算多项概率密度函数?

    我原本打算使用 MATLAB 来解决这个问题 但内置函数有局限性 不适合我的目标 NumPy 中也存在同样的限制 我有两个制表符分隔的文件 第一个是显示内部蛋白质结构数据库的氨基酸残基 频率和计数的文件 即 A 0 25 1 S 0 25
  • 根据子节点数量动态调整 d3 树布局的大小

    从这个例子来看http mbostock github com d3 talk 20111018 tree html http mbostock github com d3 talk 20111018 tree html我已经建立了一个d3
  • 如何从此 d3.js layout.tree 获取树祖先和树后代的列表?

    我正在尝试和修改this https bl ocks org mbostock 4339083d3 js 的示例 用于根据 JSON 树结构绘制树 这就是树的一部分开始时的样子 我正在尝试进行两个单独的修改 但我不知道该怎么做 当单击节点的
  • 如何在 SQL 中进行广度优先搜索?

    给定一棵存储为关系的树 Parent Child 1 2 1 3 3 4 3 5 2 6 7 8 7 9 如何获取给定节点的所有后代 例如 对于 1
  • 将结构体数组传递给函数 C++

    抱歉这个菜鸟问题我只是有点困惑 如果我在 main 中有一个结构数组 我想将其传递给函数 struct MyStruct int a int b char c mayarray 5 MyStruct StructArray 10 myFun
  • 是否可以在 Java 中创建对象树?

    我正在尝试用 Java 创建对象树 我还想使用一个 Java 类 可以轻松地在树中添加或删除节点 用于此目的的最佳类是什么 示例 这是一个对象数组 数组顶部的对象是字符串 world 这里的叶子是整数 我想添加字符串 This is at
  • 为什么路径压缩不会改变 UnionFind 中的排名?

    我正在研究 UnionFind 的实现 并从这里进行排序和路径压缩http en wikipedia org wiki Disjoint set data struct Disjoint set forests http en wikipe
  • 为什么斐波那契堆被称为斐波那契堆?

    The 斐波那契堆 http en wikipedia org wiki Fibonacci heap数据结构的名称中有 斐波那契 一词 但数据结构中似乎没有任何内容使用斐波那契数 根据维基百科文章 斐波那契堆的名称来自于运行时间分析中使用
  • 在现实生活中,您会使用 heapq Python 模块做什么?

    读完吉多的书后使用 Python 对 2MB RAM 中的一百万个 32 位整数进行排序 http neopythonic blogspot com 2008 10 sorting million 32 bit integers in 2m
  • NumPy“记录数组”或“结构化数组”或“recarray”

    NumPy 结构化数组 记录数组 和 记录数组 之间有什么区别 如果有的话 The NumPy 文档 http docs scipy org doc numpy user basics rec html暗示前两个是相同的 如果是 那么该对象
  • 数据结构...那么我如何理解它们呢? [关闭]

    就目前情况而言 这个问题不太适合我们的问答形式 我们希望答案得到事实 参考资料或专业知识的支持 但这个问题可能会引发辩论 争论 民意调查或扩展讨论 如果您觉得这个问题可以改进并可能重新开放 访问帮助中心 help reopen questi
  • 我的 Bitset 的大小是多少?

    我想存储System currentTimeInMillis以尽可能小的空间存储在内存中 因为我必须将数百万个它们存储在内存中 我把它转换为binaryString这给了我41 bits 这是我的程序 public class BitSet
  • 为什么在 MySQL 中计算带条件的行时需要“OR NULL”

    有一个关于 MySQL 的 COUNT 聚合函数的问题时不时地出现在我的脑海中 我想得到一些解释为什么它会这样工作 当我开始使用 MySQL 时 我很快了解到它的 COUNT condition 似乎只有在条件最后还包含 OR NULL 时
  • Java:数组和向量

    我习惯于使用 PHP 但最近我一直在使用 Java 并且试图解决这个问题让我很头疼 我想用 Java 保存这个表示 Array col name 1 gt Array 1 gt col value 1 2 gt col value 2 n
  • 如何更新 Sencha Touch 中的嵌套列表/树存储?

    我有一个嵌套列表 必须根据用户在 Ext Carousel 中选择的内容填充新数据 TreeStore load newData this does not work TreeStore removeAll this works 似乎文档和
  • 字符串 c 的二叉树

    我正在尝试实现一个能够在 c 中保存字符串的二叉树 在让代码适用于整数之后 我尝试稍微修改它以处理字符数组 现在我似乎完全破解了代码 但不知道如何破解 任何帮助表示赞赏 include

随机推荐

  • 添加动态 formControl 时,所有必需输入字段的文本颜色更改为无效颜色

    每当我通过按钮单击添加动态 formControl 时 所需的所有输入字段都会将颜色更改为无效 红色 我的期望是 只有当输入被 触摸 时 表单字段才会更改为无效颜色 并且仅在特定的非全部 我不知道为什么会发生这种情况 我刚刚接触有角度和有角
  • 在 Silverlight 中检测控件的焦点

    有什么方法可以判断某个控件 特别是 System Windows Controls TextBox 是否在 Silverlight 中获得焦点 我正在寻找类似以下内容的内容 您会在常规 Net 应用程序中看到的内容 textBox Focu
  • Swift 3 中的 NSFastEnumeration

    我正在尝试迭代一个对象CMSensorDataList返回的类CMSensorRecorder accelerometerData from to 该类确认NSFastEnumeration协议 所以我尝试了中提到的技巧https stac
  • JUnit 运行测试命令行

    我有以下结构 lib junit 4 10 jar tests Tester java tests Tester class build jar jar file jar 测试器属于包测试 我可以使用编译测试 javac cp build
  • App Engine SDK DevServer 只读模式?

    有没有办法以只读模式运行应用程序引擎开发服务器 以模拟 Google 的定期维护 从而将数据存储区置于只读模式 在定期维护期间优雅降级 http code google com appengine docs python howto mai
  • 如何映射输入文件数组?

    我有两个函数 一个将文件转换为 dataUrl 另一个返回结果的承诺 fileToDataURL file var reader new FileReader return new Promise function resolve reje
  • 我可以使用 <%= ... %> 在 ASP.NET 中设置控件属性吗?

  • 行为相同的条件检查的执行[重复]

    这个问题在这里已经有答案了 我回答了这个问题 https stackoverflow com questions 25234401 which is a better practice for if else condition 25234
  • 使用按钮导航到导航窗口中的另一个页面

    我正在尝试使用 WPF 中的导航命令框架在 WPF 应用程序 桌面 不是 XBAP 或 Silverlight 内的页面之间导航 我相信我已经正确配置了所有内容 但它不起作用 我构建并运行时没有错误 在输出窗口中没有收到任何绑定错误 但我的
  • 将 CSS3 动画/变换与滚动事件链接起来

    我正在寻找一种将 CSS3 过渡链接到滚动事件的方法 我正在寻找类似的功能http nizoapp com http nizoapp com 当您到达页面上的某个滚动点时 某些元素会移动 我知道你必须使用 jQuery 调用滚动事件 使用偏
  • 具有多个 S3 源的 AWS CloudFront

    我想配置 AWS CloudFront CDN 以提供来自两个 AWS S3 存储桶的 HTML 静态内容 第一个存储桶应在根目录中托管对象 第二个存储桶应在特定子路径中托管对象 S3配置 第一个桶 myapp home 应将主页和所有其他
  • C# 中的排序列表

    如何根据项目的整数值对列表进行排序 该列表就像 1 5 3 6 11 9 NUM1 NUM0 结果应该是这样的 1 3 5 6 9 11 NUM0 NUM1 有什么想法可以使用 LINQ 或 Lambda 表达式来做到这一点吗 提前致谢 这
  • 导入 _imaging 时 DLL 加载失败:

    我正在尝试运行我的 Python 程序 这些是我要导入的模块 从 tkinter 导入 从 functools 导入部分将 numpy 导入为 np 导入 matplotlib matplotlib use TkAgg 从 matplotl
  • 如何使用 CSS 将自定义位图字体嵌入到网站中

    如何使用 CSS 将自定义位图字体嵌入到我的网站中 我已尝试以下操作 但它只是恢复为后备字体 font face font family AgendaSemibold src url Agenda Semibold bmap format
  • JPA:检查实体对象是否已持久化

    有没有一个通用的方法可以 if entity is persisted before entity entity merge else entity persist 那么包含上述逻辑的方法在任何地方都是安全的吗 如果您需要知道对象是否已经在
  • Google Analytics API 3 - 错误:“invalid_grant”,说明:“”,Uri:“”

    我今天用谷歌搜索了这个问题的生命 分辨率为零 我正在尝试使用服务帐户构建一个非常简单的 Google Analytics 数据请求控制台应用程序 我已在 Google Developers Console 中设置了所有必需的详细信息 但收到
  • TFDMoniFlatFileClientLink 不规则地不跟踪到文件

    我有一个TFDMoniFlatFileClientLink在表单上 文件名设置为d temp monitor txt 追踪 真 TFDConnection Params MonitorBy mbFlatFile 这有时有效 有时则不跟踪任何
  • Python-创建一个以变量为名称的文本文件

    所以我正在做一个项目 我的程序创建一个名为 十个绿色瓶子 的文本文件 并在其中写入 10 个绿色瓶子歌曲 我已经成功地使其工作 但我想让它变得更好 我首先让用户可以选择瓶子的数量 效果很好 现在我只希望名称与用户输入的瓶子数量相关 即 如果
  • 为什么 Linux 可以在多处理中接受套接字?

    该代码在 Linux 上运行良好 但在 Windows 下失败 这是预期的 我知道多处理模块使用fork 产生一个新进程 并且父进程拥有的文件描述符 即打开的套接字 因此由子进程继承 然而 据我了解 您可以通过多处理发送的唯一数据类型需要是
  • B 树和 2-3-4 树之间的区别

    B 树和 2 3 4 树有什么区别 另外 你如何找到每个的最大和最小高度 链接到维基百科 http en wikipedia org wiki 2 3 4 tree and引用 2 3 4 树是 4 阶 B 树 A 2 3 4 is a B