BST / AVL puu visualiseerija

Sisesta väärtusi ja vaata, kuidas puu kasvab. Lülitu AVL-režiimile, et näha automaatset tasakaalustamist.

Näidisarvutus — BST / AVL puu visualiseerija

Puu kõrgus	7
Tippude arv	7
Tüüp	BST
Ideaalne tasakaalustatud kõrgus	3
AVL-pöörded	väljas

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Sorteeritud sisend on halvim sisend 🖖

Kahendotsingupuu kiirus tuleb tema kujust ja kuju tuleb ainuüksi lisamisjärjekorrast. Anna sellele tööriistale 10, 20, 30, 40, 50, 60, 70 just selles järjekorras: iga võti on eelmisest suurem ja jääb seega eelmisest paremale, nii et puust saab sirge kett kõrgusega 7. See on ahelloend, mis kannab kaasas puuviitade lisakulu, ja 70 leidmine nõuab seitset võrdlust kolme asemel. Andmetes ei olnud midagi patoloogilist — need olid lihtsalt juba sorteeritud, ja just nii andmed enamasti saabuvadki. Lülita needsamad seitse väärtust AVL-režiimi ja pöörded suruvad kõrguse tagasi kolmele. Selles ongi kogu isetasakaalustuvate puude argument.

Iga samm viskab poole minema 🖖

Kahendotsingupuu töötab nagu sõna otsimine sõnastikust: igas tipus võrdled ja viskad kohe kõrvale terve poole, mis sinu väärtust sisaldada ei saa. Seepärast leiab hästi kujundatud puu miljoni kirje seast iga väärtuse umbes 20 võrdlusega. Kuid kuju sõltub täielikult lisamise järjekorrast — sisesta väärtused juba sorteeritult (10, 20, 30, …) ja vaata, kuidas puu variseb üheks kaldu jooneks, mis pole kiirem kui loendi ükshaaval läbivaatamine.

Kuldlõige peitub AVL-puudes 🖖

Lülitu AVL-režiimi ja küsi: kui kõrgeks võib tasakaalustatud puu antud tippude arvu juures üldse kasvada? Vastus peidab endas kuldlõiget. Iga kõrguse hõredaim lubatud AVL-puu on Fibonacci puu, mis on ehitatud kahest väiksemast Fibonacci puust, nii et tema tippude arvud järgivad Fibonacci jada. Seepärast kannab kõrguse ülempiir konstanti 1.44 — see on täpselt 1 / log₂(φ), kus φ ≈ 1.618 on kuldlõige.

BST- JA AVL-PUUD — SAMAD VÄÄRTUSED, NELI ERINEVAT PUUD

Millise puu annab sinu lisamisjärjekord?

Kahendotsingupuu kuju ei otsusta see, milliseid väärtusi ta hoiab, vaid järjekord, milles need saabusid — ja see kuju on kogu hind: iga otsing, lisamine ja kustutamine kõnnib juurest leheni, nii et maksma läheb kõrgus. Kaks küsimust ütlevad, millises juhtumis sa oled: kas väärtused saabusid juba sorteeritult, ja kas keegi pöörab neid tasakaalu tagasi?

Tasakaalus BST — saabumisjärjekord põimus hästi h = 3 = ⌈log₂(n + 1)⌉

Mandunud BST — sorteeritud sisend, miski ei tasakaalusta h = n = 7 ⇒ O(n)

AVL tasakaalustamine — pööre on kohalik ja odav |hL − hR| > 1 → ↻, h = 3

AVL sorteeritud sisendiga — juhtum, mille jaoks pöörded olemas on ↻ × 4 ⇒ h = 3 < 7

Tasakaalus BST — saabumisjärjekord põimus hästi

Mida sa tead: Puhas BST-režiim, pöördeid pole. Väärtused saabuvad keskelt alustades, nii et iga uus võti kukub veel madalasse alampuusse ja kumbki pool ei jookse teisest ette.

Mida see maksab: h = 3 = ⌈log₂(n + 1)⌉

