在一个论坛上有人告诉我数组已经是一个平衡的 B 树。它是如何获得的?可能是因为B树中元素的添加有一个固定的复杂度?
最佳答案
我想纯粹从数据结构的角度来看,一个排序数组a
可以被认为是一个只有一个节点的B树。即,顺序大于 a
的 length
的 B 树。在这种情况下,您的根节点将是数组 a
并且由于树中只有一个节点,因此该根节点将是叶节点(这意味着它包含数据而不仅仅是键)。
这样一棵 B 树是平衡的,因为只有一个节点位于深度为零,这满足了平衡 B 树中所有叶节点必须处于同一深度的要求。
这适用于顺序定义,其中 m 顺序的 B 树是每个节点最多有 m 个子节点的 B 树。这意味着节点最多可以包含 m-1 个键(或者叶节点中的元素)。
关于arrays - 一个数组已经是一个平衡的 B 树,这是真的吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20676172/