Arborele binar

În calculul unui arbore binar este un arbore ale cărui noduri au grad între 0 și 2. Pentru arbore înseamnă un grafic nu direct, conectat și aciclic, în timp ce pentru gradul unui nod este definit ca numărul de arbori de sub nod, care este egal cu numărul de copii ai nodului.

Chiar și arborele format dintr-un singur nod și fără margini este considerat un arbore binar valid, deși gradul nodului în acest caz este nul.

Ca și în cazul general al copacilor, este posibil să se identifice (într-un mod non- unic) un nod rădăcină: orice nod de grad mai mic de 3 poate fi ales ca rădăcină a arborelui binar. Odată ce un nod rădăcină a fost stabilit, este posibil să se construiască relații de rudenie între noduri: nodul rădăcină nu are tată și poate avea 0, 1 sau 2 copii și fiecare nod este evident tatăl copiilor săi. Întrucât toate nodurile, cu excepția rădăcinii, au un părinte, datorită limitării gradului de noduri, fiecare nod poate avea maximum 2 copii (de unde și numele „copac binar”).

Nodurile fără copii se numesc frunze sau noduri terminale; un nod fără frunze este un nod intern.

Implementați copaci binari

În această secțiune ne ocupăm de implementarea arborilor binari din punct de vedere teoretic, folosind structuri de programare generice; programatorul va decide apoi cum să implementeze aceste structuri pe baza limbajului de programare pe care îl va folosi.

Există diverse sisteme, dar cel mai simplu este cel care folosește o matrice care conține nodurile arborelui conform acestei logici: rădăcina ocupă prima poziție a matricei și copiii acestei rădăcini sunt la rândul lor în matrice și ocupă ca poziție (2i) și (2i + 1) unde i este poziția rădăcinii, a tatălui, a celor doi copii.

Trebuie remarcat faptul că această implementare este optimă dacă arborele este complet, adică dacă toate elementele care alcătuiesc arborele au exact doi copii, cu excepția evidentă a frunzelor, altfel este necesar un steag boolean , de fapt o matrice însoțitoare, care indică dacă poziția este validă sau nu.

Să o interpretăm: în A, poziția 1, există întotdeauna rădăcina, în poziția 2 și 3 găsim copiii B și C. Să luăm copilul B, poziția 2, copiii ei sunt în 4 și 5, dar, steagul coloana ne spune că pozițiile 4 și 5 sunt dezactivate, de fapt B nu are copii, dimpotrivă, poziția C 3, în 6 și 7 are exact valorile căutate și că sunt cei doi copii D, E.

Avantajele utilizării acestei implementări sunt simplitatea accesului și simplitatea gestionării elementelor listei, dimpotrivă, operațiunile de inserare și, în general, dimensiunea considerabilă a unei matrice de arbori mari se joacă împotriva acestei implementări, care, prin urmare, se dovedește a fi incomod de utilizat.

O altă implementare care implică utilizarea matricelor este cea a reprezentării conectate cu matrice , în care, într-un tabel cu trei coloane avem, respectiv, pe rând, în cel central valoarea, în stânga adresa stânga copil și în cel potrivit adresa celui potrivit. Este necesar să adăugăm un start variabil pentru a indica punctul în care trebuie să începem analiza, dimpotrivă, dacă o adresă este la zero, aceasta este considerată NULL .

Start = 1

Începând de la 1, A are copii care sunt în 2 și 3, copilul B nu are descendenți, în timp ce cel C are ca descendenți 4 în stânga și 5 în dreapta, adică D și E.

Același rezultat poate fi obținut luând în considerare în locul unui tablou , un nod structurat simplu cu trei câmpuri, etichetă, copil stâng, copil drept și cu un pointer la primul nod și, de fapt, ne reconectăm la imaginea care însoțește cele două tabelele anterioare.

Adâncimea unui copac : rădăcina r are adâncimea 0, copiii stânga și dreapta au adâncimea 1, nepoții adâncimea 2 și așa mai departe. Deci, dacă adâncimea unui nod este pi, copiii săi care nu sunt goi au adâncimea p + 1

