From 5a266b18633ecf9adae5e1c4e701c7e9f242c6be Mon Sep 17 00:00:00 2001
From: Stoycho Kyosev <stoycho.kk@gmail.com>
Date: Sat, 10 Dec 2022 22:57:40 +0200
Subject: add seminar09

---
 README.md                     |   3 +-
 Seminar08/tree-utils.h        |  76 +++++++++++++++++++++++++++++++++++++++++-
 Seminar09/README.md           |  12 ++++++-
 Seminar09/media/rotations.jpg | Bin 0 -> 46788 bytes
 4 files changed, 88 insertions(+), 3 deletions(-)
 create mode 100644 Seminar09/media/rotations.jpg

diff --git a/README.md b/README.md
index 836d3bd..0b95e93 100644
--- a/README.md
+++ b/README.md
@@ -6,4 +6,5 @@
 * Тема 5: Итератори. std::list. Задачи за упражнение [тук най-долу](Seminar05/README.md)
 * Тема 6: Двойно свързани списъци. Задачи върху списъци. [Упражнение - реализирайте двойно свързан списък](Seminar06/DLLSkeleton.cpp)
 * Тема 7: Сортиращи алгоритми.
-* Тема 8: Дървета. Двоични дървета. Двоични наредени дървета.
\ No newline at end of file
+* Тема 8: Дървета. Двоични дървета. Двоични наредени дървета.
+* Тема 9: Дървета 2. Балансирани дървета. Ротации. Задачи върху дървета.
\ No newline at end of file
diff --git a/Seminar08/tree-utils.h b/Seminar08/tree-utils.h
index 26c9596..ad3be90 100644
--- a/Seminar08/tree-utils.h
+++ b/Seminar08/tree-utils.h
@@ -6,7 +6,6 @@
 #include<fstream>
 
 // Важни неща:
-
 template<class T>
 struct Tree {
     T data;
@@ -25,6 +24,81 @@ void freeTree(Tree<T>* t) {
     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);
+    }
+}
+
+template<class T>
+Tree<T>* getMinRightNode(const Tree<T>* t) {
+	assert(t != nullptr);
+
+	Tree<T>* iter = t;
+
+	while (iter->left) {
+		iter = iter->left;
+	}
+	return iter;
+}
+
+template<class T>
+bool removeElement(Tree<T>*& t, const T& elem) {
+	if (t == nullptr)
+		return false;
+
+	if (t->data > elem) {
+		return removeElement(t->left, 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;
+	}
+}
+
+template<class T>
+bool containsBST(const Tree<T>* t, const T& elem) {
+	if (t == nullptr)
+		return false;
+
+	if (t->data == elem)
+		return true;
+
+	if (t->data < elem)
+		return containsBST(t->right, elem);
+
+	return containsBST(t->left, elem);
+}
+
 // Неща за мое удобство, не е нужно да ги четете:
 
 // Взето от:
diff --git a/Seminar09/README.md b/Seminar09/README.md
index c167b2e..e3404ba 100644
--- a/Seminar09/README.md
+++ b/Seminar09/README.md
@@ -76,9 +76,19 @@ int main() {
 С балансирани дървета ще се занимаваме много подробно следващия път. Засега само дефинираме неща, които ще ни бъдат от голяма полза при реализацията на едно такова дърво.
 
 ## Ротации и запазване на балансираността
+Ротацията е операция върху балансирани двоични дървета, която запазва балансираността им.
 
-Ще бъдат качени на 8ми за да имам време да систематизирам информацията. Извинявам се за забавянето!
+![](media/rotations.jpg)
 
+Ротациите обаче променят височината на лявото и дясното поддърво на корена.
+
+Нека разгледаме 1, където правим ротация около х. Височината на дясното поддърво е 1 + max(h(beta) + h(gamma)).
+
+След ротацията височината на дясното поддърво е h(gamma). Следователно височината е **намаляла поне с единица**.
+
+По същата логика височината на лявото поддърво расте отново поне с единица.
+
+Разбрахме се, че ще се стараем да си държим дърветата ниски. Тези операции ще ни бъдат полезни в тази ни задача.
 ## Задача първа
 Да се напише функция, която проверява дали дадено дърво е двоично наредено дърво.
 
diff --git a/Seminar09/media/rotations.jpg b/Seminar09/media/rotations.jpg
new file mode 100644
index 0000000..a852ab3
Binary files /dev/null and b/Seminar09/media/rotations.jpg differ
-- 
cgit v1.3.1-23-gd82d