Sisu

• Võrdlusdiagramm
• B-puu määratlus
• B-puu omadused järjekorras M
• Binaarse puu määratlus
• Läbiviimise tehnikad
• Järeldus

B-puu ja binaarne puu on mittelineaarse andmestruktuuri tüübid. Mõisted näivad küll sarnased, kuid on kõigis aspektides erinevad. Binaarset puud kasutatakse siis, kui kirjeid või andmeid hoitakse ketta asemel RAM-is, kuna RAM-i juurdepääsu kiirus on palju suurem kui kettal. Teisest küljest kasutatakse B-puud andmete salvestamisel kettale. See vähendab juurdepääsu aega, vähendades puu kõrgust ja suurendades okste sõlme.

Veel üks erinevus B-puu ja binaarse puu vahel on see, et B-puul peavad kõik selle lastesõlmed olema samal tasemel, samas kui binaarsel puul pole sellist piirangut. Binaarsel puul võib olla maksimaalselt 2 alampuud või sõlme, samas kui B-puul võib olla M mitte ühtegi alampuud või -sõlme, kus M on B-puu järjekord.

1. Võrdlusdiagramm
2. Definitsioon
3. Peamised erinevused
4. Järeldus

Võrdlusdiagramm

Võrdluse alus	B-puu	Binaarne puu
Oluline piirang	Sõlmel võib olla maksimaalselt M lapsesõlmede arvu (kus M on puu järjekord).	Sõlmel võib olla maksimaalselt 2 arvu alamtreid.
Kasutatud	Seda kasutatakse andmete kettale salvestamisel.	Seda kasutatakse siis, kui dokumendid ja andmed on salvestatud RAM-i.
Puu kõrgus	logiM N (kus m on M-suuna puu järjekord)	logi2 N
Rakendus	Koodide indekseerimise andmestruktuur paljudes DBMS-ides.	Koodide optimeerimine, Huffmani kodeerimine jne

B-puu määratlus

B-puu on tasakaalustatud M-tee puu ja tuntud ka kui tasakaalustatud sortimispuu. See sarnaneb binaarse otsimispuuga, kus sõlmed on korraldatud sissetungija liikumise alusel. B-puu ruumi keerukus on O (n). Sisestamise ja kustutamise aja keerukus on O (log n).

B-puu puhul peavad kehtima teatud tingimused:

• Puu kõrgus peab olema võimalikult väike.
• Puu lehtede kohal ei tohiks olla ühtegi tühja alajagu.
• Puu lehed peavad olema samal tasemel.
• Kõigil sõlmedel peaks olema kõige vähem lapsi, välja arvatud lahkusõlmed.

B-puu omadused järjekorras M

• Igas sõlmes võib olla maksimaalselt M laste arvu ja minimaalselt M / 2 laste arvu või mis tahes arv 2 kuni maksimum.
• Igas sõlmes on üks võti vähem kui maksimaalselt M-1 klahvidega lastel.
• Klahvide paigutus on sõlmedes mingis kindlas järjekorras. Kõik võtme vasakpoolses osas paiknevad subreede klahvid on klahvi eelkäijad ja klahvi paremal olevaid klahve nimetatakse järglasteks.
• Terve sõlme sisestamise ajal lõheneb puu kaheks osaks ja mediaanväärtusega võti sisestatakse vanema sõlme.
• Ühendamine toimub pärast sõlmede kustutamist.

Binaarse puu määratlus

Binaarne puu on puustruktuur, millel võib olla lapsesõlmede jaoks maksimaalselt kaks osutust. See tähendab, et kõrgeim aste, mida sõlmel võib olla, on 2 ja seal võib olla ka null või ühe kraadine sõlm.

Binaarsel puul on teatud variandid, näiteks rangelt binaarne puu, täielik binaarne puu, laiendatud binaarne puu jne.

• Rangelt binaarne puu on puu, kus igal mitteterminalilisel sõlmel peab olema vasakpoolne alam- ja parem alampuu.
• Puu nimetatakse täielikuks binaarseks puuks, kui see vastab tingimusele, et sellel on 2 ⁱ sõlmed igal tasandil, kus i on tase.
• Keermestatud binaarne on binaarne puu, mis koosneb kas 0 sõlmede arvust või 2 arvust sõlmedest.

Läbiviimise tehnikad

Puu liikumine on üks kõige sagedasemaid toiminguid puu andmestruktuuril, kus iga sõlm külastas süstemaatiliselt täpselt üks kord.

• Inorder - selles puus läbitakse vasakpoolne alamtuul rekursiivselt, seejärel külastatakse juursõlme ja külastatakse viimast paremat alampuitu.
• Eelsõitja - selle puu läbimisel külastatakse juursõlme alguses, seejärel vasakus alampunktis ja viimases paremas alampuu.
• Postorder - see tehnika külastab vasakut alammenüüd, siis paremat alammenüüd ja viimases juursõlme.

1. B-puus võib mitte-terminaalsõlmes olla maksimaalne lapsesõlmede arv M, kus M on B-puu järjekord. Teisest küljest võib binaarsel puul olla maksimaalselt kaks alam- või alamsõlme.
2. B-puud kasutatakse siis, kui andmeid hoitakse kettal, samas kui binaarset puud kasutatakse siis, kui andmeid hoitakse kiirsmälus nagu RAM.
3. Veel üks B-puu kasutusvaldkond on koodide indekseerimine andmestruktuuris DBMS-is, vastupidiselt kasutatakse binaarset puud koodide optimeerimisel, huffmani kodeerimisel jne.
4. B-puu maksimaalne kõrgus on log_MN (M on puu järjekord). Vastupidiselt sellele on binaarse puu maksimaalne kõrgus log₂N (N on sõlmede arv ja alus on 2, kuna see on binaarne).

Järeldus

B-puud kasutatakse binaarse ja binaarse otsingupuu kohal. Selle peamiseks põhjuseks on mäluhierarhia, kus CPU on ühendatud suure ribalaiusega kanalitega vahemäluga, samal ajal kui CPU on ühendatud kettaga väikese ribalaiusega kanali kaudu. Binaarset puud kasutatakse juhul, kui kirjeid hoitakse RAM-is (väike ja kiire), ja B-puud, kui kirjeid säilitatakse kettal (suur ja aeglane). Niisiis, B-puu kasutamine binaarse puu asemel lühendab oluliselt hargnemisteguri ja puu madala kõrguse tõttu juurdepääsu aega.