BTree Confusion

[pinsickle]

class BTreeNode : public LinkedNode
{
	public:
		BTreeNode
			(BTreeNode* child0, int key0, BTreeNode* child1);
		
		BTreeNode
			(const BTreeNode& sibling);

		bool isNotLeaf
			(void) const;

		BTreeNode* findChild
			(int newKey) const;

		BTreeNode* addKey
			(int newKey, BTreeNode* newChild = 0);

		BTreeNode* getChild
			(int i) const;

		void write
			(ostream& outfile) const;

	private:
		void setChild
			(int i, BTreeNode* child);

		BTreeNode* getParent
			(void) const;

		void setParent
			(BTreeNode* newParent);

	private:
		int keyCount;
		int keys [5]; // 5th used for split
};

ostream& operator << (ostream& outfile, const BTreeNode& node);

BTreeNode::BTreeNode (BTreeNode* child0, int key0, BTreeNode* child1)
{
	parent = 0;
	keyCount = 1;
	keys[0] = key0;
	children[0] = child0; // 0 for original root
	children[1] = child1; // 0 for original root
	for (int i = 1; i <= 3; i++) // is this loop necessary?
	{
		// key i = +INFINITY;
		// child i+1 = 0;
	}

	for (i = 0; i <= 1; i++)
	{
		if // (child i != 0) // true for new roots
			// child i's parent = this;
	}
}

My professor has me confused with this constructor. Is children [] and parent suppose to be part of the keys array or is it private data for BTreeNode that he forgot to include in the .h file??

Thanks for the help.

[mitrmkar]

Perhaps you should consult your professor?

[pinsickle]

Perhaps you should consult your professor?

That is the problem, if brought up in class he basically says that we don't have time to discuss it as we are behind and to email him. Virtually everyone in class has talked and/or emailed him to no avail.

Here is what I have so far :

class BTreeNode : public LinkedNode
{
	public:
		BTreeNode
			(BTreeNode* child0, int key0, BTreeNode* child1);
		
		BTreeNode
			(const BTreeNode& sibling);

		bool isNotLeaf
			(void) const;

		BTreeNode* findChild
			(int newKey) const;

		BTreeNode* addKey
			(int newKey, BTreeNode* newChild = 0);

		BTreeNode* getChild
			(int i) const;

		void write
			(ostream& outfile) const;
			
		int getKey (int number = 0) const;

	private:
		void setChild
			(int i, BTreeNode* child);

		BTreeNode* getParent
			(void) const;

		void setParent
			(BTreeNode* newParent);

	private:
		int keyCount;
		int keys [5]; // 5th used for split
};

ostream& operator << (ostream& outfile, const BTreeNode& node);

BTreeNode::BTreeNode (BTreeNode* child0, int key0, BTreeNode* child1): LinkedNode (7)
{
	setParent(0);
	keyCount = 1;
	keys[0] = key0;
 	setChild (1, child0);// 0 for original root
	setChild (2, child1);
	
	for (int i = 1; i <= 3; i++) // is this loop necessary?
	{
		keys [i] = 999999; // key i = +INFINITY;
		setChild (i+1, 0); // child i+1 = 0;
	}

	for (int i = 0; i <= 1; i++)
	{
		if  (getChild(i) != 0) // true for new roots
		{
			getChild(i) -> setParent (this);
		}
	}
}

BTreeNode::BTreeNode (const BTreeNode& sibling): LinkedNode (7)
{
	setParent (sibling.getParent());
	keyCount = 2;
	keys[0] = sibling.getKey (3);
	keys[1] = sibling.getKey (4);
	
	for (int i = 1; i < 4; i++)// children 0, 1 & 2 <= sibling children 3, 4 & 5
	{
		setChild(i, sibling.getChild(i + 3));
	}
	keys[2] = keys[3] = 999999;// keys 2 & 3 <= large values (for comparisons)
	setChild (4, 0);
	setChild (5, 0);// children 3 & 4 <= zero (null pointers)

	for (int i = 1; i < 4; i++)// parents of children 0, 1 & 2 are all this node
		getChild (i) -> setParent (this);

}

