Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar09
diff options
context:
space:
mode:
Commit46a31d1c2bfeca7429df19a5e989a52b665b0bb3 (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-04 18:01:53 +0200
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-04 18:01:53 +0200
Files84c78178afbc28d74edaf0918cfb3c3fb273e23a /Seminar09
Data-structures-and-algorithms-46a31d1c2bfeca7429df19a5e989a52b665b0bb3.tar
Data-structures-and-algorithms-46a31d1c2bfeca7429df19a5e989a52b665b0bb3.tar.gz
Data-structures-and-algorithms-46a31d1c2bfeca7429df19a5e989a52b665b0bb3.zip
Parent63f4cb943f81c257e78ebeef828edbc04e78264b (diff)
Parent76904781d28d13e321c48827680bdb0d7c039bd9 (diff)
pls no more merge conficts
1 files changed, 8 insertions, 4 deletions
-rw-r--r--Seminar09/README.md12
diff --git a/Seminar09/README.md b/Seminar09/README.md
index 92a4fdb..617232d 100644
--- a/Seminar09/README.md
+++ b/Seminar09/README.md
@@ -20,7 +20,7 @@ T maxElem(const Tree<T>* t) {
Това решение работи почти винаги. Какво става ако t e nullptr?
Ако знаехме, че дървото е от тип int, лесно можехме да връщаме INT_MAX, но в случая не знаем какъв тип е скрит зад Т.
-Един от начините да се справим с този проблем е да връщаме T* вместо Т. Така, ако дървото е nullptr ние също ще връщаме nullptr. Това е валиден начин, и може би стандартния начин по който бихме подходили в С или във версиите на С++ преди С++17.
+Един от начините да се справим с този проблем е да връщаме T\* вместо Т. Така, ако дървото е nullptr ние също ще връщаме nullptr. Това е валиден начин, и може би стандартния начин по който бихме подходили в С или във версиите на С++ преди С++17.
## std::optional\<T>
std::optional\<T> е клас който в някакъв смисъл "обвива" елемент от тип Т. Както името подсказва той или има стойност.. или няма.
@@ -71,7 +71,7 @@ int main() {
Също така дърво ще наричаме **идеално балансирано** ако за всеки негов възел броя на възлите в лявото поддърво и броя на възлите в дясното поддърво се различават най - много с единица.
-В балансираните и идеално балансираните дървета сложността на операциите добавяне, търсене, изтриване стават O(log<sub>2</sub>(n)).
+В балансираните и идеално балансираните дървета сложността на операциите добавяне, търсене, изтриване стават $\mathcal{O} (\log_2 n)$.
С балансирани дървета ще се занимаваме много подробно следващия път. Засега само дефинираме неща, които ще ни бъдат от голяма полза при реализацията на едно такова дърво.
@@ -105,11 +105,15 @@ int main() {
Да се реализират ляво и дясна ротация за произволно дърво.
## Задача шеста (За домашно)
-Нека имаме двоично наредено дърво T от цели числа.
+Нека имаме двоично наредено дърво T от цели числа.
+
+```
pred(x) = max{y | y е ключ на възел в Т и y < x} // Предшественик
succ(x) = min{y | y е ключ на възел в T и y > x} // Наследник
+```
+
Да се реализира pred(t, x) и succ(t, x).
Бележка: Не е нужно х да се съдържа в дървото.
## Задача седма (Контролно)
-Да се напише функция, която намира сумата на всички елементи на двоично наредено дърво от цели числа, които имат нечетен брой наследници в интервала [x, y] (т.е. сумата на броя елементи в лявото поддърво и броя елементи в дясното поддърво в интервала [x, y] е нечетно число). Нека x и y са параметри на функцията. \ No newline at end of file
+Да се напише функция, която намира сумата на всички елементи на двоично наредено дърво от цели числа, които имат нечетен брой наследници в интервала [x, y] (т.е. сумата на броя елементи в лявото поддърво и броя елементи в дясното поддърво в интервала [x, y] е нечетно число). Нека x и y са параметри на функцията.