Advanced search trees

Question 1

M-ary tree

Answer 1

A binary search tree expansion where each node has up to m children, and m-1 keys.

Question 2

M-ary tree height

Answer 2

If all the nodes are full, then the tree’s height is O(logm(n)). (m-degree of the tree, n-number of different nodes)

Question 3

B-tree

Answer 3

1. An m-ary tree
2. Each non root, non leaf node has at least m/2 children.
3. All leafs are at the same level.

Question 4

B-tree insertion (idea)

Answer 4

Insert in a similar fashion to a BST. If the node is full, divide it into two, and send the median up. if it is also full do the same recursively.

Question 5

B-tree deletion from leaf (idea)

Answer 5

If the node still has a least (m/2 - 1) -> done.
Else -> Try taking from a sibling node.
Not possible -> Merge with sibling node.

Question 6

B-tree deletion from non leaf node (idea)

Answer 6

Find the successor found in the leaf and replace it.

Question 7

B-tree run time costs

Answer 7

All actions done in O(logn)

Question 8

2-3 trees

Answer 8

B trees where the degree m=3