În ceea ce privește înălțimea h a unui copac binar este dată de adâncimea maximă atinsă de frunzele sale. Prin urmare, înălțimea măsoară distanța maximă a unei frunze de rădăcina arborelui, în ceea ce privește numărul de arce încrucișate. Deoarece definiția copacilor se aplică și subarborilor, este mai eficientă și mai ușoară găsirea înălțimii unui copac binar observând că arborele format dintr-un singur nod are înălțimea de 0, în timp ce un copac cu cel puțin două noduri are înălțime. egală cu înălțimea subarborelui său cel mai înalt, mărită cu unul pe măsură ce rădăcina introduce un alt nivel

h = adâncimea celei mai lungi căi

În cazul arborelui din figura de mai sus, înălțimea h este 0 (frunze) +1 (copii rădăcină) +1 (rădăcină) = 2.

Există câteva formule pentru calcularea caracteristicilor copacilor:

$Log_{2}(n+1)-1$ ${\ displaystyle Log_ {2} (n + 1) -1}$ $Jurnal_ {2} (n + 1) -1$	Înălțimea unui arbore binar echilibrat umplut cu n noduri
$2^{h+1}-1$ ${\ displaystyle 2 ^ {h + 1} -1}$ $2 ^ {{h + 1}} - 1$	Numărul maxim de noduri dintr-un arbore binar de înălțime h
$h$ ${\ displaystyle h}$ $h$	Înălțimea sau numărul minim de noduri ale unui copac cu înălțimea h
$2^{l}$ ${\ displaystyle 2 ^ {l}}$ $2 ^ {l}$	Numărul maxim de noduri la un nivel l (elle)

Implementați copaci binari de căutare pe tablouri

Dacă nu este necesar să efectuați frecvent operații de inserare și ștergere sau nu este necesar să le efectuați deloc și nu doriți să utilizați prea multă memorie, este posibil să implementați un arbore de căutare binară pe o matrice ordonată, cu restricția că numărul de elemente este $2^{n}-1$ ${\ displaystyle 2 ^ {n} -1}$ $2 ^ {{n}} - 1$ cu $n\in \mathbb {N}$ ${\ displaystyle n \ in \ mathbb {N}}$ $n \ in \ mathbb {N}$ .

Imaginea de mai sus arată un arbore de căutare binar implementat pe o matrice ordonată de 15 elemente, începând prin plasarea centrului matricei ca rădăcină a arborelui și ca frunze ale acestuia respectiv centrul părții din dreapta matricei și centrul partea stângă a matricei, continuați să aplicați procedura recursiv până când toate elementele au fost acoperite. Se obține apoi echivalentul arborelui

pseudo-algoritmul pentru căutarea unei chei este

 Căutați o cheie
   N: = numărul de elemente ale arborelui (2 ^ k-1)
   A: = matrice de N chei sortate în ordine crescătoare, A [0], A [1] .. A [N - 1]
   cheie: = cheie de căutat
   sari: = (N + 1) / 4
   i: = (N - 1) / 2
   în timp ce sari> 0 faceți
       if key == A [i] atunci
           căutați peste
       altfel dacă tasta <A [i] atunci
           i = i - sari
       altfel dacă tasta> A [i] atunci
           i = i + salt
       endif
       jump = jump / 2
   Terminat
   nici un rezultat

Modul de afișare menționat anterior al unui arbore binar exploatează definiția skip-list , adică a unui arbore binar ale cărui elemente sunt ordonate și se folosește un algoritm randomizat. Într-o listă de sărituri pentru a căuta un element, nu facem altceva decât să creăm liste noi începând cu cel inițial L0, înjumătățind elementele de fiecare dată după regula (n / 2 ^ i) = 2, adică știm că putem crea liste Li până atunci nu ajungem la lista cu cel mai mic număr de elemente, adică 2. Lista de sărituri este foarte utilă dacă vrem să găsim un element, deoarece în căutare trebuie să începem din lista L (lgn) și mergi întotdeauna în căutarea primului element mai mare decât valoarea căutată x; este un algoritm bun chiar dacă este scump din punct de vedere al spațiului, dar este mai dificil să adăugați sau să ștergeți un element.

Implementați copaci binari folosind pointeri