BTreeNode* BTreeNode::addKey (int newKey, BTreeNode* newChild /* = 0 */)
{
  int i = 3;// start i at key 3, last of keys[0], [1], [2], & [3]

  while (i >= 0 && keys[i] > newKey)
	{	
		BTreeNode* temp = getChild (i + 1);
		keys[i + 1] = keys[i]; // move key i to the right
		setChild(i + 2, temp);// move child i+1 to the right
		i--;
	}

	keys[i + 1] = newKey;// insert new key & child ptr in key i+1 & child i+2
	setChild (i+2, newChild);
	keyCount++;
	BTreeNode* newRoot = 0; // assume no split of old root

	if (keyCount > 4) // full node => split
	{
		int splitKey = keys[2]; // keys [3] & [4] go to new node
		BTreeNode* sibling = new BTreeNode (*this);
		keyCount = 2; // only keys[0] & [1] will stay
		for(int i = 2; i < 5; i++)// reset keys 2, 3 & 4 to large values (for comparisons)
		{
			keys[i] = 999999;// reset children 3, 4 & 5 to zero
			setChild (i+1, 0);
		}
		
		if (getParent() != 0) // level exists above
		{	
			newRoot = getParent()->addKey (splitKey, sibling);
		}
		else // were at root, so add a new higher level
		{
			newRoot = new BTreeNode (this, splitKey, sibling);
		}
	}
	return newRoot;
}

void BTreeNode::write (ostream& outfile) const
{
	outfile << "#Keys = " << keyCount << "; ";// display key count
	if (getParent() != 0)// display 1st (key) of parent
	{
		outfile << "parent (" << getParent() -> getKey(0) << ") ";
	}
	else
	{
		outfile << "parent (----) ";
	}
	for (int i = 0; i < keyCount; i++)
	{
		if (getChild(i + 1) != 0)// display 1st <key> of child i
		{
			outfile << "<" << getChild(i + 1) -> getKey(i) << "> "; 
		}
		else 
		{
			outfile << "<-----> "; 
		}
		outfile << keys[i] << " ";// display keys[i]
	}
	if (getChild (keyCount - 1) !=0)// display 1st <key> of last child
	{
		outfile << "<" << getChild (keyCount - 1) -> getKey (keyCount - 1) << ">\n";
	}
	return;
}

void BTreeNode::setChild (int i, BTreeNode* child)
{
	setLink (i, child);
	return;
}

BTreeNode* BTreeNode::getChild (int i) const
{
	return static_cast <BTreeNode*> (getLink(i));
}

bool BTreeNode::isNotLeaf (void) const
{
	return  getChild(1) != 0;
}

		
BTreeNode* BTreeNode::findChild (int newKey) const
{
	int i = 0;
	while (newKey >= keys[i] && i < 4)
	{
		i++;
	}
	return getChild(i);
}

BTreeNode* BTreeNode::getParent (void) const
{
	return static_cast <BTreeNode*>(getLink (0));
}

void BTreeNode::setParent (BTreeNode* newParent)
{
	setLink (0, newParent);
}

int BTreeNode::getKey (int number) const
{
	return keys[number];
}

ostream& operator << (ostream& outfile, const BTreeNode& node)
{
	node.write(outfile);
	return outfile;
}

I'm getting an out of bounds error (in the children array) that i need to trace but other than that does this look close?

Note** 1. I haven't hit the tree class just have been testing nodes works fine unit nodes are full and it is time to "split" that is when I crash.

2. All comments in the file were include by my professor

3. The way I interpreted his take on setting up LinkedNode pointer array is suppose to be set up such that LinkedNode[0] is the parent and LinkedNode[1] through LinkedNode[6] are the children.
Thanks for any help