Näidisarvutus: 50, 30, 70, 20, 40, 60, 80 → juur 50, 7 tippu, kõrgus 3 — täpselt ideaal ⌈log₂(7+1)⌉ = 3, seega kõige sügavam otsing kulutab 3 võrdlust

Ava see juhtum: Tasakaalustatud

Tasakaalus BST — saabumisjärjekord põimus hästi. Seitse tippu kolmel tasemel: iga leht juurest ühekaugusel — paremaks ei lähe. Puhas BST-režiim, pöördeid pole. Väärtused saabuvad keskelt alustades, nii et iga uus võti kukub veel madalasse alampuusse ja kumbki pool ei jookse teisest ette. — Seitse tippu kolmel tasemel: iga leht juurest ühekaugusel — paremaks ei lähe.

Mandunud BST — sorteeritud sisend, miski ei tasakaalusta

Mida sa tead: Jällegi puhas BST-režiim, aga väärtused saabuvad kasvavas järjekorras. Iga järgmine on suurem kui kõik juba salvestatu, seega läheb paremale — iga kord.

Mida see maksab: h = n = 7 ⇒ O(n)

Näidisarvutus: 10, 20, 30, 40, 50, 60, 70 → juur 10, 7 tippu, kõrgus 7 asemel 3; 70 leidmine kulutab 7 võrdlust ja tööriist nimetab tulemust ahelloendiks

Ava see juhtum: Taandunud

Mandunud BST — sorteeritud sisend, miski ei tasakaalusta. Igal tipul on üks laps: otsing kõnnib läbi kõik seitse taset, mitte kiiremini kui massiivi läbivaatus. Jällegi puhas BST-režiim, aga väärtused saabuvad kasvavas järjekorras. Iga järgmine on suurem kui kõik juba salvestatu, seega läheb paremale — iga kord. — Igal tipul on üks laps: otsing kõnnib läbi kõik seitse taset, mitte kiiremini kui massiivi läbivaatus.

AVL tasakaalustamine — pööre on kohalik ja odav

Mida sa tead: AVL-režiim. Pärast iga lisamist kõnnib puu juure poole tagasi ja esimene tipp, mille kahe alampuu kõrgused erinevad rohkem kui 1 võrra, pööratakse. Tippude kõrval olevad märgid näitavad vasakut kõrgust miinus paremat.

Mida see maksab: |hL − hR| > 1 → ↻, h = 3

Näidisarvutus: 30, 20, 10, 25, 35, 40 AVL-režiimis → 10 lisamine kallutab tipu 30 väärtusele +2 ja üks parempööre tõstab 20 tema asemele; hiljem kallutab 40 ühe tipu väärtusele −2 ja üks vasakpööre parandab selle. 2 pööret, 6 tippu, kõrgus 3.

Ava see juhtum: AVL-i tasakaalustamine

AVL tasakaalustamine — pööre on kohalik ja odav. Ringiga tähistatud tipud tõstis üles pööre; iga märk on tagasi vahemikus ±1. AVL-režiim. Pärast iga lisamist kõnnib puu juure poole tagasi ja esimene tipp, mille kahe alampuu kõrgused erinevad rohkem kui 1 võrra, pööratakse. Tippude kõrval olevad märgid näitavad vasakut kõrgust miinus paremat. — Ringiga tähistatud tipud tõstis üles pööre; iga märk on tagasi vahemikus ±1.

AVL sorteeritud sisendiga — juhtum, mille jaoks pöörded olemas on

Mida sa tead: AVL-režiim, toidetud täpselt nende väärtustega, mis kaks juhtumit ülalpool andsid ahela. Iga lisamine kukub kõige parempoolsemasse otsa ja lükkab mõne eellase tasakaalu väärtusele −2, nii et pea iga lisamine käivitab paranduse.

Mida see maksab: ↻ × 4 ⇒ h = 3 < 7

Näidisarvutus: 10, 20, 30, 40, 50, 60, 70 AVL-režiimis → 4 vasakpööret ja juureks jääb lõpuks 40, mitte 10. Kõrgus 3, mitte 7 — sama sisend, samad seitse tippu, alla poole sügavusest.

