Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 14. 03. 2016 21:00
Stromy (rotace)
Dobrý den,
prosím Vás, potřeboval bych poradit s důkazem v jedné úloze.
Zadání:
Nechť T_1 a T_2 jsou dva binární vyhledávací stromy se stejnou množinou n klíčů. Dokažte, že T_1 lze na T_2 převest pomocí O(n) rotací.
První, co mě napadlo, že by to šlo dokázat nějak pomocí matematické indukce, ale nejsem si úplně jistý postupem. Kdyby někdo mohl nasměrovat, budu moc rád.
Offline
