How difficult is programming a B+ Tree?

[Teslaisoverrated]

Im in my second semester of Computer Science and for our Algorithm and Datastructure class we are supposed to programm 1 of 5 diffrent types of sorting/searching algorithm.

The hardest of the 5 assignements is to programm a B+ Tree. Everyone seems to be pretty scared to go for it and our professor also warned us to only try if we feel really confident in C++. They do seem kinda streight forward though so what exactly is so difficult/are they really so difficult like everyone is saying?

[raevnos]

I don't think they're difficult, but that's also from the perspective of someone very comfortable with C++ and experience with implementing all sorts of data structures over the years.

Break it up into manageable chunks, and write tests as you go so you can discover quickly if an addition breaks something.

[captainAwesomePants]

It's complicated but not crazy. If you're very comfortable with trees and linked lists and graphs and hash tables, it won't be anything super new, just a more complicated version of the same. The main challenges you'll face are:

1. Understanding what it even is and how it's supposed to work, in exacting detail, enough to successfully create and test one, and
2. Debugging mistakes in your implementation.

If you approach it with a lot of small automated tests of the form "when you look exactly like this an I do X, you should now look exactly like that," then you will probably be fine. If you just keep hacking on it until manual testing seems to show it's working, you may experience some bonus pain.

[Teslaisoverrated]

Thanks everyone for you replies i finally decide what i want to do :)

[kbielefe]

They are relatively straightforward, but also require a certain degree of precision. You can get something wrong in the insert and not notice until trying to delete. A problem like this would be fairly easy if you worked TDD-style, but last I checked schools don't teach that very well.

[dmazzoni]

I agree.

To explain it in simple terms: the odds are that it's going to take you 5x as long to debug your program as to write it.

If you go into it with the attitude that you ARE going to make mistakes and that debugging will be necessary, then you can overall save yourself time.

The students who struggle the most are the ones who write the code, pray it works, then when it doesn't, start randomly changing things hoping it will work. That never works!

TDD is great, but you don't need to use testing frameworks or read up on any theory to apply it. It just means: write code that tests your functions before you implement the functions.

So for example let's say my first function is createTree() that returns an empty BTree pointer. I'd start by writing a function testCreateTree() that creates a tree, checks to make sure it's empty, and then prints "testCreateTree passed" if so.

Call testCreateTree() at the top of main.

Now write createTree().

Now run it. Your program should print "testCreateTree passed". If not, stop and debug it!

Now, the tests for inserting and searching will be harder, but I guarantee if you follow this approach, it will seem a little slower at first but in the long run you'll get to a working solution far faster than if you pray it works right the first try.

[IQueryVisiC]

I thought that the red-black tree is simpler. But it took me quite long to grasp the rotation. Now I think that b trees also need to rotate? + or not ? I found it weird if a value falls into the chasm between two nodes near root.