Un arbore binar de căutare este un arbore binar care are în plus următoarele proprietăți:
- cheile stocate în noduri (informația utilă) aparțin unei mulțimi peste care există o relație de ordine
- cheia dintr-un nod oarecare este mai mare decât cheile tuturor nodurilor din subarborele stâng şi este mai mică decât cheile tuturor nodurilor ce compun subarborele drept
Arborii binari de căutare permit menţinerea datelor în ordine şi o căutare rapidă a unei chei, ceea ce îi recomandă pentru implementarea de mulţimi şi dicţionare ordonate.
O importantă carcteristică a arborilor de căutare, este aceea că parcurgerea inordine produce o secvenţă ordonată crescător a cheilor din nodurile arborelui.
Valoarea maximă dintr-un arbore binar de căutare se află în nodul din extremitatea dreaptă şi se determină prin coborârea pe subarborele drept, iar valoarea minimă se află în nodul din extremitatea stângă, determinarea fiind simetrică.
Căutarea unei chei într-un arbore binar de căutare este asemănătoare căutării binare: cheia căutată este comparată cu cheia din nodul curent (iniţial nodul rădăcină). În funcţie de rezultatul comparaţiei apar trei cazuri:
- acestea coincid –> elementul a fost găsit
- elementul căutat este mai mic decât cheia din nodul curent –> căutarea continuă în subarborele stâng
- elementul căutat este mai mare decât cheia din nodul curent → căutarea continuă în subarborele drept
Inserarea unui nod se face, în funcţie de rezultatul comparaţiei cheilor, în subarborele stâng sau drept. Dacă arborele este vid, se creează un nod care devine nodul rădăcină al arborelui. În caz contrar, cheia se inserează ca fiu stâng sau fiu drept al unui nod din arbore.
Ștergerea unui nod este o operaţie puţin mai complicată, întrucât presupune o rearanjare a nodurilor. Pentru eliminarea unui nod dintr-un arbore binar de căutare sunt posibile următoare cazuri:
- nodul de şters nu există → operaţia se consideră încheiată
- nodul de şters nu are succesori → este o frunză
- nodul de şters are un singur successor
- nodul de şters are doi succesori