Arborele binar de căutare (BST)
Căutarea binară funcționează pe o listă sortată, dar inserarea în listă costă O(n). Arborele binar de căutare (BST, *binary search tree*) păstrează ordinea și permite atât căutarea, cât și inserarea în O(h): la fiecare nod alegi o singură direcție.
Regula BST
Un arbore binar este arbore de căutare dacă, pentru fiecare nod, toate valorile din subarborele stâng sunt mai mici decât nodul, iar toate cele din subarborele drept sunt mai mari (sau egale, dacă permitem duplicate).
Scrie insereaza(radacina, val) (returnează rădăcina arborelui după inserare) și cauta(radacina, val) (returnează True/False, coborând pe o singură ramură la fiecare pas). Clasa Nod, inordine, pe_niveluri și testele sunt date.
- insereaza: pentru None creezi Nod(val); altfel inserezi recursiv la stânga (val mai mic) sau la dreapta și întorci nodul.
- cauta: o buclă while care alege nod.st sau nod.dr după comparație.
- Trebuie să apară: True, False, True, False, [1, 3, 4, 6, 7, 8, 10, 14], apoi arborele pe niveluri.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan