Arborele echilibrat perfect. în cazul în care pentru fiecare dintre numărul său de nod de noduri din subarborele stânga și dreapta nu diferă cu mai mult de 1.
Arborele este echilibrat. în cazul în care pentru fiecare nod sale înălțime două subramificații respective nu diferă cu mai mult de 1.
Caută copac - un copac în care fiecare nod
AVL-tree (Adelson-Belsky, Landis) - un arbore de căutare echilibrat.
Fig. 6. Exemple de arbori binari.
a), b) - arbori echilibrate; b) - un arbore perfect echilibrat. căutare copac, AVL-tree
Crearea unui arbore ideal de echilibrat
Secvența de pași pentru a crea un arbore perfect echilibrat pentru un număr de pre-cunoscute de noduri (n):
Creează un nod rădăcină;
Într-un mod similar cu subarborele stâng este construit cuprinzând nl = n div 2 noduri;
Într-un mod similar cu subarborele drept este construit cuprinzând nr = n-nl-1 noduri;
Recursivitatea se termină dacă subramificație nu conține nici un nod (n = 0).
Exemplul 3. PROCEDURA DE pomului echilibrată IDEAL
if (x if (x> p ^ .key) apoi Căutare (x, p ^ .Right) altceva writeln ( „unitate există o“) Pentru căutare procedură recursiv pentru o valoare în arborele este suficientă pentru a înlocui introducerea bloc a unui nou nod pentru a afișa un mesaj (sau întoarce valoarea zero), și un mesaj de avertizare „unitate există o“ puteți lăsa (sau înlocuită cu o trimitere la nodul găsit). Folosind arborele de căutare pentru a sorta datele - construirea unui arbore de căutare, și apoi du-te în jurul ei de regula LPC (crescator) sau PCL (descrescator) Exemplul 8. căutare PROCEDURA cu (non-recursivă) ... Ref2 Egal copaci care sunt create funcția CreateTree (Exemplul 3) și procedura de căutare (Exemplul 7) pentru „calculatoare“ secventa de caractere de intrare. NOTĂ. . A se vedea, de asemenea, programul: TreeSearch.exe (directorul \ Program Files \ 02_DerevoPoiska) - crearea arborelui de căutare și a sustragerii acestuia; Demt.exe (directorul \ Program Files \ 03_DerevoPoiska) - crearea arborelui de căutare și echilibrat. Eliminarea unui nod din arbori de căutare EXEMPLUL 10 PROCEDURA DE SCOATERE DIN NOD CAUTARE TREE Notă: Când ștergeți un element cu doi descendenți de substituție are loc pe dreapta-cele mai multe elemente ale subarborele stâng (a se vedea protsedurudel). PROCEDURA DELNODE (x: char; VAR p: arbore); Procedura del (var r: arbore);articole similare