diff options
add seminar09
2 files changed, 11 insertions, 1 deletions
| -rw-r--r-- | Seminar09/README.md | 12 | ||||
| -rw-r--r-- | Seminar09/media/rotations.jpg | bin | 0 -> 46788 bytes |
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ми за да имам време да систематизирам информацията. Извинявам се за забавянето! + +Ротациите обаче променят височината на лявото и дясното поддърво на корена. + +Нека разгледаме 1, където правим ротация около х. Височината на дясното поддърво е 1 + max(h(beta) + h(gamma)). + +След ротацията височината на дясното поддърво е h(gamma). Следователно височината е **намаляла поне с единица**. + +По същата логика височината на лявото поддърво расте отново поне с единица. + +Разбрахме се, че ще се стараем да си държим дърветата ниски. Тези операции ще ни бъдат полезни в тази ни задача. ## Задача първа Да се напише функция, която проверява дали дадено дърво е двоично наредено дърво. diff --git a/Seminar09/media/rotations.jpg b/Seminar09/media/rotations.jpg Binary files differnew file mode 100644 index 0000000..a852ab3 --- /dev/null +++ b/Seminar09/media/rotations.jpg |
