Btree node deletion algorithm
Good day!
The history of this text is as follows. The child was asked to program btree. I sometimes help him. Decided that this is trivial. But attempts to solve the problem by success were not crowned. Searches for any reasonable description and / or code were also futile. Passed son passed long ago, but my paranoid nature made me solve the problem. Maybe someone will come in handy.
Btree balanced search tree (b tree)
Definition not cite. Find it is not difficult. Search, insert key are trivial.
')
A node will be called empty if it contains t-1 keys, i.e. no keys can be removed from it. The root is by definition never empty. Also, a subtree will be called empty if all its nodes are empty. Empty tree is arranged uniquely. Accordingly, a full node will be called a node with the number of keys 2t-1. The number of keys in an empty tree is obvious
(t-1) * (1 + t + t ^ 2 + ... + t ^ h) = t ^ (h + 1) -1, where h is the height of the tree (root height = 0).
If inserting a key into btree is unambiguous, then deletion is ambiguous.
If the node containing the found key is leaf, then if the node is not empty, the keys are shifted, replacing the one being deleted:
If the node is empty, you need to convert the tree so that it becomes non-empty.
For a given key, we call the leaf on the left leaf node into which we rest, moving first to the left descendant of this key, and then to the leaf node along the last descendants. The left sheet on the right is defined in the same way. First to the right stream, then zero descendants.
If the node is not leaf, this key has a right and left descendant and a parent (if not root), in which our node is in position i. By the definition of btree, all keys of the left child are smaller, and all keys of the right child are larger than the given key. Without violating the definition of btree, which key can replace the deleted one?
In the figure, the keys marked in blue are smaller than this, yellow is greater than this. The deleted key can be replaced only with the largest of the smaller ones or the smallest of the largest ones. In the figure they are circled in red and blue, respectively. The first is the last key of the right sheet on the left, the second is the first key of the left sheet on the right. If one of them is not empty, simply change the deleted key to one of them and remove the replacement key from the source sheet, if not, return to the task how to make the leaf node non-empty.
To solve the problem of making this leaf node non-empty, consider two btree transformations: merge and outweigh. If this node is not empty, and both descendants of this key are empty, you can do a merge transformation. This key is removed from its node, one node is made from it and its descendants. Since the root is never empty, if all nodes are empty, and at the root of one key, merging is done, and the old root is deleted.
The second Btree transform is overweight. If the given key has the right leaf on the left is not empty, the left leaf on the right is not full, you can make a right advantage. If the left sheet on the right is full, perform the separation. This key is inserted into the zero position of the left sheet on the right, increasing by one the number of keys in it. Replace this key with the last key of the right sheet on the left, and delete it.
Similarly, the advantage is to the right. The height of the odds from one to the height of the tree.
Now, actually, the algorithm is how to make this sheet non-empty. The process is called crimping wood. Consider crimping to the right.
The left brother is a node at the same level to the left of the current one. The brothers have a common ancestor and the key of a common ancestor. Through the key of the common ancestor, the keys are re-weighted.
If the left brother is not empty, outweigh the key. Problem solved. If the left sibling is empty, but the parent is not empty, perform the merge. Problem solved. If both the parent is empty and the left brother, we recursively ask for a spin from the parent, then from the left (any) brother.
Similarly, crimping is done to the left. The ambiguity of the removal is whether you can first crimp either right or left. You can also first request the odds, and then merge, and vice versa.
Proving reluctance, but intuition shows that crimped always.
It must be remembered that when rebuilding a tree, the key found for deletion may be the result of merges in other nodes of the tree. But to lose touch with the replacement keys can not.
As one of the conclusions it can be argued that to speed up the removal of keys, it is desirable to keep the leaf nodes non-empty. Those. in his spare time, do the pressing down of the tree by merging. It does not make sense to outweigh.
You can also offer some optimization.
Btree is a low but wide tree. Walking on the branches can be expensive. For optimization, we can suggest the parameter “branch weight” - the number of keys in it. Since the weight of an empty tree is a constant for one height, you can check the weight by walking along the branches. If it is equal to the weight of an empty tree, there is nothing to do there, if not, we’ll stop on it, just press one key from it. Weight management is simple. When inserting a key, the weight of all nodes along the insertion path is incremented; if you remove the current node and all parents to the root, it is decremented.
Terminology own.
I say goodbye to this, I hope I am not tired. Listing with ++ is attached (without optimization and not too combed).
PS Ripened and proof.
If there is at least one non-empty sheet, you can always move it to the one you need. If there is not even one sheet above the sheets, we merge. Further, by induction. Given that the root is never empty.
An optimization option has also surfaced. If the node in which you want to remove the key is not empty, and all the left and right descendants are empty, the key is simply removed, and the descendants are glued together. Those. if the node is not empty, it is not necessary to go further than the nearest descendants to the left and right.
Sources with ++ .
The history of this text is as follows. The child was asked to program btree. I sometimes help him. Decided that this is trivial. But attempts to solve the problem by success were not crowned. Searches for any reasonable description and / or code were also futile. Passed son passed long ago, but my paranoid nature made me solve the problem. Maybe someone will come in handy.
Btree balanced search tree (b tree)
Definition not cite. Find it is not difficult. Search, insert key are trivial.
')
Removing a key from btree
A node will be called empty if it contains t-1 keys, i.e. no keys can be removed from it. The root is by definition never empty. Also, a subtree will be called empty if all its nodes are empty. Empty tree is arranged uniquely. Accordingly, a full node will be called a node with the number of keys 2t-1. The number of keys in an empty tree is obvious
(t-1) * (1 + t + t ^ 2 + ... + t ^ h) = t ^ (h + 1) -1, where h is the height of the tree (root height = 0).
If inserting a key into btree is unambiguous, then deletion is ambiguous.
If the node containing the found key is leaf, then if the node is not empty, the keys are shifted, replacing the one being deleted:
If the node is empty, you need to convert the tree so that it becomes non-empty.
For a given key, we call the leaf on the left leaf node into which we rest, moving first to the left descendant of this key, and then to the leaf node along the last descendants. The left sheet on the right is defined in the same way. First to the right stream, then zero descendants.
If the node is not leaf, this key has a right and left descendant and a parent (if not root), in which our node is in position i. By the definition of btree, all keys of the left child are smaller, and all keys of the right child are larger than the given key. Without violating the definition of btree, which key can replace the deleted one?
In the figure, the keys marked in blue are smaller than this, yellow is greater than this. The deleted key can be replaced only with the largest of the smaller ones or the smallest of the largest ones. In the figure they are circled in red and blue, respectively. The first is the last key of the right sheet on the left, the second is the first key of the left sheet on the right. If one of them is not empty, simply change the deleted key to one of them and remove the replacement key from the source sheet, if not, return to the task how to make the leaf node non-empty.
To solve the problem of making this leaf node non-empty, consider two btree transformations: merge and outweigh. If this node is not empty, and both descendants of this key are empty, you can do a merge transformation. This key is removed from its node, one node is made from it and its descendants. Since the root is never empty, if all nodes are empty, and at the root of one key, merging is done, and the old root is deleted.
The second Btree transform is overweight. If the given key has the right leaf on the left is not empty, the left leaf on the right is not full, you can make a right advantage. If the left sheet on the right is full, perform the separation. This key is inserted into the zero position of the left sheet on the right, increasing by one the number of keys in it. Replace this key with the last key of the right sheet on the left, and delete it.
Similarly, the advantage is to the right. The height of the odds from one to the height of the tree.
Now, actually, the algorithm is how to make this sheet non-empty. The process is called crimping wood. Consider crimping to the right.
The left brother is a node at the same level to the left of the current one. The brothers have a common ancestor and the key of a common ancestor. Through the key of the common ancestor, the keys are re-weighted.
If the left brother is not empty, outweigh the key. Problem solved. If the left sibling is empty, but the parent is not empty, perform the merge. Problem solved. If both the parent is empty and the left brother, we recursively ask for a spin from the parent, then from the left (any) brother.
Similarly, crimping is done to the left. The ambiguity of the removal is whether you can first crimp either right or left. You can also first request the odds, and then merge, and vice versa.
Proving reluctance, but intuition shows that crimped always.
It must be remembered that when rebuilding a tree, the key found for deletion may be the result of merges in other nodes of the tree. But to lose touch with the replacement keys can not.
As one of the conclusions it can be argued that to speed up the removal of keys, it is desirable to keep the leaf nodes non-empty. Those. in his spare time, do the pressing down of the tree by merging. It does not make sense to outweigh.
You can also offer some optimization.
Btree is a low but wide tree. Walking on the branches can be expensive. For optimization, we can suggest the parameter “branch weight” - the number of keys in it. Since the weight of an empty tree is a constant for one height, you can check the weight by walking along the branches. If it is equal to the weight of an empty tree, there is nothing to do there, if not, we’ll stop on it, just press one key from it. Weight management is simple. When inserting a key, the weight of all nodes along the insertion path is incremented; if you remove the current node and all parents to the root, it is decremented.
Terminology own.
I say goodbye to this, I hope I am not tired. Listing with ++ is attached (without optimization and not too combed).
PS Ripened and proof.
If there is at least one non-empty sheet, you can always move it to the one you need. If there is not even one sheet above the sheets, we merge. Further, by induction. Given that the root is never empty.
An optimization option has also surfaced. If the node in which you want to remove the key is not empty, and all the left and right descendants are empty, the key is simply removed, and the descendants are glued together. Those. if the node is not empty, it is not necessary to go further than the nearest descendants to the left and right.
Sources with ++ .
Source: https://habr.com/ru/post/242411/
All Articles