Nākamajā apmācībā mēs uzzināsim par B Tree datu struktūru un apsvērsim tās vizualizāciju.
Tātad, sāksim.
Kas ir B koks?
The B Koks ir īpaša veida daudzvirzienu meklēšanas koks , pazīstams kā M-ceļš koks, kas līdzsvaro sevi. Līdzsvarotās struktūras dēļ šie koki parasti tiek izmantoti, lai darbinātu un pārvaldītu milzīgas datu bāzes un vienkāršotu meklēšanu. B kokā katram mezglam var būt ne vairāk kā n pakārtotie mezgli. B koks ir daudzlīmeņu indeksēšanas piemērs datu bāzes pārvaldības sistēmā (DBVS). Lapu un iekšējiem mezgliem būs ierakstu atsauces. B koks ir pazīstams kā līdzsvarots uzglabātais koks, jo visi lapu mezgli atrodas vienā līmenī.
Šī diagramma ir B koka piemērs:
1. attēls. A B Koks ar 3. secību
Izpratne par B koka noteikumiem
Šīs ir svarīgas B koka īpašības:
- Visi lapu mezgli atrodas vienā līmenī.
- B koka datu struktūru nosaka termins minimālā pakāpe “d”. “d” vērtība ir atkarīga no diska bloka lieluma.
- Katram mezglam, izņemot sakni, jāsastāv no vismaz d-1 atslēgām. Saknes mezglā var būt vismaz 1 atslēga.
- Visi mezgli (ieskaitot saknes mezglu) var sastāvēt no ne vairāk kā (2d-1) atslēgas.
- Mezgla bērnu skaits ir vienāds ar tajā esošo atslēgu skaita pievienošana un .
- Visas mezgla atslēgas ir sakārtotas augošā secībā. Bērns starp diviem taustiņiem k1 un k2 sastāv no visiem taustiņiem, kas attiecīgi ir no k1 līdz k2.
- Atšķirībā no binārā meklēšanas koka B koka datu struktūra aug un sarūk no saknes. Savukārt binārais meklēšanas koks aug uz leju un sarūk uz leju.
- Līdzīgi kā citiem pašlīdzsvarotiem binārajiem meklēšanas kokiem, B koka datu struktūras laika sarežģītība tādām darbībām kā meklēšana, ievietošana un dzēšana ir O(log?n) .
- Mezgla ievietošana B kokā notiek tikai lapas mezglā.
Apskatīsim šādu B koka piemēru ar minimālo pakāpi 5.
2. attēls. A B Kārtības koks 5
Piezīme: minimālā pasūtījuma vērtība ir daudz lielāka par 5 praktiskajā B Koki.
Iepriekš redzamajā diagrammā mēs varam novērot, ka visi lapu mezgli atrodas vienā līmenī, un visiem mezgliem, kas nav lapu mezgli, nav tukša apakškoka un tie sastāv no taustiņiem, kas ir par vienu mazāki nekā to bērnu skaits.
B koka noteikumu noteiktais formulējums:
Katrs B koks ir atkarīgs no pozitīva konstanta vesela skaitļa, kas pazīstams kā MINIMUM , ko izmanto, lai noteiktu datu elementu skaitu, ko var turēt vienā mezglā.
1. noteikums: Saknē var būt tikai viens datu elements (vai pat bez datu elementiem, ja tas nav arī pakārtots); katram otrajam mezglam ir vismaz MINIMUM datu elementi.
daļējs lateksa atvasinājums
2. noteikums: Maksimālais mezglā saglabāto datu elementu skaits ir divreiz lielāks par vērtību MINIMUM .
3. noteikums: Katra B koka mezgla datu elementi tiek glabāti daļēji aizpildītā masīvā, sakārtoti no mazākā datu elementa (indeksā 0 ) uz lielāko datu elementu (masīva galīgajā izmantotajā pozīcijā).
4. noteikums: Kopējais apakškoku skaits zem mezgla, kas nav lapas, vienmēr ir par vienu vairāk nekā datu elementu skaits šajā mezglā.
- apakškoks 0, apakškoks 1,...
5. noteikums: Attiecībā uz jebkuru mezglu, kas nav lapu:
- Datu elements indeksā ir lielāks par visiem datu elementiem apakškoka numurā i no mezgla un
- Datu elements indeksā ir mazāks par visiem datu elementiem apakškoka numurā i+1 no mezgla.
6. noteikums: Katrai B koka lapai ir vienāds dziļums. Tādējādi tas nodrošina, ka B koks novērš nelīdzsvarota koka problēmu.
Darbības ar B koka datu struktūru
Lai nodrošinātu, ka darbību laikā netiek pārkāpts neviens no B koka datu struktūras rekvizītiem, B koks var tikt sadalīts vai apvienots. Tālāk ir norādītas dažas darbības, kuras mēs varam veikt ar B koku:
- Datu elementa meklēšana B kokā
- Datu elementa ievietošana B kokā
- Datu elementa dzēšana B kokā
Meklēšanas operācija uz B koka
Elementa meklēšana B kokā ir līdzīga kā binārajā meklēšanas kokā. Bet tā vietā, lai pieņemtu divvirzienu lēmumu (pa kreisi vai pa labi), piemēram, binārais meklēšanas koks, B koks katrā mezglā pieņem m-virziena lēmumu, kur m ir mezgla bērnu skaits.
Darbības, lai meklētu datu elementu B kokā:
1. darbība: Meklēšana sākas no saknes mezgla. Salīdziniet meklēšanas elementu k ar sakni.
1.1. darbība: Ja saknes mezgls sastāv no elementa k, meklēšana būs pabeigta.
1.2. darbība: Ja elements k ir mazāks par pirmo vērtību saknē, mēs pāriesim uz vistālāk kreiso bērnu un meklēsim bērnu rekursīvi.
1.3.1. darbība: Ja saknei ir tikai divi bērni, mēs pāriesim uz vislabāko bērnu un rekursīvi pārmeklēsim bērna mezglus.
1.3.2. darbība: Ja saknei ir vairāk nekā divas atslēgas, mēs meklēsim pārējās.
2. darbība: Ja elements k netiek atrasts pēc visa koka šķērsošanas, tad meklēšanas elements B kokā nav.
Ļaujiet mums vizualizēt iepriekš minētās darbības, izmantojot piemēru. Pieņemsim, ka mēs vēlējāmies meklēt atslēgu k=34 šādā B kokā:
3.1.attēls. Dotais B koks
- Pirmkārt, mēs pārbaudīsim, vai atslēga k = 34 atrodas saknes mezglā. Tā kā atslēga neatrodas saknē, mēs pāriesim uz tās atvasinātajiem mezgliem. Varam arī novērot, ka saknes mezglam ir divi bērni; tāpēc mēs salīdzināsim nepieciešamo vērtību starp abiem taustiņiem.
3.2.attēls. Atslēga k neatrodas saknē - Tagad, kad mēs varam pamanīt, ka atslēga k ir lielāka par saknes mezglu, t.i., 30, mēs turpināsim ar pareizo saknes atvasinājumu.
3.3.attēls. Taustiņš k > 30, pāriet uz labo bērnu - Tagad mēs salīdzināsim atslēgu k ar vērtībām, kas atrodas mezglā, t.i., attiecīgi 40 un 50. Tā kā atslēga k ir mazāka par kreiso taustiņu, t.i., 40, mēs pāriesim uz mezgla kreiso atvasi.
3.4.attēls. Atslēga k<40, move to left child< li> - Tā kā 40. kreisā atvasinātā vērtība ir 34, kas ir vajadzīgā vērtība, mēs varam secināt, ka atslēga ir atrasta un meklēšanas darbība ir pabeigta.
3.4.attēls. Atslēga k = 34, kreisais bērns — 40
Mēs salīdzinājām atslēgu ar četrām dažādām vērtībām iepriekš minētajā piemērā, līdz to atradām. Tādējādi laika sarežģītība, kas nepieciešama meklēšanas darbībai B kokā, ir O(log?n) .
Ievietošanas darbība uz B koka
Ievietojot datu elementu B kokā, vispirms ir jāpārbauda, vai šis elements jau ir kokā. Ja datu elements tiek atrasts B kokā, ievietošanas darbība nenotiek. Tomēr, ja tas tā nav, mēs turpināsim ievietošanu. Ievietojot elementu lapas mezglā, ir jāievēro divi scenāriji:
Darbības, lai ievietotu datu elementu B kokā:
1. darbība: Mēs sāksim ar maksimālo atslēgu skaitu mezglā, pamatojoties uz B koka secību.
2. darbība: Ja koks ir tukšs, tiek piešķirts saknes mezgls, un mēs ievietosim atslēgu, kas darbojas kā saknes mezgls.
3. darbība: Tagad mēs meklēsim atbilstošo mezglu ievietošanai.
4. darbība: Ja mezgls ir pilns:
4.1. darbība: Mēs ievietosim datu elementus augošā secībā.
4.2. darbība: Ja datu elementi ir lielāki par maksimālo atslēgu skaitu, mēs sadalīsim visu mezglu pie mediānas.
pasvītrot, izmantojot css
4.3. darbība: Mēs virzīsim vidējo taustiņu uz augšu un sadalīsim kreiso un labo taustiņu kā kreiso un labo bērnu.
5. darbība: Ja mezgls nav pilns, mēs ievietosim mezglu augošā secībā.
Ļaujiet mums vizualizēt iepriekš minētās darbības, izmantojot piemēru. Pieņemsim, ka mums ir jāizveido 4. kārtas B koks. Datu elementi, kas jāievieto B kokā, ir 5, 3, 21, 11, 1, 16, 8, 13, 4 un 9 .
- Tā kā m ir vienāds ar 3, maksimālais atslēgu skaits mezglam = m-1 = 3-1 = 2 .
- Mēs sāksim ar ievietošanu 5 tukšajā kokā.
4.1.attēls. Ievietošana 5 - Tagad mēs ievietosim 3 kokā. Tā kā 3 ir mazāks par 5, mēs tajā pašā mezglā ievietosim 3 pa kreisi no 5.
4.2. attēls. Ievietošana 3 - Tagad kokā ievietosim 21, un, tā kā 21 ir lielāks par 5, tas tiks ievietots pa labi no 5 tajā pašā mezglā. Tomēr, tā kā mēs zinām, ka maksimālais atslēgu skaits mezglā ir 2, viena no šīm atslēgām tiks pārvietota uz augstāk esošo mezglu, lai to sadalītu. Tādējādi 5, vidējais datu elements, pārvietosies uz augšu, un 3 un 21 kļūs attiecīgi par tā kreiso un labo mezglu.
4.3.attēls. Ievietošana 21 - Tagad ir pienācis laiks ievietot nākamo datu elementu, t.i., 11, kas ir lielāks par 5, bet mazāks par 21. Tāpēc 11 tiks ievietota kā atslēga pa kreisi no mezgla, kas sastāv no 21 kā atslēga.
Attēls 4.4. Ievietojot 11 - Līdzīgi mēs kokā ievietosim nākamo datu elementu 1, un, kā redzam, 1 ir mazāks par 3; tādēļ tā tiks ievietota kā atslēga pa kreisi no mezgla, kas sastāv no 3 kā atslēga.
4.5. attēls. Ievietošana 1 - Tagad kokā ievietosim datu elementu 16, kas ir lielāks par 11, bet mazāks par 21. Tomēr atslēgu skaits šajā mezglā pārsniedz maksimālo atslēgu skaitu. Tāpēc mezgls sadalīsies, pārvietojot vidējo taustiņu uz sakni. Tādējādi 16 tiks ievietots pa labi no 5, sadalot 11 un 21 divos atsevišķos mezglos.
4.6. attēls. Ievietojot 16 - Datu elements 8 tiks ievietots kā atslēga pa kreisi no 11.
4.7. attēls. Ievietošana 8 - Mēs kokā ievietosim 13, kas ir mazāks par 16 un lielāks par 11. Tāpēc datu elements 13 ir jāievieto pa labi no mezgla, kas sastāv no 8 un 11. Tomēr, tā kā maksimālais atslēgu skaits kokā var tikai 2, tiks veikta sadalīšana, pārvietojot vidējo datu elementu 11 uz iepriekš minēto mezglu un 8 un 13 divos atsevišķos mezglos. Tagad iepriekš minētais mezgls sastāvēs no 5, 11 un 16, kas atkal pārsniedz maksimālo atslēgu skaitu. Tāpēc tiks veikts vēl viens sadalījums, padarot datu elementu 11 par saknes mezglu ar 5 un 16 kā atvasinājumiem.
Attēls 4.8. Ievietošana 13 - Tā kā datu elements 4 ir mazāks par 5, bet lielāks par 3, tas tiks ievietots pa labi no mezgla, kas sastāv no 1 un 3, kas atkal pārsniegs maksimālo atslēgu skaitu mezglā. Tāpēc atkal notiks noplūde, pārvietojot 3 uz augšējo mezglu blakus 5.
4.9. attēls. Ievietošana 4 - Beidzot datu elements 9, kas ir lielāks par 8, bet mazāks par 11, kā atslēga tiks ievietots pa labi no mezgla, kas sastāv no 8.
4.10. attēls. Ievietošana 9
Iepriekš minētajā piemērā mēs esam veikuši dažādus salīdzinājumus. Pirmā vērtība tika tieši ievietota kokā; pēc tam katra vērtība bija jāsalīdzina ar šajā kokā pieejamajiem mezgliem. B koka ievietošanas operācijas laika sarežģītība ir atkarīga no mezglu skaita un .
Darbības dzēšana B kokam
Datu elementa dzēšana B kokā ietver trīs primāros notikumus.
- Meklējot mezglu, kurā atrodas dzēšamā atslēga,
- Dzēšot atslēgu un
- Koka līdzsvarošana, ja nepieciešams.
Dzēšot elementu no koka, var rasties stāvoklis, kas pazīstams kā Underflow. Nepietiekama plūsma notiek, ja mezglā ir mazāk nekā minimālais atslēgu skaits; tam vajadzētu noturēties.
Tālāk ir norādīti daži termini, kas jāsaprot pirms dzēšanas/noņemšanas darbības vizualizācijas.
Tālāk ir norādīti trīs pamanāmi dzēšanas darbības gadījumi B kokā.
1. gadījums: atslēgas dzēšana/noņemšana atrodas Lapas mezglā - Šī lieta ir sadalīta divos dažādos gadījumos:
1. Atslēgas dzēšana/noņemšana nepārkāpj minimālā atslēgu skaita īpašību, kas jāsatur mezglā.
Vizualizēsim šo gadījumu, izmantojot piemēru, kurā mēs izdzēsīsim atslēgu 32 no nākamā B koka.
4.1. attēls: Lapas mezgla atslēgas (32) dzēšana no B koka
Kā mēs varam novērot, 32 dzēšana no šī koka nepārkāpj iepriekš minēto īpašību.
2. Atslēgas dzēšana/noņemšana pārkāpj minimālā mezgla atslēgu skaita īpašību. Šajā gadījumā mums ir jāaizņemas atslēga no tās tuvākā brāļa un māsas mezgla secībā no kreisās uz labo.
Pirmkārt, mēs apmeklēsim tuvāko kreiso brāli. Ja mezglam Left sibling ir vairāk nekā minimālais atslēgu skaits, tas aizņems atslēgu no šī mezgla.
Citādi mēs pārbaudīsim, vai aizņemties no tuvākā labā brāļa mezgla.
Tagad vizualizēsim šo gadījumu, izmantojot piemēru, kur mēs izdzēsīsim 31 no iepriekš minētā B koka. Šajā gadījumā mēs aizņemsimies atslēgu no kreisā brāļa mezgla.
4.2. attēls: Lapas mezgla atslēgas (31) dzēšana no B koka
galvenā metode java
Ja abi tuvākie māsas mezgli jau sastāv no minimālā atslēgu skaita, tad mēs apvienosim mezglu vai nu ar kreiso brāļa mezglu vai labo. Šis apvienošanas process tiek veikts, izmantojot vecāku mezglu.
Atkārtoti vizualizēsim, izdzēšot atslēgu 30 no iepriekš minētā B koka.
4.3. attēls: Lapas mezgla atslēgas (30) dzēšana no B koka
2. gadījums: atslēgas dzēšana/noņemšana atrodas mezglā, kas nav lapa - Šī lieta ir sīkāk sadalīta dažādos gadījumos:
1. Noņemtais mezgls, kas nav lapa/iekšējais mezgls, tiek aizstāts ar secības priekšteci, ja kreisajam pakārtotajam mezglam ir vairāk nekā minimālais atslēgu skaits.
Vizualizēsim šo gadījumu, izmantojot piemēru, kur mēs izdzēsīsim atslēgu 33 no B koka.
4.4. attēls: Lapas mezgla atslēgas (33) dzēšana no B koka
2. Noņemtais mezgls, kas nav lapas/iekšējais mezgls, tiek aizstāts ar kārtas pēcteci, ja labajā pakārtotajā mezglā ir vairāk nekā minimālais atslēgu skaits.
Ja kādam no bērniem ir minimālais atslēgu skaits, mēs sapludināsim kreiso un labo pakārtoto mezglu.
Vizualizēsim šo gadījumu, izdzēšot atslēgu 30 no B koka.
4.5. attēls: Lapas mezgla atslēgas (30) dzēšana no B koka
Pēc apvienošanas, ja vecākajam mezglam ir mazāks atslēgu skaits par minimālo atslēgu skaitu, var meklēt brāļus un māsas, kā 1. gadījums .
3. gadījums: Šādā gadījumā koka augstums samazinās. Ja mērķa atslēga atrodas iekšējā mezglā un atslēgas noņemšana noved pie mazāk atslēgu mezglā (kas ir mazāks par nepieciešamo minimumu), meklējiet secības priekšteci un secības pēcteci. Ja abiem bērniem ir minimālais atslēgu skaits, aizņemšanās nevar notikt. Tas noved pie Lieta 2(3) , t.i., apvienojot bērnu mezglus.
Mēs atkal meklēsim brāli un māsu, lai aizņemtos atslēgu. Tomēr, ja arī brālis un māsa sastāv no minimālā atslēgu skaita, tad mēs apvienosim mezglu ar brāli un māsu kopā ar vecākmezglu un sakārtosim pakārtotos mezglus atbilstoši prasībām (augošā secībā).
Vizualizēsim šo gadījumu ar piemēra palīdzību, kur mēs izdzēsīsim datu elementu 10 no dotā B koka.
4.6. attēls: Lapas mezgla atslēgas (10) dzēšana no B koka
Laika sarežģītība iepriekš minētajos piemēros atšķiras atkarībā no vietas, no kuras atslēga ir jādzēš. Tādējādi B koka dzēšanas operācijas laika sarežģītība ir O(log?n) .
Secinājums
Šajā apmācībā mēs esam uzzinājuši par B koku un vizualizējuši tā dažādās darbības ar dažādiem piemēriem. Mēs esam sapratuši arī dažas B koka pamatīpašības un noteikumus.