O modalitate ușoară de a implementa arborii de căutare binară este utilizarea de indicatori. În implementarea clasică, fiecare nod al arborelui, pe lângă valoarea sa, are un pointer către copilul din dreapta și unul către copilul din stânga, în acest fel este posibil, începând de la rădăcină, să coboare în copac până la frunze . Toate nodurile sunt aceleași, singura diferență este că niciun nod nu va indica rădăcina (de fapt rădăcina nu este nici un copil drept, nici un copil stâng), iar frunzele care nu au copii nu vor indica nimic (zero, valoare NULL) .

O implementare simplă în C

 / ************************************************** *************************************************** **********
* Acest fișier va include funcțiile necesare pentru a construi un arbore binar,
* și gestionați-l prin
* indicațiile pe care fiecare rădăcină le are față de copilul drept și copilul stâng.
* Interfața este destul de simplă, odată ce ați început ajungeți la un meniu.
* Este recomandat să îl compilați sub * nix pentru a utiliza „gcc -o btree binarytree.c”,
* Pentru a porni în schimb, așa cum sugerează parametrul EROARE
* va fi util să urmați formularul ./btree <filename>, unde numele fișierului poate conține și calea completă.
* datele din numele fișierului trebuie să fie întregi separate prin spații.
*************************************************** *************************************************** ********** /

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

FILE * intfile ;

typedef struct T { // Încep să definesc structura de care voi avea nevoie
    valoarea int ; // După cum văd, am valoarea curentă și două indicatoare: una către copilul din stânga
    struct T * T_l , * T_r ; // Și celălalt către fiul potrivit
} * copac , slab ;

tree mergetree ( int el , tree t1 , tree t2 ) { // Mergetree alătură doi copaci
    copac t0 = ( copac ) malloc ( sizeof ( dim ));
    t0 -> T_l = t1 ;
    t0 -> T_r = t2 ;
    t0 -> valoare = el ;
    retur ( t0 );
}

copac createleaf ( int el ) {
    returnează mergetree ( el , NULL , NULL ); // Fiecare frunză este formată dintr-o valoare și două indicatoare nule
}

int isvoidtree ( copac t ) { // Verific dacă un copac este gol
    return ( t == NULL ); // Dacă nu este nimic, este evident că este un copac gol ...
}

tree leftchild ( tree t ) { // Returnează copilul stâng accesând structura tree
    returnează t -> T_l ;
}

tree rightchild ( tree t ) { // Returnează copilul potrivit, accesând structura copacului
    returnează t -> T_r ;
}

int root ( copac t ) { // Returnează rădăcina, accesând în continuare structura
    returnează t -> valoare ;
}

tree insert ( int el , tree t ) { // Insert a integer el, into tree t
    if ( isvoidtree ( t )) { // Dacă arborele este gol, atunci se va crea o frunză
        return createleaf ( el );
    }
    
    if ( rădăcină ( t ) > = el ) { // Altfel procedăm cu directive, adică dacă valoarea rădăcinii este> = a elementului
        returnează mergetree ( rădăcină ( t ), inserare ( el , leftchild ( t )), rightchild ( t )); // Va merge la stânga
    }
    
    dacă ( rădăcină ( t ) < el ) { // A și rădăcina este mai mică decât elementul, va fi inserată în dreapta.
        returnează mergetree ( rădăcină ( t ), leftchild ( t ), insert ( el , rightchild ( t )));
    } altceva {
        retur t ;
    }
}

int mintree ( copac t ) { // Găsesc minimul prin dihotomie: știind că cu cât mă mișc mai jos
    if ( isvoidtree ( leftchild ( t ))) {
        returnează rădăcina ( t ); // Și în stânga, cu atât mai mult am un număr mic.
    } altceva {
        returnează mintree ( leftchild ( t )); // Repet procedura recursiv.
    }
}

int maxtree ( copac t ) {
    if ( isvoidtree ( rightchild ( t ))) {
        returnează rădăcina ( t ); // În ceea ce privește minimul, numai în acest caz
    } altceva {
        returnează maxtree ( rightchild ( t )); // Mă deplasez în dreapta jos
    }
}

voit showtree ( copac t ) {
    int i ;
    
    if ( isvoidtree ( t ) == false ) {
        showtree ( leftchild ( t ));
        printf ( "% d" , rădăcină ( t ));
        showtree ( rightchild ( t ));
    }
}

