BST / AVL puu visualiseerija

Binary Search Trees mandate a strict hierarchical organization, ensuring left-child nodes hold lesser values. AVL trees enhance this by algorithmically enforcing a maximum height differential of one between subtrees. This mathematical self-balancing requires precise rotational transformations upon insertion or deletion. Such structural constraints guarantee search, insertion, and deletion operations remain bounded by O(log n) time complexity, optimizing rapid data retrieval.

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.

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.