Problem Detail: I have a B-Tree of order 5. So the keys are between $lceil n/2 rceil- 1 leq keys leq n – 1$ and children are between $lceil n/2 rceil leq children leq n $. Am I doing it right? So a full node would be of 4 keys, how do I split that, because when I split that full node, I get uneven keys in any of the children. Example: ${G}$ at level $0$, ${A, C, E}$ and ${H, K, N, Q}$ at level $1$ Here ${H, K, N, Q}$ is a full node, when I insert T, I must pre-split ${H, K, N, Q}$, I get one key in either of the subtree which is wrong as the selection of keys suggest that they must be between 2 and 4. What am I doing wrong?
Asked By : Abdussami Tayyab
Answered By : Hendrik Jan
It seems you are doing nothing wrong. Like you say, for a B-tree of order $n$ the number of children is between $lceil n/2 rceil$ and $n$, the number of keys is one less. For $n=5$, keys are between $2$ and $4$. When you add a key to a node of size $4$, you get two new nodes of size $2$ and one new key which is pushed upwards. When this happens at the root, a new root with a single key is formed. Your example. Add $T$ to the tree. At the root $G$ go right, to ${H,K,N,Q}$. With $T$ this becomes ${H,K,N,Q,T}$ which is too heavy and we split into ${H,K}$ and ${Q,T}$. Middle key $N$ is pushed upwards to the root. In the new configuration the root ${G,N}$ with two keys has three children ${A,C,E}$, ${H,K}$ and ${Q,T}$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/25867 3.2K people like this
