diff options
pls no more merge conficts
1 files changed, 8 insertions, 4 deletions
| -rw-r--r-- | Seminar09/README.md | 12 |
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 са параметри на функцията. |
