Learn how to a build a cloud-first strategyRegister Now

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 5366

# c++ 2-3 Tree Insertion

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
0
Kibbie
• 6
• 5
1 Solution

Commented:
A 2-3 tree stores the values inside the nodes, no ? So, you'd have for your example (after inserting 1, 2, 3, 4 and 5) :

--------
| 2  4 |
--------
/     |     \
-----   -----   -----
| 1 |   | 3 |   | 5 |
-----   -----   -----

Inserting 6 would give you this :

--------
| 2  4 |
--------
/     |     \
-----   -----   ---------
| 1 |   | 3 |   | 5  6 |
-----   -----   ---------

Inserting 7 would give :

-----
| 4 |
-----
/        \
-----            -----
| 2 |            | 6 |
-----            -----
/     \           /     \
-----   -----   -----    -----
| 1 |   | 3 |   | 5 |   | 7 |
-----   -----   -----    -----

etc.

>> but now the root has 3 children

This is what happened when adding 7 in my example above. The root would have contained 2, 4 and 6, so it needed to be split up into one root node (4) and two child nodes (2 and 6).

For implementing that in C++, it's not extremely complicated, since there are a few well-defined rules that you need to implement. Just refer to any description of a 2-3 tree, and these rules should be properly described with pictures.

I just looked around a bit with Google, and found this one that clearly explains all the different rules :

http://cs.wellesley.edu/~cs230/fall02/2-3-trees.pdf

I know you asked not to post any links, but pictures mean more than a 1000 words in this case.
0

Author Commented:
The problem I'm having, however, is that your implementation is slightly different than the one I've been asked to implement.  In ours, the values are not stored in each node, but rather only in the leaf nodes.  That is, if you were to level order traverse, printing out all the leaves (which are all on the same level) you would get a lowest to highest printout.
0

Commented:
>> In ours, the values are not stored in each node, but rather only in the leaf nodes.

Ok. It's not the standard 1-2 tree then. The insertion rules also seem different. Do you have a document describing them ?
0

Commented:
2-3 tree, not 1-2 tree lol - these keys are too close together ;)
0

Author Commented:
i don't have an electronic form of the description, but i'll write here what it says:
1.There are two types of nodes in T (the tree):
a)Leaf nodes and
b)non leaf (interior) nodes

2.All data elements are stored in the leaf nodes and they must be ordered from left (min) to right (max)
3.All leaf nodes must have same depth (height)
4.Each interior onde can either be a 2-node with exactly two subtrees or a 3-node with exactly three subtrees
5.If an interior node is a 2-node, it will hold the minimum key of it' second subtree.  If an interior node is a 3-node, it will hold the minimum key of BOTH its second and third subtrees.
6.An empty tree and a tree containing a single data element in a leaf node are 2-3 trees.

node structure:  [min second, min third, parentPtr, leftChildPtr, middleChildPtr, rightChildPtr, tag (0 if nonleaf, 1 if leaf), and key].

Typical operations: find, insert, findMin, findMax, DeleteMin, DeleteMax, general delete.

the pseudocode algorithm i'm trying to implement in c++  (and in the attached files i posted originally)
is inserting item into T, with steps:

Case Analysis:
0:Create new leaf node with item x.
1:If T = NULL, return T with one node.
2.If T has one node 'y', create new interior node with children x and y
3.In general, find parent N for x insertion
a)if N is a 2-node, insert x and adjust N
b)if N is a 3-node, split N into two interior nodes (2-nodes) N1 and N2 with x inserted
i)if N was the root of T, create a new interior node, which becomes the new root o f T, having children N1 and N2
ii) If N was not the root of T, N must have a parent p(N).  Attach N1 to p(N) as a child and then insert N2 to p(N) as before.

I hope that makes sense.  What I'm having difficulty is case 3-b-ii) since that's the recursive bit.
You can see that in my c++ algorithm I posted earlier.
0

Commented:
>> (and in the attached files i posted originally)

Note that there are no attachments to your question post ... Maybe the file extensions were not supported ?

>> What I'm having difficulty is case 3-b-ii) since that's the recursive bit.

Yep, you need to apply the same algorithm to insert N2 to p(N). Note that this is as "simple" as calling the insert function recursively.
0

