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 树之间的区别 的相关文章

  • 查找其索引的乘积可被另一个数字 X 整除的对的数​​量

    给定一个数组和某个值 X 找到满足以下条件的对的数量 i lt j a i a j and i j X 0 Array size lt 10 5 我想这个问题有一段时间了 但只能想出蛮力解决方案 通过检查所有对 这显然会超时 O N 2 t
  • stl 集的 C# 等效项是什么?

    我想使用 C 将一些值存储在平衡二叉搜索树中 我查看了泛型命名空间中的集合 但没有找到与 stl 集合等效的集合 我可以使用什么通用集合 我不想存储键 值对 只是值 你可以使用HashSet http msdn microsoft com
  • O(n^2) 与 O (n(logn)^2)

    时间复杂度是O n 2 or O n logn 2 better 我知道当我们简化它时 它就变成了 O n vs O logn 2 and logn lt n 但是关于logn 2 n is only less than log n 2 f
  • 如何证明2条sql语句是等价的

    我开始用连接和子语句重写一个复杂的 SQL 语句 并获得一个看起来更简单的语句 我通过在相同的数据集上运行并获得相同的结果集来测试它 一般来说 我如何 概念上 证明这两个陈述在任何给定数据集中都是相同的 我建议学习关系代数 正如 Mchl
  • 在Python中寻找坐标系中某些点之间的最短路径

    我编写了一个代码 可以在坐标系中的特定宽度和长度范围内生成所需数量的点 它计算并列出我使用欧几里德方法生成的这些点的距离矩阵 我的代码在这里 import pandas as pd from scipy spatial import dis
  • 在大文件中查找重复项

    我有一个非常大的文件 大约有 1500 万个条目 文件中的每一行都包含一个字符串 称为键 我需要使用 java 查找文件中的重复条目 我尝试使用哈希图并检测重复的条目 显然 这种方法向我抛出了 java lang OutOfMemoryEr
  • Python - 在大型数据集上计算多项概率密度函数?

    我原本打算使用 MATLAB 来解决这个问题 但内置函数有局限性 不适合我的目标 NumPy 中也存在同样的限制 我有两个制表符分隔的文件 第一个是显示内部蛋白质结构数据库的氨基酸残基 频率和计数的文件 即 A 0 25 1 S 0 25
  • python数据结构(类似设置)在添加重复项时抛出异常

    我正在寻找一种在添加重复元素时会引发异常的数据结构 我发现的最接近的是collections Counter gt gt gt from collections import Counter as counter gt gt gt c co
  • 如何在 SQL 中进行广度优先搜索?

    给定一棵存储为关系的树 Parent Child 1 2 1 3 3 4 3 5 2 6 7 8 7 9 如何获取给定节点的所有后代 例如 对于 1
  • 将 Lambda 表达式树与 IEnumerable 结合使用

    我一直在尝试了解有关使用 Lamba 表达式树的更多信息 因此我创建了一个简单的示例 这是代码 如果作为 C 程序粘贴到 LINQPad 中 它可以工作 void Main IEnumerable
  • C++:二叉树所有节点值的总和

    我正在准备面试 我被一个二叉树问题困住了 我们如何计算二叉树所有节点中存在的值的总和 优雅的递归解决方案 伪代码 def sum node if node NULL return 0 return node gt value sum nod
  • 如何在 Twig 中渲染树

    我想渲染一棵深度不确定的树 孩子的孩子的孩子等 我需要递归地循环遍历数组 我怎样才能在 Twig 中做到这一点 我玩过domi27的想法 https stackoverflow com questions 8326482 how to re
  • 为什么路径压缩不会改变 UnionFind 中的排名?

    我正在研究 UnionFind 的实现 并从这里进行排序和路径压缩http en wikipedia org wiki Disjoint set data struct Disjoint set forests http en wikipe
  • 给定一个数字 0-9 的数组和一个整数 n,找到可由输入数组组成且小于 n 的所有整数

    问题是这样的 给你一个数字 0 9 的数组和一个整数n 该数组可能包含任何给定数字的重复项 找到所有可以通过连接输入数组中的数字形成的整数并且小于n 输入数组中的数字可以在输出的元素中重复 例如 输入为 2 5 8 且 n 223 则输出应
  • 如何向 Ext.tree.TreePanel 添加复选框?

    我创建了这个简单的树 var children text My Layers children new Ext tree TreeNode text test1 leaf true new Ext tree TreeNode text te
  • 关于树和前缀(波兰语)表示法?

    我的 MIPS Assembly 类要求我将未知大小的表达式读入解析树 我从来没有处理过树 所以这就是我存储值的方式 假设用户输入了表达式 1 3 4 每个操作数只能是数字 1 9 我最左边的子节点将是起点并包含 2 条数据 1 The o
  • 使用 R 中“rpart”包中的生存树来预测新的观察结果

    我正在尝试使用 R 中的 rpart 包来构建生存树 并且我希望使用这棵树来对其他观察结果进行预测 我知道有很多涉及 rpart 和预测的问题 但是 我还没有找到任何解决 我认为 特定于将 rpart 与 Surv 对象一起使用的问题的方法
  • 我可以使用什么数据结构来查找给定姓名的人的电话号码?

    我可以使用什么数据结构来查找给定姓名的人的电话号码 假设您只会使用人名进行查询 那么最好的选择是使用关联数据结构 这基本上是一种数据结构 通常实现为哈希表或平衡二叉搜索树 将数据存储为键 gt 值 或者 换句话说 作为 键 值 对 您使用键
  • 在现实生活中,您会使用 heapq Python 模块做什么?

    读完吉多的书后使用 Python 对 2MB RAM 中的一百万个 32 位整数进行排序 http neopythonic blogspot com 2008 10 sorting million 32 bit integers in 2m
  • 德尔福数据结构

    我可能需要在 Delphi 中做一个项目 并且是该领域的初学者 目前 我正在网上搜索资源 但由于资源站点太少而感到困惑 首先 你能给我一些好的网站 其中包含我迄今为止错过的 Delphi 资源吗 我也在 Delphi 中搜索数据结构 想知道

随机推荐

  • 添加动态 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