En annen forskjell mellom B-treet og det binære treet er at B-treet må ha alle sine barnnoder på samme nivå, mens binært tre ikke har en slik begrensning. Et binært tre kan ha maksimalt 2 subtreer eller noder, mens det i B-tre kan ha M ingen av subtreer eller noder der M er rekkefølgen til B-treet.
Sammenligningstabel
| Grunnlag for sammenligning | B-tree | Binært tre |
|---|---|---|
| Viktig begrensning | En knute kan ha på maks M antall barnnoder (hvor M er rekkefølgen til treet). | En knute kan ha maksimalt 2 antall subtreer. |
| brukes | Den brukes når data lagres på disken. | Den brukes når poster og data lagres i RAM. |
| Høyde på treet | logg M N (hvor m er rekkefølgen på M-veistreet) | logg 2 N |
| applikasjon | Kode indeksering datastruktur i mange DBMS. | Kodeoptimalisering, Huffman-koding, etc. |
Definisjon av B-tre
Et B-tre er det balansert M-veistreet og også kjent som det balansert sorterte treet. Det ligner på binært søketre der nesene er organisert på grunnlag av inorder-traversal. B-treets kompleksitet er O (n). Innsetting og slettingstidskompleksitet er O (log n).
Det er visse forhold som må være sant for et B-tre:
- Høyden på treet må ligge så lavt som mulig.
- Over blomstene på treet, bør det ikke være noen tomme subtreer.
- Bladene på treet må komme på samme nivå.
- Alle noder skal ha minst antall barn unntatt forlate noder.
Egenskaper for B-tre av ordre M
- Hver knute kan ha maksimalt antall M antall barn og minimum M / 2 antall barn eller et tall fra 2 til maksimum.
- Hver knute har en nøkkel mindre enn barn med maksimale M-1-taster.
- Ordningen av nøklene er i en bestemt rekkefølge i noderne. Alle nøkler i subtree-presentet til venstre for nøkkelen er forgjengere av nøkkelen, og det til stede i høyre side av nøkkelen kalles etterfølgere.
- På tidspunktet for innsetting av en hel knutepunkt, splittes treet i to deler, og nøkkelen med medianverdi er satt inn på foreldre node.
- Sammenslåingen foregår når nodene slettes.
Definisjon av binært tre
Et binært tre er en trestruktur som kan ha høyst to pointers for sine barnnoder. Det betyr at den høyeste graden en node kan ha er 2, og det kan også være null eller en-grader node.
Det er visse varianter av et binært tre som strengt binært tre, komplett binært tre, utvidet binærtre, etc.
- Det strengt binære treet er et tre hvor hver ikke-terminale node må ha forlatt deltre og høyre undertrinn.
- Et tre kalles et komplett binært tre når det tilfredsstiller betingelsen om å ha 2 jeg noder på hvert nivå hvor jeg er nivået.
- Gjenget binært er et binært tre som består av enten 0 noder eller 2 noder.
Traversal Techniques
Tree-traversal er en av de hyppigste operasjonene som utføres på tredata struktur hvor hver node besøkte nøyaktig en gang på en systematisk måte.
- Inorder-I dette treet traversal er venstre undertreet besøkt rekursivt, deretter blir rotnoden besøkt og i siste høyre undertreet er besøkt.
- Preorer- I dette treet traversal blir rotnoden besøkt først da venstre undertreet og til slutt høyre undertreet.
- Postorder-Denne teknikken besøker venstre subtree deretter høyre subtree og til slutt root node.
Viktige forskjeller mellom B-tre og binært tre
- I B-treet kan det maksimale antall barnnoder som en ikke-terminal node har, er M hvor M er rekkefølgen til B-treet. På den annen side kan et binært tre ha maksimalt to subtre eller barnnoder.
- B-tre brukes når data lagres i disk mens binær tre brukes når data lagres i hurtigminne som RAM.
- Et annet område for søknad for B-tre er kodeindeksering datastruktur i DBMS, i kontrast, Binært tre er ansatt i kodeoptimalisering, huffman-koding, etc.
- Maksimum høyde på et B-tre er log M N (M er rekkefølgen til treet). Imidlertid er binær tre maksimal høyde log 2 N (N er antall noder og base er 2 fordi den er for binær).
Konklusjon
B-treet brukes over binært og binært søketre. Hovedårsaken bak dette er minneshierarkiet hvor CPU er koblet til cache med høybåndsbreddekanaler mens CPU er koblet til disk via lav båndbreddekanal. Et binært tre brukes når arkiver lagres i RAM (liten og rask) og B-tre brukes når poster lagres i disken (stor og sakte). Så, bruk av B-tre i stedet for Binært tre reduserer betydelig tilgangstid på grunn av høy forgreningsfaktor og redusert høyde på treet.