Author Commented:
hmm i didn't realize it wasn't attaching the .cpp file, i'll post my insert algorithm here...well, actually this willl be my whole two-three tree implementation so far
``````#include "TwoThreeTree.h"

#include <cstddef>  // definition of NULL
#include <iostream>
#include <queue> //for level order traversal

TwoThreeTree::TwoThreeTree()
{
root->parentPtr = NULL;
root->leftChildPtr = NULL;
}

TwoThreeTree::~TwoThreeTree()
{
destroyTree(root);
}

bool TwoThreeTree::isEmpty()
{
return (root->parentPtr == NULL);
}

bool TwoThreeTree::search(TwoThreeNode* tempRoot, TreeItemType item)
{
if (tempRoot->tag == 1)//leaf node is found
return (item == tempRoot->item);
else
{
TwoThreeNode* temp = tempRoot;
if (item < tempRoot->minSecond)
search(tempRoot->leftChildPtr,item);
else if (tempRoot->minThird != -1 && item >= tempRoot->minThird)
search(tempRoot->rightChildPtr, item);
else
search(tempRoot->middleChildPtr, item);
}
}

void TwoThreeTree::build(TreeItemType item)
{
TwoThreeNode* newItem = new TwoThreeNode(item); //create the new node to be inserted
root = insert(root, newItem);
}
TwoThreeNode* TwoThreeTree::insert(TwoThreeNode* temp, TwoThreeNode *newItem)
{

//the cases for 2-3 tree insertion are as follows:
//1. inserting node into initially empty tree--insert node and return
//2.inserting node into a tree with one node--create a new 2-node, make the previous node and new node it's children
//3.inserting into a tree with more than one node, in which case we have subcases.  Also, we must find the correct parent for insertion
//3a) if the parent N is a 2-node, insert newItem as the third child and set the minThird value
//3b) if the parent N is a 3-node, split N into two 2-nodes N1 & N2 and insert newItem. we have 2 subcases
//3bi)if N was root of tree (i.e. it's parent pointer is itself), create new interior node which becomes
//root of the tree, with children N1 and N2
//3bii) if N was NOT the root of the tree (N->parentPointer != NULL), attach N1 to parent of N
//and then insert N2 to parent of N as before.
//---------
//case 1
//---------
if (isEmpty())//if tree is empty
{
temp = newItem;
temp->parentPtr = temp; //root's parent is itself
}
//---------
//case 2
//---------
else if (temp->leftChildPtr == NULL) //tree is 1-node (the root)
{
TwoThreeNode * newInterior = new TwoThreeNode; //create new interior node
newInterior->tag = 0;
newInterior->parentPtr = newInterior;
if (temp->item > newItem->item) //the new item is smaller than the root's
{
newInterior->leftChildPtr = newItem;		//set left child
newInterior->leftChildPtr->parentPtr = newInterior;  //set the child's parent pointer
newInterior->middleChildPtr = temp;			//same for middle child
newInterior->middleChildPtr->parentPtr = newInterior; // ----------
}
else //root's item is less than the new item
{
newInterior->middleChildPtr = newItem;		//set middle child
newInterior->middleChildPtr->parentPtr = newInterior;  //set the child's parent pointer
newInterior->leftChildPtr = temp;			//same for left child
newInterior->leftChildPtr->parentPtr = newInterior; // ----------
}
temp = newInterior; //newInterior is the new root of the tree
temp->minSecond = findMin(temp->middleChildPtr); //set the root's second value

//tree now has 3 nodes, one interior node and the two leaves
}

else
temp = auxInsert(temp, newItem); //I made the third case a separate function because this was
//getting so huge that it was hard to read it all
return temp;  //very important! return the root
}

