En annan skillnad mellan B-trädet och det binära trädet är att B-träd måste ha alla sina barnnoder på samma nivå medan binärt träd inte har sådan begränsning. Ett binärt träd kan ha maximalt 2 subtre eller noder, medan i B-träd kan ha M inga subtreer eller noder där M är B-trädets ordning.
Jämförelsediagram
| Grunder för jämförelse | B-träd | Binärt träd |
|---|---|---|
| Nödvändig begränsning | En nod kan ha vid max M antal barnnoder (där M är trädets ordning). | En nod kan ha max 2 antal subtre. |
| Begagnade | Den används när data lagras på disken. | Den används när poster och data lagras i RAM. |
| Träets höjd | logga M N (där m är M-way-trädets ordning) | logg 2 N |
| Ansökan | Kod indexering datastruktur i många DBMS. | Kodoptimering, Huffman kodning etc. |
Definition av B-träd
Ett B-träd är det balanserade M-way-trädet och även känt som ett balanserat sortträd. Det liknar binärt sökande träd där noderna organiseras på grundval av inorder-traversal. B-trädets rymdkomplexitet är O (n). Infogning och borttagningstidskomplexitet är O (log n).
Det finns vissa villkor som måste vara sanna för ett B-träd:
- Trädets höjd måste ligga så minimalt som möjligt.
- Över trädets löv borde det inte finnas några tomma subtre.
- Trädens löv måste komma på samma nivå.
- Alla noder borde ha minst antal barn utom att lämna noder.
Egenskaper för B-träd i ordning M
- Varje nod kan ha maximalt antal M antal barn och minsta antal M / 2 barn eller något antal från 2 till maximalt.
- Varje nod har en nyckel mindre än barn med maximala M-1-tangenter.
- Ordningen av nycklarna ligger i någon specifik ordning inom noderna. Alla nycklar i delträdet till vänster om nyckeln är föregångare till nyckeln, och det som finns till höger om nyckeln kallas efterträdare.
- Vid införandet av en hel nod splittras trädet i två delar, och nyckeln med medianvärdet sätts in vid parentnoden.
- Sammanslagning sker när noderna raderas.
Definition av binärt träd
Ett binärt träd är en trädstruktur som kan ha högst två pekare för sina barnnoder. Det betyder att den högsta graden en nod kan ha är 2 och det kan också vara noll eller en grader nod.
Det finns vissa varianter av ett binärt träd, såsom strikt binärt träd, komplett binärt träd, förlängt binärt träd etc.
- Det strängt binära trädet är ett träd där varje icke-terminal nod måste ha lämnat subtree och right subtree.
- Ett träd kallas ett komplett binärt träd när det uppfyller villkoret att ha 2 jag noder på varje nivå där jag är nivån.
- Gängat binärt är ett binärt träd som består av antingen 0 noder eller 2 antal noder.
Traversal Techniques
Trädkorsning är en av de vanligaste operationerna som utförs på träddatastrukturen där varje nod besökte exakt en gång på ett systematiskt sätt.
- Inorder-I detta träd traversal vänster subtree besökas rekursivt sedan rot nod besöks och i sista höger delträdet besöks.
- Preorer-I detta träd traversal är rotknutpunkten besökt först då vänster subtree och till sist höger subtree.
- Postorder-Denna teknik besöker vänster subtree då höger subtree och till sist root node.
Viktiga skillnader mellan B-träd och binärt träd
- I B-träd kan det maximala antalet barnnoder som en icke-terminal nod har, är M där M är B-trädets ordning. Å andra sidan kan ett binärt träd ha högst två subtre eller barnnoder.
- B-träd används när data lagras i disken medan binärt träd används när data lagras i snabbminnet som RAM.
- Ett annat användningsområde för B-träd är kodindexeringsdatastrukturen i DBMS, däremot är binärt träd anställt i kodoptimering, huffman-kodning etc.
- B-trädets maximala höjd är logg M N (M är trädets ordning). Däremot är binärt träd högsta höjd log 2 N (N är antalet noder och basen är 2 eftersom den är för binär).
Slutsats
B-trädet används över binärt och binärt sökträde. Huvudskälet bakom detta är minneshierarkin där CPU är ansluten till cache med högbandbreddskanalerna medan CPU är ansluten till disk via låg bandbreddskanal. Ett binärt träd används när poster lagras i RAM (liten och snabb) och B-träd används när poster lagras i disken (stor och långsam). Så, användningen av B-träd i stället för binärt träd minskar avsevärt åtkomsttiden på grund av hög förgreningsfaktor och minskad höjd av trädet.