Ava see juhtum: Sorteeritud AVL-i

AVL sorteeritud sisendiga — juhtum, mille jaoks pöörded olemas on. Samad sorteeritud väärtused nagu juhtumis 2, saabumise käigus kolmele tasemele tagasi pööratud. AVL-režiim, toidetud täpselt nende väärtustega, mis kaks juhtumit ülalpool andsid ahela. Iga lisamine kukub kõige parempoolsemasse otsa ja lükkab mõne eellase tasakaalu väärtusele −2, nii et pea iga lisamine käivitab paranduse. — Samad sorteeritud väärtused nagu juhtumis 2, saabumise käigus kolmele tasemele tagasi pööratud.

Allikad (1)

Insight block 3 — the Fibonacci tree that sets the AVL height bound: D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, §6.2.3. Addison-Wesley, 1998. ISBN 978-0-201-89685-5 — the sparsest legal AVL tree of each height, and the logφ bound that follows.

Ülesanne täielikult lahendatud

Seitsme sõlmega puu kõrgusega seitse 5 sammu
Seitse tippu ja puu kõrgusega seitse. Tasakaalustatud puu kõrgus oleks 3. Tehke kindlaks, mida sisend tegi — ja mida see suures skaalas maksma läheb.
1. Vaikimisi võtmed on 10, 20, 30, … — juba sorditud. Järgige lisamise reeglit ja iga uus võti on suurem kõigest muust puus, nii et see läheb iga kord paremale.
  
  $insert 10, 20, 30, 40, 50, 60, 70 in order$
2. Tulemusel pole üldse hargnemist. Igal tipul on üks alluv, seega on struktuuriks ahelloend, mis on lihtsalt joonistatud puuna, ning kõrgus võrdub tippude arvuga.
  
  $each new key > every key present ⟹ always the right child$
3. Parim võimalik kõrgus seitsme tipu korral on 3, sest puu kõrgusega h mahutab kõige rohkem 2ʰ − 1 tippu ja täpselt 2³ − 1 = 7. See sisend saavutab halvima juhu, kuigi valida oli tasakaalustatud variant.
  
  $h = n = 7 (a linked list wearing a tree’s name)$
4. Otsing liigub juurest alates, seega on ajakulu võrdne kõrgusega: siin 7 võrdlust 3 vastu.
  
  $h_{m i n} = ⌈ lo g_{2} (n + 1)⌉ = ⌈ lo g_{2} 8 ⌉ = 3$
5. Määrav on nende suhe, ja see kasvab. Miljoni tipu korral on tasakaalustatud puu kõrgus 20 ja sorditud sisendi korral miljon.
  
  $n = 1 0^{6} : h_{m i n} = 20 but sorted input gives h = 1 0^{6}$
Vastus

Tööriist kuvab 7 tipu puhul kõrguseks 7, võrreldes ideaalse 3-ga. Õppetund on selles, et O(log n) ei olnud kunagi binaarse otsingupuu omadus — see on lisamisjärjekorra omadus, ja kõige loomulikum järjekord, mida programmeerija sellele kunagi ette annab, sorditud andmed, on täpselt see, mis selle hävitab. See ongi kogu põhjus, miks AVL- ja punamustad puud eksisteerivad: need nõuavad lisamisel pööret või paari, et muuta see garantii tingimustetuks. Vahetage režiim AVL-iks ja jälgige, kuidas samad seitse võtit asetuvad kõrgusele 3.

$O (lo g n) is a claim about the INPUT ORDER, not about the structure$

42Mathi meeskond · Uuendatud 2026-07-28

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

Tasakaalustatud - Tasakaalustatud BST: 7 tippu, kõrgus 3
Taandunud - Sorteeritud sisend: BST venib kõrgusele 7
AVL-i tasakaalustamine - AVL tasakaalustub 2 pöördega
Sorteeritud AVL-i - Samad sorteeritud väärtused AVL-is: kõrgus 3 pärast 4 pööret