Delete operation
Delete operation is complicated, mainly because delete items that may be on the leaf node or on a leaf node, and delete after may lead to not comply with the provisions of the B tree, call this lead to unbalanced B tree here, so want to merge, left-handed and right-handed, operation, to comply with the provisions of the B tree (i.e., let the B tree balance). In addition, if it is to delete non-leaf node items, it is necessary to find middle-order precursors to replace them.
Is a
The item to be deleted is on the leaf node and does not affect the balance structure of the B-tree. For example, delete “I”, search from the root node, “I” is greater than “D”, go to the second branch,
“I” is greater than “F”, continue to compare, “I” is greater than “H” continue to compare, “I” is less than “K”, so the third branch continues to search,
Find the “I”,
Directly delete I to complete the deletion.
Case 2
The item to be deleted is on the leaf node, and breaking balance after deletion requires borrowing items from the right sibling, which has enough items to lend to it. For example, delete “G”, start from the root node, “G” is greater than “D”, go to the right subtree,
Compare the values of the items in each node and find that they should go to the second branch,
Find the “G”,
At this time, it is found that the right sibling of node “G” has an item to lend to it, so it deletes “G” and performs left-rotation operation. Left-rotation means that the original parent node “H” moves down to the left child node to fill the original “G” node, and the minimum item “I” in the right child node is promoted to the parent node, finally as follows:
The deletion is complete.
Is three
The item to be deleted is on the leaf node, and breaking balance after deletion requires borrowing items from the left sibling, which has enough items to lend to it. For example, delete “L”, start at the root, “L” is greater than “D”, go to the right subtree,
Compare the values of the items in each node and find that they should go to the fourth branch,
Find the “L”,
At this time, it found that the left sibling of “L” node had an item to lend to it, so it deleted “L” and then performed dextral rotation. Dextral rotation means that the original parent node “K” was moved down to the right child node to fill the original “L” node, and the maximum item “J” in the left child node was promoted to the parent node, finally as follows:
The deletion is complete.
Is four
The item to be deleted is on the leaf node, removed out of balance, and the left and right siblings have no items to lend to it. For example, delete “G”, start from the root node, “G” is greater than “D”, go to the right subtree,
Compare the values of the items in each node and find that they should go to the second branch,
Find the “G”,
At this time, it is found that after the deletion of “G” node, the left and right sibling nodes cannot lend items to it and perform the merge operation.
In the merge operation, the item “F” corresponding to the parent node is moved down to the left child node, and the remaining items in the right child node are also moved to the left child node (note that there are no other items after the “G” item is deleted from the right child node). The final result is as follows, and the deletion operation is completed.
Note that if the parent node is unbalanced after the merge operation, the parent node needs to continue to be balanced. For example, in the following example, the “C” item needs to be removed. The root node starts with the “D” comparison, and less than “D” is usually the first branch.
If “C” is greater than “B”, it goes to the second branch.
Find the “C”,
After the “C” item is deleted, the left and right sibling nodes cannot lend items to it.
Perform the merge operation, move the item “B” corresponding to the parent node down to the left child node, and also move all the remaining items in the right child node to the left child node. After the merge, the result is as follows: the parent node has become empty, and the tree is unbalanced.
At this point, the right sibling of the parent node can lend items to it, that is, to perform left-rotation operation, the parent node “D” moves down to the parent node, and the leftmost item “F” of the parent node’s sibling rises.
In addition, left-handed operation also involves moving the first branch (i.e., “E”) of the node corresponding to the movement item “F” to the rightmost branch of the parent node “D”. The final result is as follows:
Is five
The item to be deleted is on a non-leaf node. For example, delete “M”, start at the root node, “M” is greater than “H”, go to the second branch,
Compare the items in the child node one by one, find “M”,
The first step of deleting non-leaf node items is to find the corresponding middle-order precursor, that is, the item with the maximum value in the child node of the first branch.
Then it goes all the way to the last branch, finally finds “L” as the precursor, and promotes it to the position of the item to be deleted “M”, causing the tree imbalance, but it finds that its sibling nodes can lend items to it.
Therefore, the parent node “K” moves down to the original position of the precursor, and the rightmost item “J” of the left sibling node is promoted to the parent node. In addition, if the item “J” of the left sibling node has a right child node, it also needs to be hung to the left of the node “K”. The deletion is complete.
In addition, let’s look at deleting the root node, deleting the root node with only one item, like “D”,
Find the middle-order precursor, that is, the maximum term in the child node of the first branch,
Go all the way to the last branch, eventually find “C” as the precursor, and promote it to the root node,
This causes an imbalance, and the original “C” node’s left and right siblings can not lend to it,
The item “B” of the parent node is moved down to the left child node. After the merger, the original parent node becomes empty, resulting in imbalance. At this time, its sibling node can lend items to it, so it needs to perform left-rotation operation.
The left turn will move “C” down, “F” up,
It also attaches the “E” item to the “C” node, ending as follows.
————- Recommended reading ————
Summary of my open Source projects (Machine & Deep Learning, NLP, Network IO, AIML, mysql protocol, Chatbot)
Why to write “Analysis of Tomcat Kernel Design”
My 2017 article summary – Machine learning
My 2017 article summary – Java and Middleware
My 2017 article summary – Deep learning
My 2017 article summary — JDK source code article
My 2017 article summary – Natural Language Processing
My 2017 Article Round-up — Java Concurrent Article
Talk to me, ask me questions:
Welcome to:
