Improved remove()

remove() now reinserts subtree of delted element 'as is' instead of
creating a list and reinserting it

4 files changed, 65 insertions, 23 deletions

diff --git a/tree/src/cNode.cpp b/tree/src/cNode.cpp
index 8618354..8e001c4 100644
--- a/tree/src/cNode.cpp
+++ b/tree/src/cNode.cpp
@@ -42,20 +42,29 @@ void cDatanode::insert(cData* _data, cNode** _me)
 		nextSmaller->insert(_data, &nextSmaller);
 }//insert
 
-void cDatanode::remove(cData* _data, list<cData>* _list, cNode** _me)
+void cDatanode::insert(cNode* _data, cNode** _me)
+{
+	if (_data->getDataObject() > *data)
+		nextBigger->insert(_data, &nextBigger);
+	else if (_data->getDataObject() == *data)
+		return;
+	else
+		nextSmaller->insert(_data, &nextSmaller);
+}
+
+void cDatanode::remove(cData* _data, sSubTree* _subtree, cNode** _me)
 {
 	if(*_data == *data)
 	{
 		//save subtree inorder before deleting
-		nextSmaller->getSortet(_list);
-		nextBigger->getSortet(_list);
+		*_subtree = getSubTree();
 		*_me = new cEndnode(); //set pointer to this in parent to new cEndnode
 		delete this;
 	}
 	else if (*_data > *data)
-		nextBigger->remove(_data, _list, &nextBigger);
+		nextBigger->remove(_data, _subtree, &nextBigger);
 	else if (*_data < *data)
-		nextSmaller->remove(_data, _list, &nextSmaller);
+		nextSmaller->remove(_data, _subtree, &nextSmaller);
 }//remove
 
 cData* cDatanode::search(string _search)
@@ -129,6 +138,11 @@ sSubTree cDatanode::getSubTree()
 	return s;
 }
 
+cNode *cDatanode::getFirstNode(cNode** _me)
+{
+	return nextSmaller->getFirstNode(&nextSmaller);
+}
+
 //
 //==============================================================================================================================
 //
@@ -147,7 +161,13 @@ void cEndnode::insert(cData* _data, cNode** _me)
 	delete this;
 }
 
-void cEndnode::remove(cData*, list<cData>*, cNode**)
+void cEndnode::insert(cNode* _data, cNode** _me)
+{
+	*_me = _data;
+	delete this;
+}
+
+void cEndnode::remove(cData*, sSubTree*, cNode**)
 {
 	return;
 }
@@ -190,7 +210,11 @@ sSubTree cEndnode::getSubTree()
 	return sSubTree{NULL, NULL};
 }
 
-
+cNode *cEndnode::getFirstNode(cNode** _me){
+	cNode* tmp = *_me;
+	*_me = new cEndnode();
+	return tmp;
+}
 
 
 
diff --git a/tree/src/cNode.h b/tree/src/cNode.h
index 9918bf0..c39dc60 100644
--- a/tree/src/cNode.h
+++ b/tree/src/cNode.h
@@ -31,23 +31,27 @@ public:
 	/*
 	 * returns dataObject
 	 */
-	virtual void insert(cData*,  cNode** = NULL) = 0;
+	virtual void insert(cData* _data,  cNode** _me) = 0;
 	/*
 	 * Inserts *cData into tree
 	 * cNode** required to change pointer in the caller's pointer to next element
 	 */
-	virtual void remove(cData*, list<cData>*, cNode**) = 0;
+	virtual void insert(cNode* _data, cNode** _me) = 0;
 	/*
-	 * Removes *cData from tree. Its subtree is stored in list<cData>*. cNode** refers to pointer to pointer to self to be able to change reference
+	 * Overloading Function to be able to insert complete subtrees
 	 */
-	virtual cData* search(string) = 0;
+	virtual void remove(cData* _data, sSubTree* _subtree, cNode** _me) = 0;
+	/*
+	 * Removes *cData from tree. Its subtree is stored in sSubTree*. cNode** refers to pointer to pointer to self to be able to change reference
+	 */
+	virtual cData* search(string _data) = 0;
 	/*
 	 * Searches for a Object by its Primary Key, returns pointer pointing at result (NULL if no result)
 	 */
