英文:
Write a formula which calculates the number of elements in B tree root after every i-th insertion
问题
我已经理解你的请求，以下是翻译好的部分：
插入1、2、...、20个数字到空的B树中，按顺序进行插入。编写一个公式，用于计算在每次第i次插入后B树根节点中的元素数量。第一部分我已经完成，但是在第二部分我遇到了问题。
这是我的做法。
假设N是B树根节点中元素的最大数量。
如果i ≤ N，则公式为：`R(i) = i`。
如果N < i ≤ 2N，则公式为：`R(i) = N`。
如果2N < i ≤ 3N，则公式为：`R(i) = N + 1`，以此类推。
但是通过对答案的核对，似乎我做错了些什么。你能帮我检查并纠正我的解决方案吗？
英文:
Insert 1,2,..,20 numbers to the empty B tree sequentially. Write a formula which calculates the number of elements in B tree root after every i-th insertion. The first part I did, but I'm having trouble in the second part.
Here's what I did.
Let N be the maximum number of elements in the root of the B-tree.
If i ≤ N, the formula is: R(i) = i.
If N < i ≤ 2N, the formula is: R(i) = N.
If 2N < i ≤ 3N, the formula is: R(i) = N + 1 and so on.
But by checking against the answer key, it seems I've done something wrong. Can you revise my solution and correct if it's wrong?
答案1
得分: 1
有不同的B树插入算法，你所寻找的结果取决于它们。我在这里假设没有预先拆分，当一个节点已满时，不会尝试通过将键移动到兄弟节点来延迟拆分。
让我们看看你的陈述：
如果 i ≤ N，则公式为：
R(i) = i。
正确。
如果 N < i ≤ 2N，则公式为：R(i) = N。
不正确。当插入 𝑁+1 时，根节点会分裂成两个节点，每个节点都有 𝑁/2 个键，并且一个值被推到上面，成为新根节点中唯一的键。所以在那个时候 R(𝑁+1) = 1。例如，如果 𝑁=4，那么在插入5之前我们有：
root:
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
└───┴───┴───┴───┘
然后添加5后，我们得到：
root:
┌───┬───┬───┬───┐
│ 3 │ - │ - │ - │
├───┼───┴───┴───┘
┌─────┘ └─────────┐
┌───┬─┴─┬───┬───┐ ┌───┬─┴─┬───┬───┐
│ 1 │ 2 │ - │ - │ │ 4 │ 5 │ - │ - │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
如果 2N < i ≤ 3N，则公式是：
R(i) = N + 1
那应该会引起警告：一个节点永远不会有超过 𝑁 个元素，所以显然 𝑁+1 是错误的。
在树接收到第二级（即插入 𝑁+1 后）后，有一个序列，其中左侧叶节点被填充，分裂为两个，根中添加一个键，然后再次填充左侧叶节点，...等等。在某一时刻，根节点变满并分裂为两个，得到一个具有3级和根中仅一个键的树。
你可以在纸上画出这个过程来理解逻辑。
英文:
There are different insertion algorithms for B-trees, and the results you are looking for depend on them. I will here assume there is no pre-emptive splitting, and when a node is full there is no attempt to delay splitting by moving keys to sibling nodes.
Let's look at your statements:
> If i ≤ N, the formula is: R(i) = i.
Correct.
> If N < i ≤ 2N, the formula is: R(i) = N.
Not correct. When 𝑁+1 is inserted, the root node splits into two nodes with each 𝑁/2 keys, and one value is pushed up to become the only key in a new root node. So at that time R(𝑁+1) = 1. For example, if 𝑁=4, then before inserting 5 we have:
root:
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
└───┴───┴───┴───┘
Then after adding 5, we get:
root:
┌───┬───┬───┬───┐
│ 3 │ - │ - │ - │
├───┼───┴───┴───┘
┌─────┘ └─────────┐
┌───┬─┴─┬───┬───┐ ┌───┬─┴─┬───┬───┐
│ 1 │ 2 │ - │ - │ │ 4 │ 5 │ - │ - │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
> If 2N < i ≤ 3N, the formula is: R(i) = N + 1
That should have raised an alarm: a node could never have more than 𝑁 elements, so obviously 𝑁+1 is wrong.
After the tree has received its second level (so when 𝑁+1 has been inserted), there is a sequence where the left side leaf node is filled, splits into two, adding one key in the root, and again the left side leaf node is filled, ...etc. At a certain moment the root gets full and splits into two, to get a tree with 3 levels and only one key in the root.
You may want to draw this on paper and see the logic.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论