Un arbore binar de căutare este un arbore binar destinat îmbunătăţirii timpului de căutare a informaţiei. El va trebui să respecte următoarea proprietate: pentru oricare nod n, fiecare din descendentii din subarborele din stânga va avea valoarea informaţiei mai mică decât a nodului n, iar fiecare din descendenţii din subarborele din dreapta va avea valoarea informaţiei mai mare decât a nodului n.

 

 

de introdus

Creare, inserare si listare

 

 

Stergerea unui nod

 

Eventual

În figura de mai sus avem 2 arbori binari. Arborele din figura b) este arbore binar de căutare deoarece este respectată regula de mai sus, si anume că în oricare subarbore stâng valorile trebuie să fie mai mici decât ale rădăcinii şi în oricare subarbore dreapta, valorile trebuie să fie mai mari decât ale rădăcinii. (Cu alte cuvinte, toate valorile din nodurile aflate în stânga nodului n trebuie să fie mai mici, iar cele din dreapta mai mari). Se foloseşte exprimarea „oricare din subarborii” stâng respectiv drept, deoarece pentru rădăcina 7, elementele subarborelui stâng sunt 3, 1, 5, 4 (care sunt toate mai mici decât 7), iar elementele subarborelui drept sunt 11, 10, 15 (care sunt toate mai mari decât 7). Dacă în schimb vom considera ca rădăcină nodul 3, vom avea ca subarbore stâng nodul 1 (1 este mai mic decât 3), iar ca subarbore drept nodurile 5 şi 4 (ambele mai mari decât 3). Dacă vom considera ca şi rădăcină pe nodul 10, acesta nu are nici un copil, deci implicit respectă regula pentru arborii binari de căutare.

Arborele din figura a) nu este un arbore binar de căutare deoarece nu toate nodurile respectă regula. Nodul 4 nu are ce căuta acolo în dreapta nodului 8. Ar trebui să se afle în stânga lui 8 (4<8). Dacă privim mai sus observăm că nodul 4 ar trebui să se afle şi in stânga nodului 10, şi în stânga nodului 9, şi în stânga nodului 7. Cu alte cuvinte nodul 4 nu are ce căuta în subarborele drept.

A.

Exemplul 1

Exemplul 2

 

Up Home Structura Site