TwoThreeNode* TwoThreeTree::auxInsert(TwoThreeNode *temp, TwoThreeNode *newItem)
{
//---------
//case 3
//---------
//FIRST we want to figure out what interior node should be the parent
if (temp->leftChildPtr->tag == 0)  //if this is true temp is not the parent
{
if (newItem->item < temp->minSecond) //temp is smaller than the minSecond
temp = insert(temp->leftChildPtr, newItem);
else if (temp->rightChildPtr == NULL) //temp only has 2 children
temp->middleChildPtr = insert(temp->middleChildPtr, newItem);
else //temp has 3 children
{
if (newItem->item > temp->minSecond && newItem->item < temp->minThird) //also insert in middle
temp = insert(temp->middleChildPtr, newItem);
else //insert in right
temp = insert(temp->rightChildPtr, newItem);
}
return temp;
}
//---------
//case 3a)
//---------
if (temp->rightChildPtr == NULL) //attach as third
{
if (temp->minSecond < newItem->item) //the new item is bigger than the middle's item
{
temp->rightChildPtr = newItem;
temp->rightChildPtr->parentPtr = temp;

}
else
{
temp->rightChildPtr = temp->middleChildPtr; //make middle the new right (i.e. shifting it over)
if (newItem->item > temp->leftChildPtr->item)
{
temp->middleChildPtr = newItem;
temp->middleChildPtr->parentPtr = temp;
}
else
{
//shift the left over as we did with the middle
temp->middleChildPtr = temp->leftChildPtr;
temp->leftChildPtr = newItem;
newItem->parentPtr = temp;
}
}

//set the minSecond of the parent and minThird
temp->minSecond = findMin(temp->middleChildPtr);
temp->minThird = findMin(temp->rightChildPtr);
}
//---------
//case 3b)
//---------
else
//first we have to break apart N into N1 and N2, and insert newItem appropriately
//to figure out whether newItem belongs in N1 or N2, we have to check it's value
//against the value of the middle child
{
TwoThreeNode* temp2 = new TwoThreeNode;
temp2->tag = 0; //interior node

if (newItem->item < temp->middleChildPtr->item)
{
//it belongs in N1 so we must move N1->middleChild and rightChild to N2
temp2->leftChildPtr = temp->middleChildPtr;
temp2->leftChildPtr->parentPtr = temp2;
temp2->middleChildPtr = temp->rightChildPtr;
temp2->middleChildPtr->parentPtr = temp2;

if (temp->leftChildPtr->item > newItem->item) //the new item is smaller
{
//swap the left child and middle child to maintain lowest to highest order
TwoThreeNode* swapper = temp->leftChildPtr;
temp->middleChildPtr = swapper;
temp->leftChildPtr = newItem;
temp->leftChildPtr->parentPtr = temp; //setting parent pointer appropriately

}
else
{
temp->middleChildPtr = newItem;
temp->middleChildPtr->parentPtr = temp;
}
}
//making it to this else means that newItem is larger than the middle item, so it belongs in N2
else
{
if (temp->rightChildPtr->item > newItem->item) //new item is smaller than the current max
{
temp2->leftChildPtr = newItem;
temp2->leftChildPtr->parentPtr = temp2; //setting parent pointer, this should be clear by now
temp2->middleChildPtr = temp->rightChildPtr;
temp2->middleChildPtr->parentPtr = temp2;
}
//if this fails, new item is bigger than current max
else
{
temp2->leftChildPtr = temp->rightChildPtr;
temp2->leftChildPtr->parentPtr = temp2;
temp2->middleChildPtr = newItem;
temp2->middleChildPtr->parentPtr = temp2;
}
}

//don't forget to set the orginal temp's right child pointer to null!
temp->rightChildPtr = NULL;
temp->minSecond = findMin(temp->middleChildPtr);
temp->minThird = -1; //resetting temp's minThird
temp2->minSecond = findMin(temp2->middleChildPtr);

//-----------------------------------------------------------------------------------
//now that we've created (and set) N1 and N2, we get on with the real purpose of 3b
//-----------------------------------------------------------------------------------
//---------
//case 3bi)
//---------
if (temp->parentPtr == temp)  //temp is the root!
{
TwoThreeNode* newInterior = new TwoThreeNode;
newInterior->tag = 0; //0 means it is an interior node
newInterior->parentPtr = newInterior;
newInterior->leftChildPtr = temp;
newInterior->leftChildPtr->parentPtr = newInterior;
newInterior->middleChildPtr = temp2;
newInterior->middleChildPtr->parentPtr = newInterior;

//we have been returning temp in the other cases, so set temp to newInterior
temp = newInterior;
}
//---------
//case 3bii)
//---------
else
{
//here's the recursive bit
//temp = insert (temp->parentPtr, temp2);
temp->parentPtr->rightChildPtr = temp2;
return temp;
}
}
temp->minSecond = findMin(temp->middleChildPtr);
return temp;
}

