Shulou(Shulou.com)05/31 Report--

How to delete B-trees correctly? Many novices are not very clear about this. In order to help you solve this problem, the following small series will explain it in detail for everyone. Those who have this need can come to learn. I hope you can gain something.

When deleting a node in a B-tree, borrowing elements from siblings, swapping elements with children, or even merging nodes may occur.

Let's delete based on the tree below.

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

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

First delete 8, because deleting 8 does not destroy the nature of the tree, so delete it directly. get the following

Then delete 16, which leaves only 13 nodes in the node, which does not meet the requirement of 2~4 elements in the node. So it needs to be adjusted. Here you can borrow nodes from your child and raise 17 to get the following picture. You can't borrow nodes from sibling nodes here, because after borrowing 6 from nodes 3 and 6, the remaining 3 is not enough. Also, you can't raise 15 of your children, because that will cause the remaining 14 to fail.

Then delete 15, which also needs to be adjusted after deleting 15. The adjustment method is that 18 rises and 17 falls to the original position of 15, resulting in the following figure.

Then delete element 4. After deleting element 4, there are only 5 nodes left, which need to be adjusted. However, its sibling nodes do not have redundant nodes to borrow, so node merging is required. There are many ways to merge nodes, so we can choose one of them. Here, we select 3 sink, and 1, 2, and 5 in the parent node to merge, as shown below.

However, this adjustment caused 6 to fail to meet the requirements. In addition, 6 non-root nodes, but only 2 children, also do not meet the requirements. It needs to continue to adjust. The way to adjust is to merge 10 sink, 6, and 13, 18 into the root node, as shown in the following figure.

Did reading the above help you? If you still want to have further understanding of related knowledge or read more related articles, please pay attention to the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.