c++ 2-3 Tree Insertion
Posted on 2009-04-22
I'm working on a project that involves inserting items (in my case, integers) into a 2-3 tree, in c++. I've found a lot of general articles that talk about the conceptual implementation of inserting, but I am having a hard time figuring out how to traverse up the tree when doing an insertion that requres you to add a new empty node. For instance, let's say we're adding numbers 1-10 to an initially empty tree. When I reach inserting number 6 the tree looks like this
[3, -1] <---minimum of second, minimum of third
[2,-1] [4,5] NULL
(1) , (2), NULL (3) ,(4), (5)
now when you add 6, you need to create a new node, switch 5 to be it's left child, 6 to be it's middle, and reattach the new node holding 5 and 6 as the right child of the root.
That's easy enough to explicitly hack in as you can say make that node the right child of the parent of the original node that was split ( the original node had 3,4,5 before we changed things)
but now the root has 3 children and if we try this technique again the root->rightChildPtr will be overridden, where instead I need to traverse back up to the root, make it the child of a new root, etc. Can anyone help with the c++ code for this? my current insert mechanism is below.
I haven't even started thinking about how to code deletions yet, but advice there is helpful too.
PLEASE don't just link me to some website talking about the general theory of b-trees or 2-3 trees, as I've already looked at these and I'm still confused. Thanks