From 6282b54e59ac2651b682ce2c548ed8024ac92480 Mon Sep 17 00:00:00 2001 From: jonas Date: Mon, 6 Mar 2017 09:26:15 +0100 Subject: Improved remove() remove() now reinserts subtree of delted element 'as is' instead of creating a list and reinserting it --- tree/src/cNode.cpp | 38 +++++++++++++++++++++++++++++++------- tree/src/cNode.h | 39 +++++++++++++++++++++++++++------------ tree/src/cTree.cpp | 9 ++++++--- tree/src/main.cpp | 2 +- 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* _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*, 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*, cNode**) = 0; + virtual void insert(cNode* _data, cNode** _me) = 0; /* - * Removes *cData from tree. Its subtree is stored in list*. 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* _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*, 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*, 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 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* _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]); } -- cgit v1.2.3