Learn how to a build a cloud-first strategyRegister Now

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

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
Asked:
Kibbie
  • 6
  • 5
1 Solution
 
Infinity08Commented:
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
 
KibbieAuthor 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
 
Infinity08Commented:
>> 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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
Infinity08Commented:
2-3 tree, not 1-2 tree lol - these keys are too close together ;)
0
 
KibbieAuthor 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
Adjust N1 and N2
       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
 
Infinity08Commented:
>> (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
 
KibbieAuthor 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 <new>      // for bad_alloc
#include "BST.h"      // header file
#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;
		//adjusting the minSecond values
		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;
 
}

Open in new window

0
 
Infinity08Commented:
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
 
KibbieAuthor 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
 
Infinity08Commented:
>> 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
 
KibbieAuthor Commented:
Thanks for the advice, hopefully after modifying it all this will work better.
0

Featured Post

Get your Disaster Recovery as a Service basics

Disaster Recovery as a Service is one go-to solution that revolutionizes DR planning. Implementing DRaaS could be an efficient process, easily accessible to non-DR experts. Learn about monitoring, testing, executing failovers and failbacks to ensure a "healthy" DR environment.

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