how can I prove that the height(h) of a Btree, with n keys, where every node that is not a leaf has exactly d sons, keeps this trait? $$h\le log_d((d-1)n+1)-1$$

I tried this with nodes, but i am supposed to do it with n (keys) and dont know how:

$nodes =\sum_{i=0}^{h}d^i=1+(d(d^h-1)/(d-1) \rightarrow$ $nodes(d-1)+1=d^{h+1}\rightarrow$ $h=log_d((d-1)n+1)-1$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.