Update tree utils

1 files changed, 125 insertions, 53 deletions

diff --git a/Seminar08/tree-utils.h b/Seminar08/tree-utils.h
index ad3be90..531aa9d 100644
--- a/Seminar08/tree-utils.h
+++ b/Seminar08/tree-utils.h
@@ -4,45 +4,46 @@
 #include<iostream>
 #include<string>
 #include<fstream>
+#include<assert.h>
 
 // Важни неща:
 template<class T>
 struct Tree {
-    T data;
-    Tree* left;
-    Tree* right;
+	T data;
+	Tree* left;
+	Tree* right;
 
-    Tree(T data, Tree<T>* l = nullptr, Tree<T>* r = nullptr) : data {data}, left {l}, right {r} {}
+	Tree(T data, Tree<T>* l = nullptr, Tree<T>* r = nullptr) : data{ data }, left{ l }, right{ r } {}
 };
 
 template<class T>
 void freeTree(Tree<T>* t) {
-    if(t == nullptr)
-        return;
-    freeTree(t->left);
-    freeTree(t->right);
-    delete t;
+	if (t == nullptr)
+		return;
+	freeTree(t->left);
+	freeTree(t->right);
+	delete t;
 }
 
 template<class T>
-void insertInBST(Tree<T>*& t, const T& elem) {
-    if (t == nullptr) {
-        t = new Tree<T>(elem);
-        return;
-    }
-    else if (t->data < elem) {
-        insertInBST(t->right, elem);
-    }
-    else {
-        insertInBST(t->left, elem);
-    }
+void insertInBST(Tree<T>*& t, const T& elem, bool hasDuplicates = true) {
+	if (t == nullptr) {
+		t = new Tree<T>(elem);
+		return;
+	}
+	else if (t->data < elem) {
+		insertInBST(t->right, elem, hasDuplicates);
+	}
+	else if ((t->data > elem) || hasDuplicates) {
+		insertInBST(t->left, elem, hasDuplicates);
+	}
 }
 
 template<class T>
-Tree<T>* getMinRightNode(const Tree<T>* t) {
+const Tree<T>* getMinNode(const Tree<T>* t) {
 	assert(t != nullptr);
 
-	Tree<T>* iter = t;
+	const Tree<T>* iter = t;
 
 	while (iter->left) {
 		iter = iter->left;
@@ -61,28 +62,28 @@ bool removeElement(Tree<T>*& t, const T& elem) {
 	else if (t->data < elem) {
 		return removeElement(t->right, elem);
 	}
-	else {																// Намерили сме елемента
-		if (!t->left && !t->right) {									// Листо
-			delete t;
-			t = nullptr; //!!
-		}
-		else if (!t->left && t->right) {								// Има само дясно поддърво
-			Tree<T>* toDelete = t;
-			t = t->right;
-			delete toDelete;
-		}
-		else if (t->left && !t->right) {								// Има само ляво поддърво
-			Tree<T>* toDelete = t;
-			t = t->left;
-			delete toDelete;
-		}
-		else {															// Вътрешен връх. 
-			T newData = getMinRightNode(t->right)->data;
-			t->data = newData;
-			removeElement(t->right, newData);
-		}
-		return true;
+
+	// Намерили сме елемента
+	if (!t->left && !t->right) {									// Листо
+		delete t;
+		t = nullptr; // !!
+	}
+	else if (!t->left && t->right) {								// Има само дясно поддърво
+		Tree<T>* toDelete = t;
+		t = t->right;
+		delete toDelete;
+	}
+	else if (t->left && !t->right) {								// Има само ляво поддърво
+		Tree<T>* toDelete = t;
+		t = t->left;
+		delete toDelete;
+	}
+	else {															// Вътрешен връх. 
+		T newData = getMinNode(t->right)->data;
+		t->data = newData;
+		removeElement(t->right, newData);
 	}
+	return true;
 }
 
 template<class T>
@@ -99,27 +100,98 @@ bool containsBST(const Tree<T>* t, const T& elem) {
 	return containsBST(t->left, elem);
 }
 
+
+// За по - любопитните премахване на възел
+// само с пренасочване на указатели и без копие на T
+template<class T>
+void innerVertexRemoveCase(Tree<T>*& inVertex) {
+	assert(inVertex && inVertex->left && inVertex->right);
+
+	Tree<T>** minNode = &inVertex->right;
+	Tree<T>** minNodeParent = &inVertex;
+
+	bool firstGoingDown = true;
+
+	while ((*minNode)->left) {
+		minNode = &(*minNode)->left;
+
+		minNodeParent = firstGoingDown ? &(*minNodeParent)->right : &(*minNodeParent)->left;
+
+		firstGoingDown = false;
+	}
+
+	bool isLeaf = ((*minNode)->right == nullptr);
+	Tree<T>* originalRight = (*minNode)->right;
+
+	(*minNode)->left = inVertex->left;
+
+	if (!firstGoingDown)
+		(*minNode)->right = inVertex->right;
+
+	Tree<T>* toDelete = inVertex;
+
+	inVertex = (*minNode);
+
+	if (!firstGoingDown)
+		(*minNodeParent)->left = isLeaf ? nullptr : originalRight;
+
+	delete toDelete;
+}
+
+template<class T>
+bool removeElementPointerSwap(Tree<T>*& t, const T& elem) {
+	if (t == nullptr)
+		return false;
+
+	if (t->data > elem) {
+		return removeElementPointerSwap(t->left, elem);
+	}
+	else if (t->data < elem) {
+		return removeElementPointerSwap(t->right, elem);
+	}
+
+	// Намерили сме елемента
+	if (!t->left && !t->right) {									// Листо
+		delete t;
+		t = nullptr;
+	}
+	else if (!t->left && t->right) {								// Има само дясно поддърво
+		Tree<T>* toDelete = t;
+		t = t->right;
+		delete toDelete;
+	}
+	else if (t->left && !t->right) {								// Има само ляво поддърво
+		Tree<T>* toDelete = t;
+		t = t->left;
+		delete toDelete;
+	}
+	else {															// Вътрешен връх. 
+		innerVertexRemoveCase(t);
+	}
+	return true;
+}
+
 // Неща за мое удобство, не е нужно да ги четете:
 
 // Взето от:
 // https://stackoverflow.com/questions/36802354/print-binary-tree-in-a-pretty-way-using-c
 template<class T>
 void printBT(const std::string& prefix, const Tree<T>* node, bool isLeft) {
-    if(node != nullptr) {
-        std::cout << prefix;
+	if (node != nullptr) {
+		std::cout << prefix;
 
-        std::cout << (isLeft ? "|--" : "`--" );
+		std::cout << (isLeft ? "|--" : "`--");
 
-        std::cout << node->data << std::endl;
+		std::cout << node->data << std::endl;
 
-        printBT( prefix + (isLeft ? "|   " : "    "), node->left, true);
-        printBT( prefix + (isLeft ? "|   " : "    "), node->right, false);
-    }
+		printBT(prefix + (isLeft ? "|   " : "    "), node->left, true);
+		printBT(prefix + (isLeft ? "|   " : "    "), node->right, false);
+	}
 }
 
 template<class T>
 void printTree(const Tree<T>* node) {
-    printBT("", node, false);    
+	printBT("", node, false);
 }
 
 // Следващите две функции са малко по - красив начин да изпринтим дърво, но го конвертира къмм LaTeX документ
@@ -129,7 +201,7 @@ void printTree(const Tree<T>* node) {
 // Не е перфектно но пък е по - удобно от конзолата. Това е за демонстрации, не е нужно да го учите или разбирате.
 template<class T>
 void recFillFileStream(std::ofstream& outFile, const Tree<T>* r) {
-	if(r == nullptr)
+	if (r == nullptr)
 		return;
 
 	outFile << "[" << r->data << " ";
@@ -153,7 +225,7 @@ void exportToTex(const Tree<T>* root, const char* filePath) {
 	outFile << "\\end{forest}";
 	outFile << "\\end{document}";
 
-    outFile.close();
+	outFile.close();
 }
 
 #endif
\ No newline at end of file