O altă diferență între arborele B și copacul binar este că B-tree trebuie să aibă toate nodurile sale copil la același nivel, în timp ce copacul binar nu are o astfel de constrângere. Un arbore binar poate avea maximum 2 subtrei sau noduri, în timp ce în arborele B poate avea un număr M de substraturi sau noduri unde M este ordinea arborelui B.
Diagramă de comparație
| Bazele de comparație | B-tree | Arbore binar |
|---|---|---|
| Constrângere esențială | Un nod poate avea la numărul maxim de M de noduri copil (unde M este ordinea arborelui). | Un nod poate avea cel mult 2 numere de subtrei. |
| Folosit | Se utilizează atunci când datele sunt stocate pe disc. | Se utilizează atunci când înregistrările și datele sunt stocate în memoria RAM. |
| Înălțimea copacului | log M N (unde m este ordinea arborelui M-way) | log 2 N |
| cerere | Codificarea structurii datelor în multe DBMS. | Optimizarea codului, codificarea lui Huffman etc. |
Definiția B-tree
Un arbore B este arborele echilibrat în formă de M și, de asemenea, cunoscut ca arborele de sortare echilibrat. Acesta este similar cu arborele binar de căutare unde nodurile sunt organizate pe baza traversal inorder. Complexitatea spațială a arborelui B este O (n). Complexitatea timpului de inserare și ștergere este O (log n).
Există anumite condiții care trebuie să fie valabile pentru un arbore B:
- Înălțimea copacului trebuie să fie cât se poate de minimă.
- Deasupra frunzelor copacului nu ar trebui să existe substraturi goale.
- Frunzele copacului trebuie să vină la același nivel.
- Toate nodurile ar trebui să aibă cel puțin un număr de copii, cu excepția nodurilor care părăsesc.
Proprietățile arborelui B de comandă M
- Fiecare nod poate avea un număr maxim de copii M și un număr minim de copii M / 2 sau un număr de la 2 la maximum.
- Fiecare nod are o cheie mai mică decât copiii cu chei maxime M-1.
- Aranjamentul cheilor este în ordine specifică în cadrul nodurilor. Toate cheile din subfaza prezente în partea stângă a cheii sunt predecesoare ale cheii și cele prezente în partea dreaptă a cheii sunt numite succesoare.
- La momentul inserării unui nod complet, arborele se împarte în două părți, iar cheia cu valoarea mediană este inserată la nodul părinte.
- Operația de fuziune are loc când nodurile sunt șterse.
Definiția Binary tree
Un arbore binar este o structură de copac care poate avea cel mult două indicatoare pentru nodurile copilului său. Înseamnă că cel mai înalt grad pe care un nod poate avea este 2 și ar putea exista și nod de zero sau un grad.
Există anumite variante ale unui arbore binar, cum ar fi arborele binar strict, arborele binar complet, arborele binar extins etc.
- Arborele strict binar este un arbore în care fiecare nod neterminal trebuie să fi lăsat subtree și subtree dreapta.
- Un arbore este numit un arbore binar complet atunci când acesta satisface condiția de a avea 2 noduri i la fiecare nivel unde i este nivelul.
- Threaded binary este un arbore binar care constă fie din 0 nu de noduri, fie din 2 noduri.
Tehnici de traversare
Tree traversal este una dintre cele mai frecvente operațiuni efectuate pe structura de date arborescentă în care fiecare nod a vizitat exact o dată într-un mod sistematic.
- Inorder- În acest arbore traversal, subtree-ul stâng este vizitat recursiv, apoi nodul rădăcină este vizitat și în ultimul subrust drept este vizitat.
- Preorer - În acest arbore traversal nodul rădăcină este vizitat la primul substrat în stânga și la ultimul subrubric drept.
- Postorder - Această tehnică vizitează substratul stâng, apoi subtreea dreaptă și ultimul nod rădăcină.
Diferențe cheie între arborele B și arborele binar
- În arborele B, numărul maxim de noduri copil pe care un nod non-terminal poate avea este M unde M este ordinea arborelui B. Pe de altă parte, un arbore binar poate avea cel mult două subrețe sau noduri copil.
- B-tree-ul este folosit atunci când datele sunt stocate pe disc, în timp ce arborele binar este utilizat atunci când datele sunt stocate în memorie rapidă ca RAM.
- Un alt domeniu de aplicare pentru B-tree este structura de indexare a codului în DBMS, în schimb, arborele binar este utilizat în optimizarea codului, codificarea huffman etc.
- Înălțimea maximă a unui arbore B este log M N (M este ordinea arborelui). În comparație, înălțimea maximă a copacului binar este log 2 N (N este numărul de noduri și baza este 2 deoarece este pentru binar).
Concluzie
B-tree-ul este folosit peste arborele de căutare binar și binar principalul motiv din spatele acestuia este ierarhia de memorie unde CPU-ul este conectat la cache cu canalele de lățime de bandă ridicată în timp ce CPU-ul este conectat la disc prin canal de bandă mică. Un arbore binar este utilizat atunci când înregistrările sunt stocate în RAM (mici și rapide) și B-tree sunt folosite atunci când înregistrările sunt stocate pe disc (mari și lente). Deci, utilizarea copacului B în locul copacului binar reduce semnificativ timpul de acces datorită factorului de ramificare ridicat și înălțimii reduse a copacului.
