Teine erinevus B-puu ja binaarpuu vahel on see, et B-puul peab olema kõik selle lapse sõlmed samal tasemel, samas kui binaarpuudel ei ole sellist piirangut. Binaarpuudel võib olla maksimaalselt 2 alampuud või sõlmed, samas kui B-puus võib olla alampuude või sõlmede M, kus M on B-puu järjekord.
Võrdluskaart
| Võrdluse alus | B-puu | Binaarne puu |
|---|---|---|
| Oluline piirang | Noodil võib olla maksimaalselt M lastekohtade arv (kus M on puu järjekord). | Noodil võib olla maksimaalselt 2 alampuude arvu. |
| Kasutatud | Seda kasutatakse siis, kui andmed salvestatakse kettale. | Seda kasutatakse siis, kui mällu salvestatakse andmeid ja andmeid. |
| Puu kõrgus | log M N (kus m on M-tee puu järjekord) | log 2 N |
| Rakendus | Koodi indekseerimine andmete struktuuri paljudes DBMS-is. | Koodi optimeerimine, Huffmani kodeerimine jne |
B-puu määratlus
B-puu on tasakaalustatud M-tee puu ja seda tuntakse ka tasakaalustatud sorteerimispuudena. See on sarnane binaarotsingupuudega, kus sõlmed on korraldatud sisemise liikumise alusel. B-puu ruumi keerukus on O (n). Sisestamise ja deletsiooni aja keerukus on O (log n).
B-puu suhtes peavad kehtima teatud tingimused:
- Puu kõrgus peab olema võimalikult väike.
- Puu lehtede kohal ei tohiks olla tühi alampuid.
- Puu lehed peavad olema samal tasemel.
- Kõigil sõlmpunktidel peaks olema kõige vähem lapsi, välja arvatud puhkuse sõlmed.
B-järjekorra M-i omadused
- Igal sõlmel võib olla maksimaalne M-laste arv ja minimaalne M / 2-laste arv või mis tahes number 2-st maksimaalselt.
- Igal sõlmel on üks võtme vähem kui lastel, kellel on maksimaalsed M-1 võtmed.
- Klahvide paigutus on sõlmedes mingis kindlas järjekorras. Kõik klahvi vasakul pool asuvad alavõtu võtmed on võtme eelkäijad ja võtme parempoolsetes osades esinevaid pärijad on pärijad.
- Täieliku sõlme sisestamise ajal jaguneb puu kaheks osaks ja keskväärtusega võti sisestatakse põhisõlmesse.
- Ühendamine toimub siis, kui sõlmed on kustutatud.
Binaarse puu määratlus
Binaarpuu on puustruktuur, millel on oma laste sõlmede jaoks kõige rohkem kaks punkti. See tähendab, et kõrgeim tase, millel sõlme võib olla, on 2 ja samuti võib olla null või ühe kraadi sõlme.
Binaarpuud on teatud variandid nagu rangelt binaarne puu, täielik binaarne puu, laiendatud binaarne puu jne.
- Rangelt binaarne puu on puu, kus igal mitteterminalil peab olema vasakpoolne subtree ja parem subtree.
- Puu on nn täielik binaarne puu, kui see vastab 2 i sõlme seisundile igal tasandil, kus i on tase.
- Keermestatud binaar on binaarne puu, mis koosneb kas 0 sõlmedest või 2 sõlmede arvust.
Liikumisviisid
Puu liikumine on üks kõige sagedasemaid toiminguid, mida teostatakse puude andmete struktuuris, kus iga sõlme süstemaatiliselt külastas täpselt üks kord.
- Inorder- Selles puus liikumine vasakpoolne subtree külastatakse rekursiivselt, siis juuremoodulit külastatakse ja viimasel parempoolsel alamvooru külastatakse.
- Ennustaja- Selles puusõidul külastatakse juuremoodulit esimesel, seejärel vasakpoolsel alamvõrgul ja lõpuks parempoolsel alalõppal.
- Postitus- See tehnika külastab vasakpoolset subtree, siis parempoolset alajaotust ja viimasel juursõlmel.
B-puu ja binaarse puu vahelised peamised erinevused
- B-puus võib olla maksimaalne laste sõlmede arv, mis ei ole terminalisõlmed, on M, kus M on B-puu järjekord. Teisest küljest võib kahekomponendilises puus olla maksimaalselt kaks alampuud või lapse sõlmed.
- B-puu kasutatakse siis, kui andmeid salvestatakse kettale, samas kui binaarset puu kasutatakse siis, kui andmeid salvestatakse kiirmälus, nagu RAM.
- Teine B-ala rakendusala on koodide indekseerimise andmestruktuur DBMS-is, seevastu binaarne puu kasutatakse koodide optimeerimisel, huffmani kodeerimisel jne.
- B-puu maksimaalne kõrgus on log M N (M on puude järjekord). Vastupidi, binaarne puu maksimaalne kõrgus on log 2 N (N on sõlmede arv ja baas on 2, sest see on binaarne).
Järeldus
B-puu kasutatakse binaar- ja binaarotsingupuudel, mille peamiseks põhjuseks on mälu hierarhia, kus CPU on ühendatud vahemäluga suure ribalaiusega kanalitega, samas kui CPU on ühendatud kettaga väikese ribalaiuse kanali kaudu. Binaarset puu kasutatakse siis, kui salvestatakse mällu RAM (väike ja kiire) ja B-puu kasutatakse siis, kui kirjed salvestatakse kettale (suured ja aeglased). Niisiis vähendab B-puu kasutamine binaarpuu asemel märkimisväärselt ligipääsuaega kõrge hargnemisteguri ja puu kõrguse tõttu.