TreeItemType TwoThreeTree::findMin(TwoThreeNode *temp) //find the minimum by following leftchildPtr
{
if (temp->leftChildPtr != NULL)
return findMin(temp->leftChildPtr);
return temp->item;
}

void TwoThreeTree::levelOrderTrav()
{
levelOrderTraversal(root);
}
void TwoThreeTree::levelOrderTraversal(TwoThreeNode* temp)
{
if (temp->leftChildPtr != NULL)
levelOrderTraversal(temp->leftChildPtr);
if (temp->middleChildPtr != NULL)
levelOrderTraversal (temp->middleChildPtr);
if (temp->rightChildPtr != NULL)
levelOrderTraversal(temp->rightChildPtr);
cout<<temp->item<<' '; //output the item
}

TwoThreeNode* TwoThreeTree::getRoot()
{
return root;
}

void TwoThreeTree::deleteMaximum()
{
}

void TwoThreeTree::deleteMinimum()
{
}

void TwoThreeTree::deleteItem(TwoThreeNode *item)
{
}

void TwoThreeTree::destroyTree(TwoThreeNode *& treePtr)

{
// postorder traversal
if (treePtr != NULL)
{
destroyTree(treePtr->leftChildPtr);
destroyTree(treePtr->middleChildPtr);
destroyTree(treePtr->rightChildPtr);
delete treePtr;
treePtr = NULL;
}  // end if

}  // end destroyTree

and HERE is the actual node, if that helps too

/*
* TwoThreeNode.cpp
*
*  Created on: Apr 21, 2009
*      Author: DKNS
*/

#include "TwoThreeNode.h"

TwoThreeNode::TwoThreeNode()
{
parentPtr = NULL;
leftChildPtr = NULL;
rightChildPtr = NULL;
middleChildPtr = NULL;
tag = 1;
minSecond = -1;
minThird = -1;

}
``````
0

Commented:
A few remarks :

1) Your TwoThreeTree::search function searches recursivley, which is ok. But you don't handle the return value of the recursive calls, so the calling code will have no way to know whether the item was found or not ...

2) Your TwoThreeTree::levelOrderTraversal prints the item, irrespective of whether the current node is a leaf node or not ...

And then about the insert functionality :

1) You say "//root's parent is itself" - why is that ? The root doesn't have a parent, right ? So, its parent pointer should be NULL probably.

2) You probably want to use >= for the first comparison here (at the start of TwoThreeTree::auxInsert) :

>>                   if (newItem->item > temp->minSecond && newItem->item < temp->minThird) //also insert in middle

3) And your case 3bii needs a bit more work. It should be as simple as calling the insert function recursively (like in the part you commented). BUT there's a big BUT ... Your current code assumes that inserts happen in parents of leaf nodes, and that the node that is inserted is always a leaf node ... For this recursive insert, you need to be able to insert non-leaf nodes into any node in the tree. You'll need to re-work part part of your code to support this, OR you need to add one more function that handles this special case.

I'm not sure I caught everything, but at least these should get you a step closer.
0

Author Commented:
That's very true, and I took your tips to heart in correcting the search functions, and the >=.  As far as the root ptr pointing to itself that was just how our prof wanted it to be, for better or worse (as it doesn't really matter either way i suppose).  Do you have any idea how to modfiy the insert to work with nonleaf nodes?  that's really where I'm stuck.
0

Commented:
>> Do you have any idea how to modfiy the insert to work with nonleaf nodes?  that's really where I'm stuck.

Consider a leaf node as just another sub-tree, and instead of inserting leaf nodes, modify your code to insert sub-trees. That should be enough to make it generic.
Note that, when moving up into the tree, trying to insert N2, all you have to repeat is step 3). You found the parent P for inserting N2, and then you have two cases : either P is a 2-node, and you can simply insert N2 in it, or it's a 3-node, and you have to split P into P1 and P2, etc. It's exactly the same as the normal step 3), except that you're inserting a sub-tree, rather than a leaf node.

It's a pity that your prof is not using the standard 2-3 tree, as the operations on that are a bit more straightforward, and account for this specific case a bit better.
0

Author Commented:
Thanks for the advice, hopefully after modifying it all this will work better.
0

## Featured Post

• 6
• 5
Tackle projects and never again get stuck behind a technical roadblock.