-	virtual cData* getById(unsigned int, unsigned int&) = 0;
+	virtual cData* getById(unsigned int _id, unsigned int& _cntr) = 0;
 	/*
 	 * searches for obejct ID (-> inorder)
-	 * int: wanted if
+	 * int: wanted id
 	 * int&: id counter
 	 */
 	virtual void getSortet(list<cData>* _list) = 0;
@@ -58,17 +62,23 @@ public:
 	/*
 	 * returns size of subtree
 	 */
-	virtual unsigned int getDepth(unsigned int) = 0;
+	virtual unsigned int getDepth(unsigned int _deppth) = 0;
 	/*
 	 * returns maximum depth under node
 	 * unsigned int: depth of parent
 	 */
 	virtual void draw(int _depth) = 0;
 	/*
-	 *draws tree in Ascii
+	 *draws tree in ASCII
 	 */
-
 	virtual sSubTree getSubTree() = 0;
+	/*
+	 * Returns subtree of this Node, nextSmaller and nextBigger are set to new Endnodes
+	 */
+	virtual cNode *getFirstNode(cNode** _me) = 0;
+	/*
+	 * Returns Pointer to Inorder-First element in Tree
+	 */
 };
 
 class cDatanode:public cNode
@@ -81,11 +91,12 @@ public:
 	/*
 	 * returns dataObject
 	 */
-	void insert(cData*, cNode** = NULL);
+	void insert(cData*, cNode**);
 	/*
 	 * Inserts *cData into tree
 	 */
-	void remove(cData*, list<cData>*, cNode**);
+	void insert(cNode*, cNode**);
+	void remove(cData*, sSubTree*, cNode**);
 	/*
 	 * Removes *cData from tree
 	 */
@@ -103,6 +114,7 @@ public:
 	unsigned int getSubtreeSize();
 	unsigned int getDepth(unsigned int);
 	sSubTree getSubTree();
+	cNode *getFirstNode(cNode**);
 private:
 	cNode *nextSmaller, *nextBigger;
 	cData *data;
@@ -124,7 +136,8 @@ public:
 	/*
 	 * Inserts *cData into tree
 	 */
-	void remove(cData*, list<cData>*, cNode**);
+	void insert(cNode*, cNode**);
+	void remove(cData*, sSubTree*, cNode**);
 	/*
 	 * Removes *cData from tree
 	 */
@@ -143,6 +156,8 @@ public:
 	void draw(int _depth);
 
 	sSubTree getSubTree();
+
+	cNode *getFirstNode(cNode**);
 private:
 };
 
diff --git a/tree/src/cTree.cpp b/tree/src/cTree.cpp
index 943819c..6a871dd 100644
--- a/tree/src/cTree.cpp
+++ b/tree/src/cTree.cpp
@@ -30,10 +30,13 @@ void cTree::insert(string _data)
 
 void cTree::remove(cData* _data)
 {
-	list<cData> dataList; //List of Data that has to be re-inserted into the tree
-	root->remove(_data, &dataList, &root);
+	sSubTree subTree;
+	root->remove(_data, &subTree, &root);
 
-	insertList(&dataList);
+	root->insert(subTree.nextSmaller->getFirstNode(&root), &root); //Insert new root
+	//Insert remaining subtree
+	root->insert(subTree.nextSmaller, &root);
+	root->insert(subTree.nextBigger, &root);
 }//remove
 
 void cTree::getList(list<cData>* _list)
diff --git a/tree/src/main.cpp b/tree/src/main.cpp
index 658f4be..b5db0c5 100644
--- a/tree/src/main.cpp
+++ b/tree/src/main.cpp
@@ -123,7 +123,7 @@ void stress(void)
 	{
 		fill();
 		a->sort();
-		for(int i = 0; i < a->size(); i++)
+		for(unsigned int i = 0; i < a->size(); i++)
 		{
 			a->remove((*a)[i]);
 		}