节点必须包含的B树的最小密钥数是多少？ [英] What are the minimum number of keys a node must contain for a B Tree of order n?
问题描述
假设我想插入一个值k一棵B树。
在搜索适当的叶节点插入值k后，对特定叶节点中存在的值进行计数。如果叶节点已满，则：
1.从叶元素和新元素中选择单个中值。将节点分为两个节点.median值转移到父节点。
2.在m / 2-1之后将节点分成两个节点（m是树）position.median值被转移到父节点。之后将该值插入到适当的位置。
以下哪种方法是正确的？
另一个问题：
键的最小数量是多少一个节点必须包含一个订单n的B树？我已经搜索到互联网和书籍，但是无法得到确切的方程式，我可以找到最小的密钥数量：e，g如果order = 5然后最小数量的任何节点（除根）的键为2。如何到达？
任何答案都将不胜感激！ / p>
根据Knuth的定义，m阶的B树是满足以下属性的树：
- 每个节点最多有m个孩子。
- 每个非叶节点（root除外）至少有ceil（m/2）子节点。
- 如果根目录不是叶节点，则至少有两个子节点。
- 带k个孩子的非叶节点包含k-1个键。
- 所有的叶子都显示在同一个级别并携带信息。
每个内部节点的密钥作为分割其子树的分离值。例如，如果内部节点有3个子节点（或子树），那么它必须有2个键：a1和a2。最左边的子树中的所有值将小于a1，中间子树中的所有值都将在a1和a2之间，最右边的子树中的所有值都将大于a2。
内部节点
内部节点是除叶节点和根节点之外的所有节点。它们通常表示为一组有序元素和子指针。每个内部节点包含最多的U个孩子和最少的L个孩子。因此，元素的数量总是小于子指针的数量（元素的数量在L-1和U-1之间）。 U必须是2L或2L-1;因此每个内部节点至少是一半满。 U和L之间的关系意味着可以连接两个半满的节点以形成合法节点，并且一个完整节点可以分为两个合法节点（如果有一个空间将一个元素推入父节点）。这些属性使得可以删除并将新值插入到B树中并调整树以保留B树属性。
根节点
根节点的子节点数与内部节点的上限相同，但没有下限。例如，当整个树中的L-1元素少于一个时，根将是树中唯一的节点，根本没有子节点。
叶节点
叶节点对元素数量有相同的限制，但没有子节点，没有子指针。
http://en.wikipedia.org/wiki/B -Tree
添加：
一个B树使用Knuths定义的顺序5（最大数量的孩子）[4将是最大密钥数]。
分裂后内部节点的最小子数为是3 [2键]。由于当一个节点溢出B-Tree的顺序时，节点就会分裂。
列表中的B-Tree 11108,3267,11357,12080,6092
添加3267，11108，11357，12080;这是显示钥匙，而不是孩子。
└──3267，11108，11357，12080
然后添加6092;
在拆分之前（键数> 1）= [5] 5-1 = 4]：
└──3267，6092，11108，11357，12080
分割后：
└──11108
├──3267,6092
└──11357，12080
注意：根节点没有最小数的钥匙/孩子作为其他节点。
删除：
删除后重新平衡
如果从叶节点删除元素已将其置于最小大小之下，则必须重新分配某些元素以使所有节点达到最低在某些情况下，重新排列会将缺陷转移给父母，并且重新分配必须在树上迭代地应用，甚至可能应用到根。由于最小元素数不适用于根，所以使root成为唯一不足的节点不是问题。重新平衡树的算法如下：需要引用
-
如果正确的兄弟姐妹拥有超过最小数量元素
- 将分隔符添加到缺少节点的末尾
- 替换父元素中的分隔符与正确兄弟姐妹的第一个元素
- 将正确兄弟姐妹的第一个孩子作为缺少节点的最后一个孩子
-
否则，如果左边的兄弟姐妹超过
元素的最小数量
- 将分隔符添加到缺少节点的开始
- 将父节点中的分隔符替换为左兄弟的最后一个元素
- 插入最后一个左兄弟的孩子作为缺乏节点的第一个孩子
-
如果两个直系兄弟姐妹只有最少数量的元素
- 创建一个新节点，其中包含所有元素e不足的节点，来自其兄弟姐妹之一的所有元素，以及两个组合的兄弟节点之间的父节点中的分隔符
- 从父项中删除分隔符，并替换分离的两个子节点使用组合节点
- 如果父元素中的元素数量最小，则将该缺省节点重复这些步骤，除非是根节点，因为根被允许为
唯一需要解决的其他情况是当根没有元素和一个孩子。在这种情况下，只需将其替换为唯一的孩子就可以了。
预删除节点9062。
└──6169,128989
├──1009,44238,5139
├──6625,9062
└──12909,14508,14703， 14985
平衡前
└──6169，12789
├──1009,4238,5139
├──6625
└──12909,14508,14703,14985
平衡后
└──6169，12909
├──1009，4238，5139
├──6625，12789
└──14508，14703，14985
正如你所看到的，中间节点的孩子从父母那里借了12789，以满足最低要求，而父母从最适合大多数孩子的父母借来12909这是最低要求。
I have two books of Data Structures.In two books, there is two different approach of B-Tree insertion:
Suppose i want to inset a value k into a B-Tree. after searching for a appropriate leaf node to insert the value k, values present in the particular leaf node is counted. If leaf node is full then :
1.A single median is chosen from among the leaf's elements and the new element.After that split the node into two nodes.median value is shifted to parent node.
2.Split the node into two nodes after m/2-1(m is order of tree)position.median value is shifted to parent node.After that insert the value to the appropriate position.
Which one of the following method is correct?
Another Question:
What are the minimum number of keys a node must contain for a B-Tree of order n?I have searched the internet and books but unable to get the exact equation by which I can find out the minimum no of keys: e,g if order=5 then minimum number of keys for any node(except root)is 2 .How is this coming?
Any answers would be greatly appreciated!
According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:
- Every node has at most m children.
- Every non-leaf node (except root) has at least ceil(m⁄2) children.
- The root has at least two children if it is not a leaf node.
- A non-leaf node with k children contains k−1 keys.
- All leaves appear in the same level, and carry information.
Each internal node’s keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: a1 and a2. All values in the leftmost subtree will be less than a1, all values in the middle subtree will be between a1 and a2, and all values in the rightmost subtree will be greater than a2.
Internal nodes
Internal nodes are all nodes except for leaf nodes and the root node. They are usually represented as an ordered set of elements and child pointers. Every internal node contains a maximum of U children and a minimum of L children. Thus, the number of elements is always 1 less than the number of child pointers (the number of elements is between L−1 and U−1). U must be either 2L or 2L−1; therefore each internal node is at least half full. The relationship between U and L implies that two half-full nodes can be joined to make a legal node, and one full node can be split into two legal nodes (if there’s room to push one element up into the parent). These properties make it possible to delete and insert new values into a B-tree and adjust the tree to preserve the B-tree properties.
The root node
The root node’s number of children has the same upper limit as internal nodes, but has no lower limit. For example, when there are fewer than L−1 elements in the entire tree, the root will be the only node in the tree, with no children at all.
Leaf nodes
Leaf nodes have the same restriction on the number of elements, but have no children, and no child pointers.
http://en.wikipedia.org/wiki/B-Tree
ADDING:
A B-Tree of order 5 (max number of children) [4 would be the max number of keys] using Knuths definition.
The minimum number of children for an internal node after a split would be 3 [2 keys]. Since a node splits when it overflows the order of the B-Tree.
B-Tree for the list 11108, 3267, 11357, 12080, 6092
After adding 3267, 11108, 11357, 12080; this is showing keys, not children.
└── 3267, 11108, 11357, 12080
Then adding 6092; this is showing keys, not children.
Before split (number of keys > order-1) [5 > 5-1=4]:
└── 3267, 6092, 11108, 11357, 12080
After split:
└── 11108
├── 3267, 6092
└── 11357, 12080
Note: the root node does not have the min number of keys/children as other nodes.
DELETING:
Rebalancing after deletion
If deleting an element from a leaf node has brought it under the minimum size, some elements must be redistributed to bring all nodes up to the minimum. In some cases the rearrangement will move the deficiency to the parent, and the redistribution must be applied iteratively up the tree, perhaps even to the root. Since the minimum element count doesn't apply to the root, making the root be the only deficient node is not a problem. The algorithm to rebalance the tree is as follows:[citation needed]
If the right sibling has more than the minimum number of elements
- Add the separator to the end of the deficient node
- Replace the separator in the parent with the first element of the right sibling
- Append the first child of the right sibling as the last child of the deficient node
Otherwise, if the left sibling has more than the minimum number of elements
- Add the separator to the start of the deficient node
- Replace the separator in the parent with the last element of the left sibling
- Insert the last child of the left sibling as the first child of the deficient node
If both immediate siblings have only the minimum number of elements
- Create a new node with all the elements from the deficient node, all the elements from one of its siblings, and the separator in the parent between the two combined sibling nodes
- Remove the separator from the parent, and replace the two children it separated with the combined node
- If that brings the number of elements in the parent under the minimum, repeat these steps with that deficient node, unless it is the root, since the root is permitted to be deficient
The only other case to account for is when the root has no elements and one child. In this case it is sufficient to replace it with its only child.
Pre-deleting node 9062.
└── 6169, 12789
├── 1009, 4238, 5139
├── 6625, 9062
└── 12909, 14508, 14703, 14985
Before balancing
└── 6169, 12789
├── 1009, 4238, 5139
├── 6625
└── 12909, 14508, 14703, 14985
After balancing
└── 6169, 12909
├── 1009, 4238, 5139
├── 6625, 12789
└── 14508, 14703, 14985
As you can see, middle node child borrowed 12789 from it's parent to meet the minimum requirements and the parent borrowed 12909 from it's right most child to meet it's minimum requirements.
这篇关于节点必须包含的B树的最小密钥数是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
