Innehåll

• Jämförelsediagram
• Definition av B-träd
• Egenskaper hos B-träd av ordning M
• Definition av binärt träd
• Traversal tekniker
• Slutsats

B-träd och binärt träd är de typer av icke-linjär datastruktur. Även om termerna verkar vara lika men är olika i alla aspekter. Ett binärt träd används när posten eller datan lagras i RAM i stället för disken eftersom åtkomsthastigheten för RAM är mycket högre än disken. Å andra sidan används B-träd när data lagras på disken, det minskar åtkomsttiden genom att minska trädets höjd och öka grenarna i noden.

En annan skillnad mellan B-trädet och det binära trädet är att B-trädet måste ha alla sina barnnoder på samma nivå medan det binära trädet inte har sådan begränsning. Ett binärt träd kan ha högst 2 underträd eller noder medan i B-trädet kan ha M inget underträd eller noder där M är B-trädets ordning.

1. Jämförelsediagram
2. Definition
3. Viktiga skillnader
4. Slutsats

Jämförelsediagram

Grund för jämförelse	B-träd	Binärt träd
Väsentlig begränsning	En nod kan ha max M-antal barnnoder (där M är trädets ordning).	En nod kan ha max 2 antal underträd.
Begagnade	Det används när data lagras på disken.	Det används när poster och data lagras i RAM.
Trädets höjd	loggaM N (där m är ordningen för M-vägträdet)	logga2 N
Ansökan	Kodindexering av datastruktur i många DBMS.	Kodoptimering, Huffman-kodning, etc.

Definition av B-träd

Ett B-träd är det balanserade M-sättsträdet och även känt som det balanserade sorteringsträdet. Det liknar binärt sökträd där noderna är organiserade på grundval av inorder traversal. Rymdkomplexiteten hos B-träd är O (n). Införing och borttagningstidskomplexitet är O (log n).

Det finns vissa villkor som måste vara sant för ett B-träd:

• Trädets höjd måste ligga så minimal som möjligt.
• Ovanför trädets löv bör det inte finnas några tomma underträd.
• Trädets löv måste komma på samma nivå.
• Alla noder ska ha minst antal barn utom lämna noder.

Egenskaper hos B-träd av ordning M

• Varje nod kan ha maximalt M-antal barn och minimum M / 2-antal barn eller valfritt antal från 2 till det maximala.
• Varje nod har en knapp mindre än barn med maximala M-1-nycklar.
• Arrangemanget av nycklarna är i någon specifik ordning inom noderna. Alla tangenter i underträdet som finns till vänster om nyckeln är föregångare till nyckeln, och de som finns till höger om nyckeln kallas efterföljare.
• Vid tidpunkten för införandet av en fullständig nod delas trädet i två delar och nyckeln med medianvärdet sätts in i modernoden.
• Sammanfogning 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 engraders nod.

Det finns vissa varianter av ett binärt träd som strikt binärt träd, komplett binärt träd, utökat binärt träd etc.

• Det strikt binära trädet är ett träd där varje icke-terminal nod måste ha vänster undertråd och höger 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 i är nivån.
• Threaded binär är ett binärt träd som består av antingen 0 nr av noder eller 2 antal noder.

Traversal tekniker

Trädomgång är en av de vanligaste operationerna som utförs på träddatastrukturen där varje nod besöker exakt en gång på ett systematiskt sätt.

• Inorder- I denna trädkorsning besöks den vänstra undertråden rekursivt då besökas rotnoden och i sista höger undertråd besöks.
• Preorer- I denna trädkorsning besöks rotnoden först sedan vänster undertråd och till sist höger undertråd.
• Postorder- Den här tekniken besöker vänster subtree sedan höger subtree och till sist rotnod.

1. I B-träd är det maximala antalet barnnoder som en icke-terminal nod kan ha M där M är B-trädets ordning. Å andra sidan kan ett binärt träd ha högst två underträd eller barnnoder.
2. B-träd används när data lagras på disk medan binärt träd används när data lagras i snabbminne som RAM.
3. Ett annat användningsområde för B-träd är kodindexering av datastrukturen i DBMS, däremot används binärt träd för kodoptimering, huffman-kodning, etc.
4. B-trädets maximala höjd är logg_MN (M är trädets ordning). I motsats till är binär trädets maximala höjd logg₂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äd. Det främsta skälet bakom detta är minneshierarkin där CPU är ansluten till cache med kanalerna med hög bandbredd medan CPU är ansluten till disk genom kanal med låg bandbredd. 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 på disken (stor och långsam). Så användningen av B-träd istället för Binärt träd minskar åtkomsttiden betydligt på grund av hög förgreningsfaktor och minskad trädhöjd.