De ce contează?
Cauți cuvântul „obeliscul" într-un dicționar gros. Nu îl iei pagină cu pagină: deschizi pe la mijloc, vezi că ești pe la litera „m", deci sari în jumătatea din dreapta — restul stâng nu te mai interesează deloc. Repeți: jumătate, jumătate, jumătate, până ajungi la cuvânt. Un arbore binar de căutare este exact această idee transformată în structură: la fiecare pas arunci jumătate din ce a mai rămas.
Intuiția
Imaginează un arbore în care fiecare nod ține o valoare și respectă o singură regulă de aur: tot ce e în stânga lui e mai mic, tot ce e în dreapta e mai mare. Atunci, ca să cauți o valoare, o compari cu rădăcina și cobori într-o singură ramură — stânga dacă e mai mică, dreapta dacă e mai mare. Cealaltă jumătate a arborelui dispare din calcul, exact ca jumătatea de dicționar pe care n-o mai răsfoiești. Căutarea binară, dar pe o structură care se poate și modifica ușor.
Invariantul BST, exact: pentru orice nod, tot subarborele stâng conține doar valori mai mici, iar tot subarborele drept doar valori mai mari — TOT subarborele, nu doar fiii direcți. Din acest invariant decurge totul: o comparație elimină o ramură întreagă, iar parcurgerea în inordine scoate valorile exact în ordine sortată.