Forskjellen mellom B-tre og Binærtre
Innhold
- Sammenligningstabell
- Definisjon av B-tre
- Egenskaper ved B-tre av ordre M
- Definisjon av Binærtre
- Gjennomgangsteknikker
- Konklusjon
B-tre og Binærtre er typene av ikke-lineær datastruktur. Selv om begrepene ser ut til å være like, men er forskjellige i alle aspekter. Et binært tre brukes når postene eller dataene er lagret i RAM i stedet for disk ettersom tilgangshastigheten til RAM er mye høyere enn disken. På den annen side brukes B-tre når dataene er lagret på disken, det reduserer tilgangstiden ved å redusere høyden på treet og øke grenene i noden.
En annen forskjell mellom B-treet og det binære treet er at B-treet må ha alle barneknuter på samme nivå, mens binærtreet ikke har en slik begrensning. Et binært tre kan ha maksimalt 2 undertrær eller noder, mens det i B-tre kan ha M ingen av undertrær eller noder der M er rekkefølgen på B-treet.
- Sammenligningstabell
- Definisjon
- Viktige forskjeller
- Konklusjon
Sammenligningstabell
| Grunnlag for sammenligning | B-tree | Binærtre |
|---|---|---|
| Vesentlig begrensning | En node kan ha maksimalt M antall barneknuter (der M er treetes rekkefølge). | En nod kan ha maks 2 antall undertrær. |
| brukes | Det brukes når data lagres på disken. | Det brukes når poster og data lagres i RAM. |
| Treets høyde | LoggM N (hvor m er rekkefølgen på M-veistreet) | Logg2 N |
| applikasjon | Kodeindeksering av datastruktur i mange DBMS. | Kodeoptimalisering, Huffman-koding, etc. |
Definisjon av B-tre
Et B-tre er det balanserte M-veietreet og også kjent som det balanserte sorteringstreet. Det ligner på binært søketre der nodene er organisert på grunnlag av grenseovergang. Plasskompleksiteten til B-tre er O (n). Kompleksitet for innsetting og sletting er O (log n).
Det er visse forhold som må stemme for et B-tre:
- Høyden på treet må ligge minst mulig.
- Over bladene på treet skal det ikke være noen tomme undertrær.
- Bladene på treet må komme på samme nivå.
- Alle noder skal ha minst antall barn, bortsett fra la noder.
Egenskaper ved B-tre av ordre M
- Hver node kan ha maksimalt M antall barn og minimum M / 2 antall barn eller et hvilket som helst antall fra 2 til det maksimale.
- Hver node har en tast mindre enn barn med maksimale M-1 nøkler.
- Ordningen av tastene er i en bestemt rekkefølge innenfor nodene. Alle tastene i undertreet som er til venstre for tasten er forgjengerne av nøkkelen, og de som er til høyre for tasten kalles etterfølgere.
- På tidspunktet for innføring av en fullstendig node, deler treet seg i to deler, og nøkkelen med medianverdi settes inn på overordnede noder.
- Sammenslåing skjer når nodene blir slettet.
Definisjon av Binærtre
Et binært tre er en trestruktur som maksimalt kan ha to pekepinner for sine barneknuter. Det betyr at den høyeste graden en node kan ha er 2 og det kan være null eller en-graders node også.
Det er visse varianter av et binærtre som strengt binært tre, komplett binærtre, utvidet binærtre osv.
- Det strengt binære treet er et tre der hver ikke-terminal node må ha venstre undertre og høyre undertrinn.
- Et tre kalles et komplett binærtre når det tilfredsstiller betingelsen om å ha 2 Jeg noder på hvert nivå der jeg er nivået.
- Gjenget binært er et binært tre som består av enten 0 antall noder eller 2 antall noder.
Gjennomgangsteknikker
Treovergang er en av de hyppigste operasjoner som er utført på tredatastruktur der hver node besøkte nøyaktig en gang på en systematisk måte.
- Inorder- I denne treomgangen besøkes venstre undertråd rekursivt og deretter besøkes rotnode og i siste høyre høyre undertree besøkes.
- Preorer- I denne treversjonen besøkes rotnoden først og deretter til venstre undertrinn og til sist høyre undertree.
- Postorder - Denne teknikken besøker venstre undertre og deretter høyre undertre og til sist rotnode.
- I B-tre er det maksimale antall barneknuter en ikke-terminal node kan ha M der M er rekkefølgen på B-treet. På den annen side kan et binært tre ha høyst to undertrær eller barneknuter.
- B-tre brukes når data er lagret på disk mens binært tre brukes når data lagres i hurtigminne som RAM.
- Et annet bruksområde for B-tre er kodeindeksering av datastruktur i DBMS, derimot benyttes Binærtre i kodeoptimalisering, huffman-koding, etc.
- Maksimal høyde på et B-tre er loggenMN (M er rekkefølgen på tre). I motsetning er maksimal høyde for binært tre2N (N er antall noder og basen er 2 fordi den er for binær).
Konklusjon
B-treet brukes over binært og binært søketre. Hovedårsaken til dette er minnehierarkiet der CPU er koblet til cache med høye båndbreddekanaler mens CPU er koblet til disk gjennom kanal med lav båndbredde. Et binært tre brukes når poster er lagret i RAM (liten og rask) og B-tre brukes når poster er lagret på disk (stor og treg). Så bruk av B-tre i stedet for Binært tre reduserer tilgangstiden betydelig på grunn av høy forgreningsfaktor og redusert høyde på treet.
