B-Tree Implementation

Question

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?

Aify · Accepted Answer · 2015-01-19 18:27:40Z

1

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.

answered Jan 19, 2015 at 18:27

Aify

3,5573 gold badges26 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Anoop Dixith Over a year ago

Right, I got it. But in doing so, isn't he NOT COMPARING key with the jth element at all? I was wondering what if the key of the jth element itself is greater than key? He shouldn't even go to j+1th then, right?

Aify Over a year ago

I don't think he's trying to compare with j. If you read the rest of the search function, it's an if-else statement, which leads me to assume that the comparison of j is done in the "if statement". The "else" part (the part that you posted) is just there to make sure that he doesn't get a NPE (if there is no next value)

Anoop Dixith Over a year ago

Well actually, the if condition is for the leaf nodes (if(ht==0)) and else for internal nodes. Also, note that in that if block, he checks from j=0.

Aify Over a year ago

I stand by my answer that it's checking for NPE; it's a tree, and as such it is made up of by smaller trees. This function is a recursive function, so he needs to check to make sure that the internal isn't null, before calling search on the child (which will itself check j, not j+1)

Anoop Dixith Over a year ago

Actually, finally figured it out! It's because in a B-Tree, none of the nodes except the leaf nodes carry any information. They just act as separators. So, that separator will be the first child in the children's entry. So, it need not be searched!

|

Collectives™ on Stack Overflow

B-Tree Implementation

1 Answer 1

6 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Related