Introduction to the deletion process of B-tree

In the previous article https://www.jb51.net/article/154157.htm, we introduced the insertion process of B-tree. In this article, we will introduce the deletion process of B-tree.

When deleting a node in a B-tree, it may borrow elements from sibling nodes, exchange elements with child nodes, or even merge nodes.

We use the following tree as the basis for deletion.

First, let's clarify the definition of this tree. It is a 5-order tree. Therefore, the number of elements in each node is 2~4.

We delete the four elements 8, 16, 15, and 4 in turn.

First delete 8, because deleting 8 does not destroy the properties of the tree, so you can delete it directly. Get the following

Then 16 is deleted, which results in only one 13 node left, which does not meet the requirement that the number of elements in the node is 2 to 4. So adjustments are needed. Here you can borrow nodes from the child and raise 17 to get the following picture. It is not possible to borrow nodes from sibling nodes here, because after borrowing 6 from nodes 3 and 6, the remaining 3 will not meet the requirement. In addition, you cannot promote 15 of the children, as that would result in the remaining 14 not meeting the requirements.

Then delete 15. After deleting 15, the same adjustment is required. The adjustment method is to increase 18 and decrease 17 to the original position of 15, and we get the following picture.

Then delete element 4. After deleting 4, only 5 remains in the node, which needs to be adjusted. However, none of its sibling nodes have any extra nodes to borrow, so node merging is required. There are many ways to merge nodes, and we can choose one of them. Here, we select 3 in the parent node to sink and merge it with 1, 2, and 5, as shown in the following figure.

But this adjustment caused 6 to no longer meet the requirements. In addition, 6 non-root nodes, but only 2 children, also do not meet the requirements. Need to continue to adjust. The adjustment method is to sink 10 and merge it with 6, 13 and 18 into the root node, as shown in the following figure.

Finish.

Summarize

The above is the full content of this article. I hope that the content of this article will have certain reference learning value for your study or work. Thank you for your support of 123WORDPRESS.COM. If you want to learn more about this, please check out the following links