curs08.txt

STRUCTURI DE DATE SI ALGORITMI

                                    Curs 8


Arborele binar de cautare (BST)
Arborele binar de cautare reprezinta o solutie eficienta de implementare a
structurii de date numite "dictionar". Vom considera o multime "atomi".
Pentru fiecare element din aceasta multime avem:  a  atomi, este definita
o functie numita cheie de cautare: key(a)a partine lui k cu proprietatea ca
doi atomi distincti au chei diferite de cautare: a1!=a2=> key(a1)!=key(a2).

Exemplu:  (abreviere, definitie) ("BST","Binary Search Tree")
          ("LIFO","Last In First Out")  key(a) = a.abreviere

Un dictionar este o colectie S de atomi pentru care se definesc operatiile: 
insert(S,a)  insereaza atomul a 宯 S daca nu exista deja;
delete(S,k)  sterge atomul cu cheia k din S daca exista;
search(S,k)  cauta atomul cu cheia k 宯 S si-l returneaza sau determina daca
nu este.

O solutie imediata ar fi retinerea elementelor din S 宯tr-o lista 宯lantuita,
iar operatiile vor avea complexitatea O(n).

  Tabelele Hashing
Acestea sunt o alta solutie pentru a retine elementele din S. Complexitatea
pentru arborele binar de cautare 宯 cazurile:
  cel mai defavorabil: O(n);
  mediu:   O(log n).
Un arbore binar de cautare este un arbore T ale carui noduri sunt etichetate
cu atomii continuti la un moment dat 宯 dictionar.
T = (V, E) ,  圴