B-drevo vs Binarno drevo
Vsebina
- Vsebina: Razlika med B-drevo in Binarnim drevesom
- Primerjalna tabela
- B-drevo
- Binarno drevo
- Ključne razlike
- Zaključek
- Pojasnjevalni video
Razlika med B-drevesnim in binarnim drevesom je v tem, da je B-drevo razvrščeno drevo, kjer so vozlišča razvrščena po vrstnem redu, medtem ko je binarno drevo urejeno drevo s kazalcem na vsakem vozlišču.
Podatkovne strukture so najpomembnejši pojmi v računalniškem programiranju, v podatkovnih strukturah pa sta najpomembnejša pojma B-tree in Binary tree. Oba se razlikujeta drug od drugega. B-drevo je razvrščeno drevo, kjer so vozlišča razvrščena po vrstnem redu, medtem ko je binarno drevo urejeno drevo s kazalcem na vsakem vozlišču. B-drevo in binarno drevo sta nelinearni podatkovni strukturi. Oba pojma se po imenu zdita enaka, vendar nista enaka, saj sta različna. Binarna koda drevesa je shranjena v RAM-u, medtem ko je koda B-drevesa shranjena na disku.
B-drevo je M-way drevo, ki je uravnoteženo, B-drevo je znano kot drevo uravnotežene sorte. V B-drevesu je notranja prečka. Prostornost kompleksnosti B-drevesa je O (n). Časovna zapletenost vstavljanja in brisanja je O (log n). V B-drevesu mora biti višina drevesa čim manjša. V B-drevesu ne bi smelo biti prazno poddrevo. Vsi listi drevesa naj bodo na isti ravni. Vsako vozlišče ima največ M otrok in minimalno M / 2 število otrok. Vsako vozlišče v B-drevesu mora imeti manj ključa kot podrejeni ključ. V drevesu B so ključi v podrehiji, ki so na levi strani tipke, predhodniki. Ko je vozlišče polno in poskusite vstaviti novo vozlišče, je drevo razdeljeno na dva dela. Vozlišča lahko združite v B-drevesu, dokler vozlišča niso izbrisana.
Binarno drevo ima dva kazalca, ki vsebujeta naslov svojih podrejenih vozlišč. Obstajajo vrste binarnih dreves, kot je strogo binarno drevo, popolno binarno drevo, razširjeno binarno drevo itd. V strogo binarnem drevesu morata biti levo poddrevo in desno poddrevo, v celotnem binarnem drevesu morata biti dve vozlišči na na vsaki ravni, v binarnem drevesu z navojem pa naj bo 0 do 2 število vozlišč. Če govorimo o prečnih tehnikah, so tri transverzalne tehnike v vrstnem redu prečna, preredna prečna in pokončna transverzalna.
Vsebina: Razlika med B-drevo in Binarnim drevesom
- Primerjalna tabela
- B-drevo
- Binarno drevo
- Ključne razlike
- Zaključek
- Pojasnjevalni video
Primerjalna tabela
Osnove | B-drevo | Binarno drevo |
Osnove | B-drevo je razvrščeno drevo, kjer so vozlišča razvrščena v prečkanju. | Binarno drevo je urejeno drevo s kazalcem na vsakem vozlišču. |
Trgovina | Koda B-drevesa je shranjena na disku. | Binarna koda drevesa je shranjena v RAM-u |
Višina | Višina B-drevesa bo log N | Višina binarnega drevesa bo dnevnik2 N |
Uporaba | DBMS je aplikacija B-drevesa. | Huffmanovo kodiranje je aplikacija Binary Tree. |
B-drevo
B-drevo je M-way drevo, ki je uravnoteženo, B-drevo je znano kot drevo uravnotežene sorte. V B-drevesu je notranja prečka. Prostornost kompleksnosti B-drevesa je O (n). Časovna zapletenost vstavljanja in brisanja je O (log n). V B-drevesu mora biti višina drevesa čim manjša.
V B-drevesu ne bi smelo biti prazno poddrevo. Vsi listi drevesa naj bodo na isti ravni. Vsako vozlišče ima največ M otrok in najmanj M / 2 število otrok. Vsako vozlišče v B-drevesu mora imeti manj ključa kot podrejeni ključ. V drevesu B so ključi v podrehiji, ki so na levi strani tipke, predhodniki. Ko je vozlišče polno in poskusite vstaviti novo vozlišče, je drevo razdeljeno na dva dela. Vozlišča lahko združite v B-drevesu, dokler vozlišča niso izbrisana.
Binarno drevo
Binarno drevo ima dva kazalca, ki vsebujeta naslov svojih podrejenih vozlišč. Obstajajo vrste binarnih dreves, kot je strogo binarno drevo, popolno binarno drevo, razširjeno binarno drevo itd.
V strogo binarnem drevesu morata biti levo podreje in desno podreje, v celotnem binarnem drevesu naj bosta na vsaki ravni dve vozlišči, v navojnem binarnem drevesu pa naj bo od 0 do 2 število vozlišč. Če govorimo o transverzalnih tehnikah, obstajajo tri prečne tehnike, ki so po vrstnem redu prečna, preredna prečna in transverzalna po naročilu.
Ključne razlike
- B-drevo je razvrščeno drevo, pri katerem so vozlišča razvrščena v vrstnem redu, medtem ko je Binarno drevo urejeno drevo s kazalcem na vsakem vozlišču.
- Koda B-drevesa je shranjena na disku, medtem ko je binarna koda drevesa shranjena v RAM-u.
- Višina B-drevesa bo logN, višina binarnega drevesa pa bo log2 N
- DBMS je aplikacija B-drevesa, medtem ko je Huffmanovo kodiranje aplikacija Binary Tree.
Zaključek
V tem članku zgoraj vidimo jasno razliko med B-tree in Binary tree z njihovo izvedbo.