Question

Using Java
Qaustion 1)

A) Draw a B-tree of order 5, which is received sequentially
introduction of the following elements: 200,300,8,17,100,2,20,30,89,26,14,15 ,10
B) Show the result of deleting elements 15, 14, 10, 8 from the constructed
trees.

Answer 1

Let us start of by defining what is a tree, then we will come down to B-Trees.
Tree is a data structure that is used to simulate a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

This Diagram clearly illustrates how a tree looks like. The node at the top (the one with value 20) is the root. the nodes on the left are part of the left subtree and those on the right are part of the right subtree. The nodes without any children are leaf nodes.

Now coming on to what is a B-tree:
B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children.

Now the first question that must come to your mind is, what does the order of a B-tree mean.
I would like to introduce you with two important terms

1. Order
2. Degree

Degree represents the minimum number of children a node in the B Tree can have (except for the root. And the Order represents the maximum number of children.

How do we insert and delete in a B-tree?

The answer is pretty straight forward, find a leaf node where you can insert the element in a sorted manner. If the node has a size greater than or equal to the order the split it at the middle. There is a similar procedure with the delete operation. Always remember that you need to insert only in a leaf node.

Deletion should also be done so that only the structure of the leaf is changed. The examples will make it clear.

With all this information in hand, let us now proceed with the question, in a step by step manner.

Insert 200, 300, 8, 17: Since the first four nodes enter without any need of modification we simply insert it in sorted order.

Insert 100: the root node has 5 elements now so we need to split it across the middle element.

Insert 2: 2 gets inserted in the sorted position

Insert 20:

Insert 30: since after insertion of 30 the leftmost node has 5 elements so we need to split it at the middle position. and move 17 at the top node.

Insert 89: Simple sorted inserion

Insert 26: Simple sorted insertion

Insert 14: Simple sorted insertion

Insert 15: Simple sorted insertion

Insert 10: Again the leftmost node has 5 elements after insertion of 10. So we split it at the middle position and then 10 moves on the upward node.

Delete 15: 15 gets removed so to maintain the structure 20 moves to the top node and 17 moves in place of 15.

Delete 14: Again similar to the last operation, 14 gets deleted 17 moves left, 20 moves down and 26 moves up.

Delete 10: Since 10 gets deleted so we merge the two leftmost intervals.

Delete 8: Simple deletion in place.

Just keep in mind that you need to keep all leafs at the same level while you proceed with the deletion and insertion operations.

Happy to help. In case of any doubts feel free to post comments and get your doubts clarified.