🌳・AVL Stromy

[versed cape]

👋 Vítej ve svém vlákně

Ahoj @proper tree, prosím počkej na někoho, než ti odpoví na tvou žádost o pomoc.

Přeji krásný zbytek dne!

Shrnutí vlákna:

• Potřeba pomoci s kreslením AVL stromu.
• Příklad čísel: 1, 5, 15, 2, 8, 6, 9.
• Nejasnosti ohledně rotací při vkládání čísla 6.

Vyskytl se problém? Kontaktuj nás pomocí ticketů! · Oct 29, 2025, 8:52 AM

🌳・AVL Stromy

[dreamy stag]

Ahoj, na to doporučuji třeba tuhle stránku, která ti ukáže, jak se strom následně vyvažuje při přidání prvku do větve.
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

[proper tree]

děkuji, snažím se to s té stránky pochopit. už chápu kdy se to má začít otáčet ale jak to nevím

[dreamy stag]

No (pokud si to dobře pamatuji)
K vyvažování dochází pokud rozdíl leveho podstromu a pravého podstromu (v nějakém podstromě) bude absolutne roven 2. (např. že levy podstrom jen o dvě úrovně hlubší než pravý podstrom).

Pak nastává proces vyvažování - to proto, aby nenastávala situace, že jeden podstrom je neúměrně složitější než druhý. A tím pádem byla zachována nějaká algoritmická složitost při jeho procházení.

Vyvažování se provádí dvěma operacemi

• jednoduchá (levá/pravá) rotace
• dvojitá (levá-pravá/pravá-levá) rotace.

Jednotlivé ty operace se trochu složitěji vysvětlují popisem a chce to asi o trochu cviku.
Přikládám tedy obrázky z Wikipedie. Kdyžtak se z nich pak odrazíme.

Jednoduchá rotace (prava)

Jednoduchá rotace (levá)

Dvojitá rotace (pravá-levá)

Dvojitá rotace (levá-pravá)