Forskel mellem B-træ og Binært træ
Indhold
- Sammenligningstabel
- Definition af B-træ
- Egenskaber ved B-træ af ordre M
- Definition af binært træ
- Traversal teknikker
- Konklusion
B-træ og Binært træ er typerne af ikke-lineær datastruktur. Selvom udtrykkene synes at være ens, men er forskellige i alle aspekter. Et binært træ bruges, når posterne eller dataene gemmes i RAM i stedet for disk, da adgangshastigheden til RAM er meget højere end disken. På den anden side bruges B-træ, når dataene er lagret på disken, det reducerer adgangstiden ved at reducere træets højde og øge grenene i noden.
En anden forskel mellem B-træet og det binære træ er, at B-træet skal have alle sine underordnede knudepunkter på samme niveau, hvorimod det binære træ ikke har sådan begrænsning. Et binært træ kan have maksimalt 2 undertræer eller -knudepunkter, mens i B-træet kan have M intet af undertræer eller knuder, hvor M er rækkefølgen af B-træet.
- Sammenligningstabel
- Definition
- Vigtige forskelle
- Konklusion
Sammenligningstabel
| Grundlag for sammenligning | B-træ | Binært træ |
|---|---|---|
| Væsentlig begrænsning | En knude kan have et maksimalt M antal børneknuder (hvor M er træets rækkefølge). | En knude kan have maksimalt 2 antal undertræer. |
| Brugt | Det bruges, når data gemmes på disken. | Det bruges, når poster og data gemmes i RAM. |
| Træets højde | logM N (hvor m er rækkefølgen af M-veetræet) | log2 N |
| Ansøgning | Kodeindeksering af datastruktur i mange DBMS. | Kodeoptimering, Huffman-kodning osv. |
Definition af B-træ
Et B-træ er det afbalancerede M-vejetræ og også kendt som det afbalancerede sorteringstræ. Det ligner binært søgetræ, hvor knudepunkterne er organiseret på grundlag af grænseovergang. Rum-kompleksiteten af B-træ er O (n). Indsættelse og sletningstidskompleksitet er O (log n).
Der er visse betingelser, der skal være gældende for et B-træ:
- Træets højde skal ligge mindst mulig.
- Over træets blade skal der ikke være tomme undertræer.
- Træets blade skal komme på samme niveau.
- Alle knudepunkter skal have mindst antal børn undtagen forladte knudepunkter.
Egenskaber ved B-træ af ordre M
- Hver knude kan have et maksimalt M-antal børn og mindst M / 2-antal børn eller et hvilket som helst antal fra 2 til det maksimale.
- Hver knude har en nøgle mindre end børn med maksimale M-1 nøgler.
- Arrangementet af tasterne er i en bestemt rækkefølge inden for noder. Alle taster i undertræet, der findes i venstre side af nøglen, er forgængere af nøglen, og de der findes til højre for nøglen kaldes efterfølgere.
- På tidspunktet for indsættelse af en fuld knude opdeles træet i to dele, og nøglen med medianværdi indsættes ved overordnede knudepunkter.
- Sammensmeltning sker, når noderne slettes.
Definition af binært træ
Et binært træ er en træstruktur, der højst kan have to pegepunkter til dets barneknuder. Det betyder, at den højeste grad, en knude kan have, er 2, og at der også kan være nul eller en-graders knude.
Der er visse varianter af et binært træ såsom strengt binært træ, komplet binært træ, udvidet binært træ osv.
- Det strengt binære træ er et træ, hvor hver ikke-terminal node skal have venstre undertre og højre undertre.
- Et træ kaldes et komplet binært træ, når det opfylder betingelsen om at have 2 jeg noder på hvert niveau, hvor i er niveauet.
- Binært gevind er et binært træ, der består af enten 0 antal knudepunkter eller 2 antal knudepunkter.
Traversal teknikker
Træovergang er en af de hyppigste operationer, der udføres på trædatastruktur, hvor hver knude besøgte nøjagtigt en gang på en systematisk måde.
- Inorder- I dette træstræning besøges den venstre undertræ rekursivt, derefter besøges rodnoden og i sidste højre undertre besøges.
- Preorer- I dette træstræning besøges rodnoden først og derefter til venstre undertre og til sidst til højre undertre.
- Postorder - Denne teknik besøger venstre underskrift og derefter højre undertre og sidst rodnode.
- I B-træ er det maksimale antal børnknudepunkter, som en ikke-terminal knude kan have, M, hvor M er rækkefølgen af B-træet. På den anden side kan et binært træ højst have to undertræer eller underordnede knudepunkter.
- B-træ bruges, når data gemmes på disken, mens binært træ bruges, når data gemmes i hurtig hukommelse som RAM.
- Et andet anvendelsesområde for B-træ er kodeindeksering af datastruktur i DBMS, i modsætning hertil benyttes Binært træ til kodeoptimering, huffman-kodning osv.
- Den maksimale højde på et B-træ er logMN (M er træets rækkefølge). I modsætning hertil er binær træets maksimale højde log2N (N er antallet af noder, og basen er 2, fordi den er til binær).
Konklusion
B-træet bruges over binært og binært søgetræ, hovedårsagen til dette er hukommelseshierarkiet, hvor CPU er forbundet til cache med kanalerne med høj båndbredde, mens CPU er tilsluttet til disk gennem kanal med lav båndbredde. Et binært træ bruges, når poster gemmes i RAM (lille og hurtig) og B-træ bruges, når poster gemmes på disk (stor og langsom). Så brug af B-træ i stedet for Binært træ reducerer adgangstiden markant på grund af høj forgreningsfaktor og reduceret træhøjde.
