CODEWITHSUNDEEP
javaalgorithmdata-structurestreeb-tree
Anoop Dixith
Anoop Dixith

Reputation: 643

B-Tree Implementation

I was reading about implementing B-Tree from Rober Sedgewik's and found this snippet in the else part of search method from this link: http://algs4.cs.princeton.edu/62btrees/BTree.java.html

// internal node
        else {
            for (int j = 0; j < x.m; j++) {
                if (j+1 == x.m || less(key, children[j+1].key))
                    return search(children[j].next, key, ht-1);
            }
        }

I banged my head but couldn't understand why he directly starts comparing key with j+1th element of children and not jth. Could someone please through some light upon this specific point?

Upvotes: 1

Views: 689

Answers (1)

Aify
Aify

Reputation: 3537

If you look at his declaration of the less() method, you'll notice that it uses compareTo.

Essentially, what he wanted to do was key.compareTo(children[j+1].key)

But why would he use j+1 instead of j? To understand this, look at the first part of his conditional statement; he uses j+1 == x.m, meaning that he wants to test to see if j+1 is the limit. If j+1 = x.m, he doesn't want to continue incrementing j, so he returns. However, if it is not the limit yet, check compare the current key with the next key in the list (because the next key exists). IF the next key in the list is "less" than the current key, search for the current key.

In short: If j+1 doesn't exist, the first half of the if statement will catch it and it will break out of the for loop. Otherwise, check j+1's key.

Upvotes: 1

Related Questions