Arborii de regasire sunt structuri de date speciale care pot fi utilizate in reprezentarea multimilor de caractere sau a tipurilor de date care sunt siruri de obiecte de orice tip sau siruri de numere.
Un arbore de regasire permite implementarea simpla a operatorilor definiti asupra unei structuri de date de tip multime, ale carei elemente sunt siruri de caractere (cuvinte) (INSERTIE, SUPRIMARE, INITIALIZARE si TIPARIRE).
Utilizarea e eficienta atunci cand numarul de prefixe distincte ale tuturor cuvintelor din multime e mult mai mic decat numarul total de cuvinte.
Intr-un arbore de regasire, fiecare drum de la radacina spre un nod terminal, corespunde unui cuvant al multimii. Nodurile arborelui corespund prefixelor cuvintelor. Pentru delimitarea cuvintelor se foloseste caracterul '[' ( ord('[') = ord('Z') + 1 ).
Se pot face urmatoarele observatii:
Daca p e un pointer, Nod o valoare a structurii NodArboreDeRegasire, c o.valoare a tipului char, asupra structurii NodArboreDeRegasire, se definesc, urmatorii operatori:
type PointerNodArboreDeRegasire =^NodArboreDeRegasire;
caractere='A'..'[';
NodArboreDeRegasire=array[caractere] of PointerNodArboreDeRegasire;
Pentru caracterul '[' se adopta conventia : Nod['['] sa fie nil (cand nodul nu are fiu corespunzator lui '[') sau pointerul spre insusi Nod (cand nodul are fiu, indicand terminarea unui cuvant).
Exemplu: in figura 1. este reprezentat arborele trie care contine
cuvintele AR, ARAR, ARAT, PI, PIAN.
O implementare a operatorilor ar fi:
procedure Initializare(var Nod:NodArboreDeRegasire);
var c:char;
begin
for c:='A' to '[' do Nod[c]:=nil
end;
procedure Atribuie(var Nod:NodArboreDeRegasire; c:char;
p:PointerArboreDeRegasire);
begin
Nod[c]:=p
end;
function Valoare(var Nod:NodArboreDeRegasire; c:char)
:PointerArboreDeRegasire;
begin
Valoare:=Nod[c]
end;
procedure NodNou(var Nod:NodArboreDeRegasire; c:char);
begin
new(Nod[c]);
Initializare(Nod[c]^)
end;
Definind
type ArboreDeRegasire=PointerNodArboreDeRegasire;
se poate scrie procedura de adaugare a unui cuvant x in multimea cuvinte
implementata printr-un arbore de regasire:
procedure Adauga(x:TipCuvint;var cuvinte:ArboreDeRegasire);
var i:integer; {contorizeaza pozitia in cuvantul x}
t:ArboreDeRegasire; {utilizat pentru a indica nodurile
arborelui de regasire corespunzatoare prefixelor lui x}
begin
i:=1;
t:=cuvinte;
while x[i]<>'[' do
begin
if Valoare[t^,x[i])=nil then
{ nodul curent nu are fiu pentru x[i],
deci se creaza unul nou}
NodNou(t^,x[i]);
t:=Valoare(t^,x[i]); {se trece la fiul lui t
pentru caracterul x[i], chiar daca a fost creat recent}
i:=i+1
end; {s-a ajuns la caracterul '[' in x, deci la
sfarsitul lui}
Atribuie(t^,'[',t); {se face o bucla pentru '[',
pentru a marca un nod terminal}
end;
Arborele vid apare continand un singur nod, cu toti pointerii nil.
Pentru stergerea unui cuvant, se poate concepe o procedura recursiva, fiecare apel recursiv coborand cu cate un nivel in arborele de regasire.
Se coboara pana la nodul ce marcheaza sfarsitul cuvantului, avand intrarea corespunzatoare lui '[' diferita de nil . Prin punerea pe nil a acestei intrari, practic cuvantul e sters din dictionar.
Se mai poate verifica daca restul intrarilor din acest nod final sunt nil ( deci cuvantul sters nu e prefix pentru altele din dictionar ), caz in care se poate elibera spatiul ocupat de acest nod si se pune pe nil pointerul ce-l indica. La revenirea din recursivitate, se pot elibera spatiile ocupate de toate nodurile avand toti pointerii pe nil.
Configuratia arborelui trie nu depinde de ordinea in care se fac insertiile sau suprimarile.
Listarea cuvintelor unui arbore de regasire se face parcurgand cu o procedura recursiva nodurile, colectand la fiecare nivel, cate un caracter din cuvantul curent. Pentru fiecare nod, prelucrarea consta in: - daca e marcat sfarsitul unui cuvant ( elementul de indice '[' nu e nil ), se tipareste cuvantul curent ( tabloul in care s-au cules caracterele ) - pentru fiecare pointer corespunzator caracterelor 'A'..'Z', diferit de nil, se adauga respectivul caracter cuvantului curent si se apeleaza procedura recursiva de listare pentru descendent.
Se pot gasi diferite implementari, observand ca un nod de regasire este de fapt o asociere. Deoarece domeniul si codomeniul contin un numar restrans de elemente, apare potrivita reprezentarea bazata pe liste inlantuite.
Exemplu: in figura 2. este reprezentat arborele de regasire implementat cu ajutorul listelor si care contine cuvintele AR, ARAR, ARAT, PI, PIAN.
type NodArboreDeRegasire=^NodLista;
NodLista=record
domeniu:char;
valoare,urmator:NodArboreDeRegasire
{indica prima celula a listei nodului fiu, respectiv urmatoarea
celula a listei nodului curent}
end;
O alta varianta ar fi ca sufixele ( resturile cuvintelor ce au un prefix comun) sa fie memorate in cate o lista inlantuita sau un ABO in scopul reducerii memoriei ocupate de arborele trie.
Cum in cazul arborilor, performantele prelucrarii depind de inaltimea lor, e avantajos a se lucra cu arbori echilibrati : AVL, binari optimi sau binari B, insa algoritmii de prelucrare sunt foarte complecsi. in continuare se va prezenta implementarea folosind arborii B-binari, care sunt arbori-B de ordinul 1. Au toate nodurile terminale pe acelasi nivel, iar nodurile interioare au unul sau doua elemente, deci doi sau trei descendenti (se mai numesc arbori 2-3).
Se va utiliza o implementare diferita de cea prezentata la Lucrarea 5 referitoare la arborii B-binari.
Se presupune ca arborele reprezinta o multime de elemente peste
care este definita o relatie de ordonare notata '<'. Elementele sunt plasate
in nodurile terminale; daca un element x se gaseste la stanga unui element
y, e valabila relatia x Un arbore 2-3 cu h niveluri, contine intre 2h-1si 3h-1noduri
terminale, deci arborele 2-3 de reprezentare a unei multimi de n elemente,
are inaltimea intre 1+log3n si 1+log2n.
Cautarea unei chei intr-un arbore 2-3, se realizeaza cu un efort
O(log n), prin particularizarea cautarii intr-un arbore B. Astfel, cautarea
unei chei x se realizeaza simplu, parcurgand arborele de la radacina spre
nodurile terminale. in fiecare nod parcurs, continand cheile (a,-) sau
(a,b), se compara x cu a, daca x Implementarea acestei reprezentari se poate realiza in limbajul
PASCAL, utilizand structura de tip articol cu variante:
Insertia in arbori 2-3 se realizeaza in principiu ca cea in arbori B.
Astfel, insertia unui nod cu cheia x incepe cu cautarea cheii x in arbore.
Daca se ajunge la un nod apartinand nivelului situat chiar deasupra
nivelului terminal si se constata ca fiii acestuia nu contin pe x, se
procedeaza la insertie. Daca nodul are numai doi fii, se face x cel de-al
treilea fiu al nodului, plasandu-l la locul potrivit si reajustand structura
nodului, astfel incat aceasta sa reflecte noua situatie. Daca nodul
considerat are trei fii, atunci adaugarea celui de-al patrulea fiu fiind
imposibila, nodul se scindeaza in doua noduri, iar cei patru fii ai sai sunt
redistribuiti: cei doi cu chei mai mici fostului nod, iar ceilalti doi fii cu
chei mai mari, nodului nou aparut prin scindare. in continuare, nodul
nou aparut trebuie inserat in structura de arbore. in urma acestui proces,
scindarea se poate propaga spre nivelurile inferioare ale structurii, in
cazul extrem, pana la radacina. Aceasta este de fapt singura posibilitate ca
un arbore 2-3 sa creasca in inaltime.
Se va prezenta procedura Insertie care se apeleaza pentru radacina
si procedura Insertie1 care parcurge arborele intr-o maniera recursiva
pentru insertia elementului x. Se presupune ca arborele 2-3 nu este vid,
nici cu un singur nod, cazuri care se trateaza simplu, separat.
Procedura Insertie1 returneaza pointerul la nodul nou creat, daca
se creaza un astfel de nod, si cheia celui mai mic element al subarborelui
determinat de acest nod. Acest lucru este realizat cu ajutorul parametrului
Pnou, respectiv Mic, care se atribuie in situatia in care se returneaza un
nod nou. Structura de principiu a procedurii Insertie1 este:
Suprimarea in arborii 2-3 se realizeaza intr-o maniera similara cu
cea in arborii B.
Astfel, fie n parintele nodului de suprimat si fie p parintele lui n,
bunicul nodului de suprimat. Daca n are trei fii, suprimarea se face
simplu. Daca in urma suprimarii, n ramane cu un singur fiu
(subdepasire), arborele 2-3 trebuie reorganizat. Daca n este chiar nodul
radacina, dupa suprimare, singurul lui fiu va deveni noua radacina. Daca
p mai are un fiu situat la stanga sau la dreapta lui n si acest fiu are la
randul sau trei fii, in cadrul unui proces numit "echilibrare", se va realiza
"imprumutul" unui fiu, astfel incat n sa aiba doi fii. Daca insa fiul lui p
adiacent lui n are numai doi fii, echilibrarea nu se mai poate realiza prin
transfer si in consecinta se transfera singurul fiu al lui n unui frate
adiacent si se suprima n. Daca in urma acestui proces, denumit
"contopire", p ramane cu un singur fiu, se repeta procedura in mod
recursiv, substituind pe n cu p, trecand astfel pe nivelul urmator al
structurii arborelui. in caz extrem, procesul acesta se poate propaga pana
la radacina, aceasta fiind practic singura cale de reducere a inaltimii
arborelui.
Configuratia arborelui 2-3 depinde de ordinea in care se fac
insertiile si suprimarile.
Exemplu: in figura 3.a. este prezentat arborele 2-3 continand cheile 1 3 5
7 9 11 13 15. Dupa insertia cheii 8, configuratia arborelui este cea din
figura 3.b., iar dupa suprimarea cheii 5 in figura 3.c.
type TipElement=record
cheie:real;
{alte campuri utile}
end;
TipNod=(terminal, interior);
PointerNodArbore2_3=^NodArbore2_3;
NodArbore2_3=record
case fel:TipNod of
terminal:(element:Tiplement);
interior:(cheie_stang,cheie_drept:real;
fiu_unu,fiu_doi,fiu_trei:PointerNodArbore2_3)
end;
O multime poate fi definita ca un pointer la radacina arborelui 2-3
care o reprezinta.
type Multime=PointerNodArbore2_3;
2.1.Insertia in arborii 2-3
procedure Insertie1(Nod:PointerNodArbore2_3; x:TipElement;
var Pnou:PointerNodArbore2_3; var Mic:real)
var Pprim,W:PointerNodArbore2_3; MicPrim:real;
begin
Pnou:=nil;
if *Nod este terminal then
if *x nu este elementul lui Nod then
begin
*creaza un nod nou indicat de Pnou;
*atribuie pe x noului nod;
Mic:=x.cheie
end;
else
begin {Nod este un nod interior}
*fie W acel fiu al lui Nod, caruia ii va apartine x;
Insertie1(W,x,Prim;MicPrim);
if Pprim <> nil then
begin
* insereaza pointerul Pprim printre fiii lui Nod in
dreapta lui W;
if *Nod are patru fii then
begin
*creaza un nod nou indicat de Pnou;
*asociaza acestui nod, fiii trei si patru ai lui Nod;
*actualizeaza valorile lui cheie_stang si
cheie_drept in Nod si in noul nod;
*pozitioneaza pe Mic cu cea mai mica cheie
apartinand fiilor noului nod
end
end
end
end;
Procedura Insertie, in cazul in care Insertie1 returneaza un nod
nou, trebuie sa creeze o noua radacina.
procedure Insertie(x:TipElement; var M:Multime);
var Pprim:PointerNodArbore2_3;
{pointer la noul nod returnat de Insertie1}
MicPrim:real; {valoarea Mic a subarborelui determinat de Pprim}
Temp:Multime; {utilizat pentru memorarea temporara a
valorii pointerului M}
begin
{se verifica daca M este arbore vid sau cu un singur nod
si se realizeaza insertia in consecinta}
Insertie1(M,x,Pprim,MicPrim);
if Pprim<>nil then
begin {se creaza o noua radacina, fiii radacinii sint
cei indicati de M, respectiv Pprim}
Temp:=M;
new(M);
with M^ do
begin
fel:=interior;
fiu_unu:=Temp;
fiu_doi:=Pprim;
fiu_trei:=nil;
cheie_stang:=Mic_prim
end
end
end;
2.2. Suprimarea in arborii 2-3