int main ( int argc , char * argv []) {
    if ( argc < 2 ) { // Verificați dacă sunt prezenți toți parametrii
        printf ( "EROARE: Pentru a porni programul, sintaxa este ./btree <file> \ n " );
        
        returnare ( 1 );
    }
    
    if (( intfile = fopen ( argv [ 1 ], "r" )) == NULL ) { // Deschid fișierul de care am nevoie
        printf ( "EROARE: Nu se poate deschide fișierul% s \ n " , argv [ 1 ]);
        
        retur ( 2 );
    }
    
    printf ( "* Am deschis fișierul% s. \ n " , argv [ 1 ]);
    
    int num ; // Scanați fișierul pentru numere întregi
    copac copac = NUL ; // Inițializați arborele gol
    
    while ( fscanf ( intfile , "% d" , & num ) ! = EOF ) {
        copac = insert ( num , copac );
    }
    
    printf ( "* Am construit arborele binar \ n \ n " );
    printf ( "Ce vrei să faci acum? \ n " );
    printf ( "[s] tamponează arborele \ n " );
    printf ( "Găsiți [m] inimo \ n " );
    printf ( "Căutați maximul [M] \ n " );
    printf ( "[u] scire. \ n \ n " );
    
    char tmp ;
    
    printf ( ">" );
    
    while (( tmp = getchar ()) ! = 'u' ) {
        comutator ( tmp ) {
            case 's' : // Folosit pentru a arăta arborele
                 arborele de spectacol ( copac );
                 printf ( " \ n " );
            pauză ;
            
            case 'm' : // Imprimați valoarea minimă pe ecran
                 printf ( "Valoarea minimă a arborelui binar este% d \ n " , mintree ( copac ));
            pauză ;
            
            majusculă „M” : // Imprimați valoarea maximă pe ecran
                 printf ( "Valoarea maximă a arborelui binar este% d \ n " , maxtree ( copac ));
            pauză ;
            
            implicit :
                printf ( ">" );
            pauză ;
        }
    }
    fclose ( intfile );
    
    returnare ( 0 );
}

Algoritmi elementari pe copaci binari

Determinarea numărului de noduri dintr-un arbore binar

START

NumberNodes ( rădăcină de copac ) 
    Dacă rădăcina arborelui == NULL ( arborele este gol)
       retur 0 ;
    return ( NumeroNodi ( copilul stâng ) + NumeroNodi ( copilul drept )) + 1 ;
    
SFÂRȘIT

Determinarea înălțimii

 START

Înălțime ( rădăcină de copac )

    Dacă rădăcină copac == NULL ( în cazul în care „arborele este gol)
           retur 0 ;
    valueAltezzaSinistra = Înălțime ( copil stâng );
    valueAltezzaDestra = Înălțime ( copilul drept );
    returnează 1 + max ( valoarea RightHeight , valoarea LeftHeight );

SFÂRȘIT

Determinarea lățimii

Lățimea unui arbore binar corespunde numărului maxim de noduri situate la același nivel.

Determinarea acestei mărimi poate fi obținută printr-o modificare adecvată a vizitei în ordine : se folosește un vector, dimensionat egal cu numărul de noduri, inițial cu valori toate egale cu zero; funcția WrapperLarghezza este delegată trecerii corecte a parametrilor către funcția Larghezza recursivă, care returnează valoarea maximă conținută în vector, adică lățimea arborelui.

START

Lățimea învelișului ( rădăcină de copac )

    Initializare matrice de nivel ;
    Lățime ( rădăcină de copac , matrice de nivel , 0 );
    lățime = FindMaximumVector ( niveluri de matrice );
    lățimea de întoarcere ;

Lățime (rădăcină de copac, matrice nivel, nivelul actual)
   Dacă rădăcină copac == NULL ( în cazul în care „arborele este gol)
        întoarcere ;
    
   nivele [ nivel curent ] = niveluri [ nivel curent ] + 1 ;

   Lățimea (copil stânga, matrice nivel, nivelul curent + 1);
   Lățimea (copil dreapta, nivelul de matrice, nivelul curent + 1);

   întoarcere ;

SFÂRȘIT

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe un arbore binar

linkuri externe

BST echilibrat pe matrice Arborele binar pentru căutare, echilibrat și optimizat pe matrice

Controlul autorității	GND ( DE ) 4145532-0

Portal IT

Portalul de matematică