Un Arbore Binar de Căutare (BST) este un arbore în care toate nodurile urmați de mai jos-menționate proprietăți −
-
valoarea cheie a lăsat sub-arbore este mai mică decât valoarea de bază (rădăcină) nod de cheie.
-
valoarea cheii sub-arborelui drept este mai mare sau egală cu valoarea cheii nodului părinte (rădăcină).,astfel, BST împarte toți sub-arborii săi în două segmente; sub-arborele stâng și sub-arborele drept și poate fi definit ca −
left_subtree (keys) < node (key) ≤ right_subtree (keys)
reprezentare
BST este o colecție de noduri aranjate într-un mod în care mențin proprietățile BST. Fiecare nod are o cheie și o valoare asociată. În timpul căutării, cheia dorită este comparată cu tastele din BST și, dacă este găsită, valoarea asociată este recuperată.,
în Urma este o reprezentare grafică a BST −
se observă că nodul rădăcină cheie (27) are tot mai puțin apreciate tastele de pe partea stângă sub-arbore și cea mai valoroasă tastele de pe partea dreaptă sub-arbore.
operații de bază
următoarele sunt operațiile de bază ale unui arbore −
-
căutare − Caută un element într-un arbore.
-
Insert-introduce un element într-un copac.
-
pre-order Traversal-traversează un copac într-o manieră pre-order.
-
În ordine Traversal-traversează un copac într-o manieră în ordine.,
-
post-order Traversal-traversează un copac într-o manieră post-order.
nod
definiți un nod care are unele date, trimiteri la nodurile sale copil stânga și dreapta.
struct node { int data; struct node *leftChild; struct node *rightChild;};operație de căutare
ori de câte ori un element trebuie căutat, începeți căutarea din nodul rădăcină. Apoi, dacă datele sunt mai mici decât valoarea cheie, căutați elementul din subarborele din stânga. În caz contrar, căutați elementul din subarborele drept. Urmați același algoritm pentru fiecare nod.,
algoritm
Inserare operație
ori de câte ori un element este de a fi inserat, localizați mai întâi locația corectă. Începeți căutarea din nodul rădăcină, apoi dacă datele sunt mai mici decât valoarea cheii, căutați locația goală în subarborele din stânga și introduceți datele. În caz contrar, căutați locația goală în subarborele drept și introduceți datele.
Algoritm
Publicitate -