在哪里可以找到从B树中删除密钥的伪代码算法？
我正在阅读Cormen的《算法导论》（第三版）中关于B-树的章节，发现删除过程非常混乱。我可以理解插入算法，因为它提供了伪代码和一些示例，如：
但对于删除，它只是说。。。“我们勾勒出删除是如何工作的，而不是呈现伪代码”，然后是非常混乱的步骤。第一步是：
- 如果密钥k在节点x中，并且x是叶子，则从x中删除密钥k。
但是如果我从叶子中删除一个键，如果键的数量少于所需的最小值，它不会违反B-树属性吗？
共有2个答案
终于能解决这件事了。我将使用书中描述的这些案例，但是稍微修改一下语句，这样它们看起来更清楚：
>
- 例1a：如果y至少有t个键，并且
- 1b例：y的键少于t，但z至少有t个键。
- 例1c： y和z都只有t-1键。
案例2：如果此BTree只剩下一个根，并且希望从根中删除一个键。请注意，原始描述遗漏了此案例。虽然在该阶段，根确实成为叶（然后转到案例3），但当最后3个节点合并为一个叶节点时，您需要首先将其设置为叶节点（从删除的角度来看，您只能通过这种方式到达一个叶节点）。
情况3：如果节点是叶子，并且移除一个键不会导致节点具有太少的键。这对应于原始描述情况1。
情况4：如果节点是叶子，但是从节点中删除k会导致节点本身的密钥太少，或者它的父节点的密钥太少。这对应于原始描述情况3。
- 情况4a：两个兄弟姐妹的密钥数都是0或t-1。这对应于原产地描述案例3b。然后，我们需要合并的兄弟姐妹与一个键向上级别（从父）。由于这可能会导致父节点的密钥小于t-1，因为父节点中的密钥数量现在由于这种合并而减少了1，因此您需要合并父节点，并在必要时递归地检查其祖先直到根节点。
- 情况4b：要删除的节点的一个兄弟姐妹有多个t-1密钥，这样我们就可以从它的父节点“抓取”一个密钥，并让父节点从它的兄弟节点“抓取”另一个密钥。这对应于原产地描述情况3a。请注意，在这一特定情况下，父级中的键的数量不受影响，只有它由于这个抓取过程而改变了什么键。
除此之外，我想不出任何其他情况。
为了让这个删除代码更清晰，更容易想出，这些是我写的子程序。
def search(self, k, node=None, pth=[], level=0):
"""Give a key to search, return the node (as the page in computer
system concepts), path to this node (which nodes were went through),
idx of the key in the node found, and level in this BTree
of this node."""
node = node or self.root
idx = bisect.bisect_left(node.keys, k)
if idx < len(node.keys) and k == node.keys[idx]:
return (node, pth, idx, level)
elif node.isLeaf:
if k in node.keys:
return (node, pth, idx, level)
raise KeyError("Key not found in this BTree!")
else:
pth.append(node)
return self.search(k, node.pointers[idx], pth, level + 1)
def getSiblings(self, node, parent, i=None):
if i == None:
i = bisect.bisect_left(parent.keys, node.keys[0])
leftSibling, rightSibling = None, None
try:
if i > 0: leftSibling = parent.pointers[i - 1]
except IndexError:
pass
try:
rightSibling = parent.pointers[i + 1]
except IndexError:
pass
return (leftSibling, rightSibling)
def __mergeWithSibling(self, node, leftSibling, rightSibling, pth, i):
if leftSibling != None:
self.__mergeNodes(leftSibling, node, pth[-1], i - 1, i)
else:
self.__mergeNodes(node, rightSibling, pth[-1], i)
def __mergeNodes(self, node, nodeToMerge, parent, i, ptr=None):
if ptr == None: ptr = i + 1
node.keys += parent.keys[i]
node.keys += nodeToMerge.keys
node.pointers += nodeToMerge.pointers
del parent.keys[i]
del parent.pointers[ptr]
def __checkAndMerge(self, node, pth=None):
"""Check if a given node should be merged with its sibling."""
if pth == None:
pth = self.search(node[0])[1]
if len(node.keys) < self.t - 1:
i = bisect.bisect_left(pth[-1].keys, node.keys[0])
leftSibling, rightSibling = self.getSiblings(node, pth[-1], I)
self.__mergeWithSibling(node, leftSibling, rightSibling, pth, I)
self.__checkAndMerge(pth[-1], pth[:-1])
下面是代码（很容易更改为您可能需要的伪代码）：
def deleteKey(self, k):
node, pth, idx, level = self.search(k)
if not node.isLeaf:
# Case 1: If node of k is an internal node, but not leaf:
i = bisect.bisect_left(node.keys, k)
y = node.pointers[i] # y is the child that precedes k.
if len(y.keys) >= self.t:
# Case 1a, if y has at least t keys
print("Running case 2a")
pred = y.keys[-1]
self.deleteKey(pred)
node.keys[i] = pred
else:
# Case 1b: y has fewer than t keys.
z = node.pointers[i + 1] # z is the child that follows k.
if len(z.keys) >= self.t:
succ = z.keys[0]
self.deleteKey(succ)
node.keys[i] = succ
else: # Case 1c: both y and z have only t - 1 keys.
self.__mergeNodes(y, z, node, I)
self.__checkAndMerge(node, pth[:-1])
self.deleteKey(k)
if self.root.keys == []: self.root = self.root.pointers[0]
return
if node == self.root and node.pointers == []:
"""Case 2: (not included in original specification): if this BTree
only has a root left and want to delete a key from root."""
node.isLeaf = True
node.keys.remove(k)
return
if len(node.keys) >= self.t:
"""Case 3: If node is a leaf, and removing a key does not cause
the node having too few keys."""
node.keys.remove(k)
return
i = bisect.bisect_left(pth[-1].keys, node.keys[0])
leftSibling, rightSibling = self.getSiblings(node, pth[-1], i)
nKeysLeft = len(leftSibling.keys) if leftSibling != None else 0
nKeysRight = len(rightSibling.keys) if rightSibling != None else 0
if nKeysLeft <= self.t - 1 and nKeysRight <= self.t - 1:
"""Case 4a, both siblings have # of keys either 0 or t - 1.
Merge the siblings with a key up level. As this may result in
parent node having keys less than t - 1, therefore merge parents
if necessary. """
#print("pth[-2].keys ", pth[-2].keys)
self.__mergeWithSibling(node, leftSibling, rightSibling, pth, i)
self.__checkAndMerge(pth[-1], pth[:-1])
self.deleteKey(k)
if self.root.keys == []:
self.root = self.root.pointers[0]
return
"""Case 4b: One of the siblings of the node to be deleted have more
than t - 1 keys that can be "borrowed". """
print("Running case 3a.")
if nKeysLeft > self.t - 1:
# Then borrow one key from the left sibling to delete.
node.keys.remove(k)
node.keys.insert(0, pth[-1].keys[-1])
pth[-1].keys.pop()
pth[-1].keys.insert(0, leftSibling.keys[-1])
leftSibling.keys.pop()
else: # Borrow one key from the right sibling to delete.
node.keys.remove(k)
node.keys.append(pth[-1].keys[0])
pth[-1].keys.pop(0)
pth[-1].keys.insert(0, rightSibling.keys[0])
rightSibling.keys.pop(0)
至于原著中的内容，案例1-3的描述是正确的（虽然我应该说它们是以一种非常混乱的方式编写的，其中一个原因可能是在BTree中，您不能在这里使用节点的“parent”一词，因为您根本不存储父指针以节省内存，但我只是借用了“parent”一词描述链接到要操作的子节点的某事物）。另外，我应该说，图18.8 d）是完全错误和混乱的，因为在这种情况下，删除“d”作为叶节点的键不会影响该节点的有效性，也不会影响第18.1章中介绍的BTree。描述BTree的其他部分是有意义的。下面附上此BTree的其他子程序供参考：
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 13 17:13:00 2021
@author: Sam_Yan
"""
import bisect
class BTNode:
def __init__(self, keys=None, pointers=None, isLeaf=True):
self.keys = keys or []
self.pointers = pointers or []
self.isLeaf = isLeaf
def __str__(self):
return ("keys: " + str(self.keys) + "\n")
class BTree:
def __init__(self, t=2):
"""t is the degree (# of keys a node contains), ranges between t
and 2t - 1 (both sides included). When t = 2 is a 2-3-4 tree."""
assert (t >= 2 and t == int(t)), "t value of a B-Tree should be >= 2!"
newNode = BTNode()
self.t = t
self.treeStr = ""
self.root = newNode
def insertNonFull(self, node, k):
if node.isLeaf:
bisect.insort(node.keys, k)
return
i = bisect.bisect(node.keys, k)
if len(node.pointers[i].keys) == 2 * self.t - 1:
self.splitChild(node, i)
if k > node.keys[i]: i += 1 # Determine which subtree to go to.
self.insertNonFull(node.pointers[i], k)
def insert(self, k):
r = self.root
if len(self.root.keys) == 2 * self.t - 1:
s = BTNode(isLeaf=False)
self.root = s
s.pointers.append(r)
self.splitChild(s, 0)
self.insertNonFull(s, k)
else:
self.insertNonFull(r, k)
def splitChild(self, node, i):
y = node.pointers[i]
z = BTNode(isLeaf=y.isLeaf)
z.keys = y.keys[self.t:]
if not y.isLeaf: # copy pointers if y is not a leaf:
z.pointers = y.pointers[self.t:]
node.pointers.insert(i + 1, z)
node.keys.insert(i, y.keys[self.t-1])
del y.keys[self.t-1:]
del y.pointers[self.t:]
def __printHelper(self, r=None, level=0):
r = r or self.root
if r != self.root:
self.treeStr += (" " * level + "L-" + str(level) + "-" + str(r))
for node in r.pointers:
self.__printHelper(node, level + 1)
def __delHelper(self, node=None):
if node.isLeaf:
del node.pointers
del node.keys
del node
return
for c in node.pointers:
self.__delHelper(c)
del node.keys
del node.pointers
def __del__(self): # Destruct this BTree.
self.__delHelper(self.root)
def __str__(self):
# Method to obtain string info about this BTree.
self.treeStr = "Root: " + str(self.root)
self.__printHelper()
return self.treeStr
if __name__ == '__main__':
# Testing samples:
t1 = BTree(t=2)
for i in range(28):
t1.insert(i)
print(t1)
print(t1.search(27)[0])
t2 = BTree(t=3)
alphas = "AGDJKNCMEORPSXYZTUV"
alphas = [ch for ch in alphas]
for ch in alphas:
t2.insert(ch)
#print(t2)
t2.insert('B')
#print(t2)
t2.insert('Q')
#print(t2)
t2.insert('L')
#print(t2)
t2.insert('F')
#print(t2)
t2.deleteKey('F')
print(t2)
t2.deleteKey('M')
print(t2)
t2.deleteKey('G')
print(t2)
t2.deleteKey('B')
print(t2)
t2.deleteKey('Z')
print(t2)
t2.deleteKey('D')
print(t2)
"""
t3 = BTree(t=2)
#for ch in ['F', 'S', 'Q', 'K', 'C', 'L', 'H', 'T', 'V', 'W', 'M',
# 'R', 'N', 'P', 'A', 'B', 'X', 'Y', 'D', 'Z', 'E']:
for ch in ['F', 'S', 'Q', 'K', 'C', 'L', 'H', 'T', 'V', 'W', 'M']:
t2.insert(ch)
print(t2)
"""
希望这能有所帮助，我真诚地寻找这个实现的更简单的版本，或者指出潜在的错误或问题（从我的角度来看，在这些代码上测试删除、插入和搜索BTree中的密钥是有意义的）。
根据Knuth的定义，m阶B-树是满足以下性质的树：
- 每个节点最多有m个子节点。
- 每个非叶节点（根节点除外）至少有m/2子节点。
- 如果不是叶节点，根至少有两个子节点。
- 具有k个子节点的非叶节点包含k−1个密钥。
- 所有的叶子出现在同一水平。
让我们看看下面的B-树（顺序5）
让我们看看各种可能的删除。
删除21
不是问题。
- 每个节点最多仍有5个子节点
- 包含21的节点是叶，因此所有提到“非叶节点”的规则都不适用
- 所有树叶仍显示在同一标高上
删除16
需要重新平衡。根现在包含1个元素，比m/2少1个（向下舍入）。
为了修复它，我们借用一个元素（例如18或21）并将其从该叶子移动到根本身。如果树更大，我们将递归地向下重复这个过程。
总论
请记住，大多数实现使用“标记为已删除”节点，而不是实际删除节点。与实际执行删除并可能重新平衡树相比，将节点标记为已删除相对容易。此外，删除通常不像插入那样频繁。
-
我试图找到电报的Api密钥，但我找不到它。我在网站上哪里可以找到它？如果我使用Api Id，我会在C#控制台应用程序中得到错误。
-
问题内容： 在哪里可以找到javax.crypto源代码？ --update 感谢OpenJdk版本，但是jdk6版本呢？ 问题答案： 下载链接 http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/tip/src/share/classes/javax/crypto（OpenJDK版本） http://download.java.net/jdk6/sourc
-
问题内容： 我试图在glibc源代码中找到select（）源代码（Linux，i386架构），但我找不到任何东西（与所述体系结构有关） 谁能指出我的select（）源代码？ 问题答案： select（）不是libc的函数，而是内核函数，因此您需要查看内核源代码。 您可以通过查看手册页来说明这一点：如果在第2节中，则为内核函数；如果在第3节中，则为标准C库的函数，在您的情况下为glibc。 编辑：像
-
问题内容： 我想看看Java API中的方法是做什么的。所以我想要JDK源代码。在重新安装Linux之前，我先安装了包含所有正式源代码的软件包。我只需要告诉Eclipse这个文件在哪里，就可以看到代码。但是现在我没有文件了… 所以问题是：在哪里可以找到它？ 问题答案： 你尚未说出所需的版本， JDK 8源代码的存档以及JDK 7和JDK 6。 此外，你可以浏览或克隆的Mercurial库：8，7，
-
问题内容： 我想使用它们的sha256代码提取centos，tomcat等图像，例如 但是我找不到在任何地方都可以使用的sha256代码。 我在dockerhub存储库中检查了sha256代码的任何提示，但是找不到任何提示。我按标签下载了图像 并检查了图像以查看元数据中是否有sha256代码，但是没有（添加图像的sha256代码可能会更改sha256代码）。 我是否必须自己计算图像的sha256代
-
问题内容： 我想尝试查找Python标准库中某些模块的源代码，但找不到它们。下载python tarball后，我尝试在modules目录中查找，但是它主要包含.c文件。我还尝试查看了OS（mac osx）随附的python所在的目录，该目录中包含它的模块，并且那里似乎主要包含.pyc和.pyo文件。如果有人可以帮助我，我将不胜感激。 （我尝试了问题“如何找到Python模块源的位置？”中的建议，