V naslednji vadnici bomo spoznali podatkovno strukturo drevesa B in razmislili o njeni vizualizaciji.
Torej, začnimo.
Kaj je drevo B?
The B Drevo je posebna vrsta večsmernega iskalnega drevesa , splošno znan kot M-pot drevo, ki se uravnovesi. Zaradi svoje uravnotežene strukture se ta drevesa pogosto uporabljajo za delovanje in upravljanje ogromnih baz podatkov ter poenostavitev iskanja. V drevesu B ima lahko vsako vozlišče največ n podrejenih vozlišč. Drevo B je primer večnivojskega indeksiranja v sistemu za upravljanje baz podatkov (DBMS). Listna in notranja vozlišča bodo imela reference zapisov. Drevo B je znano kot uravnoteženo shranjeno drevo, ker so vsa vozlišča listov na isti ravni.
Naslednji diagram je primer drevesa B:
Slika 1. A B Drevo z redom 3
Razumevanje pravil drevesa B
Sledijo pomembne lastnosti drevesa B:
- Vsi listni vozli so na isti ravni.
- Podatkovna struktura drevesa B je opredeljena z izrazom najmanjša stopnja 'd'. Vrednost 'd' je odvisna od velikosti diskovnega bloka.
- Vsako vozlišče, razen korena, mora biti sestavljeno iz vsaj d-1 ključev. Korensko vozlišče je lahko sestavljeno iz najmanj 1 ključa.
- Vsa vozlišča (vključno s korenskim vozliščem) lahko sestavljajo največ (2d-1) ključi.
- Število otrok vozlišča je enako dodatek števila ključev, ki so v njem in .
- Vsi ključi vozlišča so razvrščeni v naraščajočem vrstnem redu. Otrok med dvema ključema, k1 in k2, je sestavljen iz vseh ključev, ki segajo med k1 in k2.
- Za razliko od binarnega iskalnega drevesa se podatkovna struktura drevesa B povečuje in krči od korena. Medtem ko binarno iskalno drevo raste navzdol in se krči navzdol.
- Podobno kot pri drugih samouravnoteženih binarnih iskalnih drevesih je časovna kompleksnost podatkovne strukture drevesa B za operacije, kot so iskanje, vstavljanje in brisanje, O(log?n) .
- Vstavljanje vozlišča v drevo B se zgodi samo na listnem vozlišču.
Oglejmo si naslednji primer drevesa B minimalnega reda 5.
očisti predpomnilnik npm
Slika 2. A B Drevo reda 5
Opomba: vrednost minimalnega naročila je veliko večja od 5 v praktičnih drevesih B.
V zgornjem diagramu lahko opazimo, da so vsa listna vozlišča na isti ravni in da vsa nelistna vozlišča nimajo praznega poddrevesa in so sestavljena iz ključev, za enega manj kot je število njihovih otrok.
Nastavljena formulacija pravil drevesa B:
Vsako drevo B je odvisno od pozitivnega konstantnega celega števila, znanega kot NAJMANJ , ki se uporablja za določitev števila podatkovnih elementov, ki jih je mogoče hraniti v enem vozlišču.
1. pravilo: Koren ima lahko le en podatkovni element (ali celo nobenega podatkovnega elementa, če prav tako ni podrejen); vsako drugo vozlišče ima vsaj NAJMANJ podatkovnih elementov.
2. pravilo: Največje število podatkovnih elementov, shranjenih v vozlišču, je dvakratna vrednost NAJMANJ .
3. pravilo: Podatkovni elementi vsakega vozlišča drevesa B so shranjeni v delno izpolnjeni matriki, razvrščeni od najmanjšega podatkovnega elementa (pri indeksu 0 ) na največji podatkovni element (na končnem uporabljenem položaju matrike).
4. pravilo: Skupno število poddreves pod vozliščem, ki ni list, je vedno za eno večje od števila podatkovnih elementov v tem vozlišču.
- poddrevo 0, poddrevo 1,...
5. pravilo: Glede na vozlišče, ki ni list:
- Podatkovni element na indeksu je večji od vseh podatkovnih elementov v številki poddrevesa jaz vozlišča in
- Podatkovni element na indeksu je manjši od vseh podatkovnih elementov v številki poddrevesa i+1 vozlišča.
6. pravilo: Vsak list v drevesu B ima enako globino. Tako zagotavlja, da drevo B prepreči problem neuravnoteženega drevesa.
Operacije na podatkovni strukturi drevesa B
Da bi zagotovili, da med operacijami ni kršena nobena od lastnosti podatkovne strukture drevesa B, se lahko drevo B razdeli ali združi. Sledi nekaj operacij, ki jih lahko izvedemo na drevesu B:
- Iskanje podatkovnega elementa v drevesu B
- Vstavljanje podatkovnega elementa v drevo B
- Izbris podatkovnega elementa v drevesu B
Operacija iskanja na drevesu B
Iskanje elementa v drevesu B je podobno kot v binarnem iskalnem drevesu. Toda namesto dvosmerne odločitve (levo ali desno), kot je binarno iskalno drevo, drevo B sprejme m-smerno odločitev v vsakem vozlišču, kjer je m število otrok vozlišča.
Koraki za iskanje podatkovnega elementa v drevesu B:
Korak 1: Iskanje se začne od korenskega vozlišča. Primerjaj iskalni element, k, s korenom.
Korak 1.1: Če je korensko vozlišče sestavljeno iz elementa k, bo iskanje končano.
Korak 1.2: Če je element k manjši od prve vrednosti v korenu, se bomo premaknili na skrajno levi podrejeni element in ga iskali rekurzivno.
Korak 1.3.1: Če ima koren samo dva otroka, se bomo pomaknili do skrajno desnega otroka in rekurzivno iskali podrejena vozlišča.
Korak 1.3.2: Če ima koren več kot dva ključa, bomo preiskali ostale.
2. korak: Če element k ni najden po prehodu celotnega drevesa, potem iskalni element ni prisoten v drevesu B.
Predstavimo zgornje korake s pomočjo primera. Recimo, da želimo poiskati ključ k=34 v naslednjem drevesu B:
Slika 3.1. Dano drevo B
- Najprej bomo preverili, ali je ključ k = 34 je v korenskem vozlišču. Ker ključ ni v korenu, bomo prešli na njegova podrejena vozlišča. Opazimo lahko tudi, da ima korensko vozlišče dva otroka; zato bomo zahtevano vrednost primerjali med dvema ključema.
Slika 3.2. Ključ k ni prisoten v korenu - Zdaj, ko lahko opazimo, da je ključ k večji od korenskega vozlišča, tj. 30, bomo nadaljevali z desnim podrejenim korenom.
Slika 3.3. Tipka k > 30, premakni se k desnemu otroku - Zdaj bomo primerjali ključ k z vrednostmi, ki so prisotne na vozlišču, tj. 40 oziroma 50. Ker je ključ k manjši od levega ključa, tj. 40, se bomo premaknili na levi podrejeni del vozlišča.
Slika 3.4. Ključ k<40, move to left child< li> - Ker je vrednost v levem podrejenem elementu 40 34, kar je zahtevana vrednost, lahko sklepamo, da je ključ najden in iskalna operacija je zaključena.
Slika 3.4. Ključ k = 34, levi otrok 40
Ključ smo primerjali s štirimi različnimi vrednostmi v zgornjem primeru, dokler ga nismo našli. Tako je časovna kompleksnost, potrebna za operacijo iskanja v drevesu B, enaka O(log?n) .
Vstavljanje operacije v drevo B
Pri vstavljanju podatkovnega elementa v drevo B moramo najprej preveriti, ali je ta element že prisoten v drevesu ali ne. Če je podatkovni element najden znotraj drevesa B, se operacija vstavljanja ne izvede. Če pa temu ni tako, bomo nadaljevali z vstavljanjem. Med vstavljanjem elementa v listno vozlišče je treba upoštevati dva scenarija:
Koraki za vstavljanje podatkovnega elementa v drevo B:
Korak 1: Začeli bomo z izračunom največjega števila ključev v vozlišču na podlagi vrstnega reda drevesa B.
rekurzija java
2. korak: Če je drevo prazno, je dodeljeno korensko vozlišče in vstavili bomo ključ, ki deluje kot korensko vozlišče.
3. korak: Zdaj bomo poiskali ustrezno vozlišče za vstavljanje.
4. korak: Če je vozlišče polno:
Korak 4.1: Podatkovne elemente bomo vstavili v naraščajočem vrstnem redu.
Korak 4.2: Če so podatkovni elementi večji od največjega števila ključev, bomo celotno vozlišče razdelili na mediano.
Korak 4.3: Srednji ključ bomo potisnili navzgor in razdelili levo in desno tipko kot levi in desni otrok.
5. korak: Če vozlišče ni polno, bomo vozlišče vstavili v naraščajočem vrstnem redu.
Predstavimo zgornje korake s pomočjo primera. Recimo, da moramo ustvariti drevo B reda 4. Podatkovni elementi, ki jih je treba vstaviti v drevo B, so 5,3,21,11,1,16,8,13,4 in 9 .
- Ker je m enako 3, je največje število ključev za vozlišče = m-1 = 3-1 = 2 .
- Začeli bomo z vstavljanjem 5 v praznem drevesu.
Slika 4.1. Vstavljanje 5 - Zdaj bomo v drevo vstavili 3. Ker je 3 manj kot 5, bomo 3 vstavili levo od 5 v isto vozlišče.
Slika 4.2. Vstavljanje 3 - Zdaj bomo v drevo vstavili 21 in ker je 21 večje od 5, bo vstavljeno desno od 5 v istem vozlišču. Ker pa vemo, da je največje število ključev v vozlišču 2, bo eden od teh ključev premaknjen v zgornje vozlišče, da ga razdelimo. Tako se bo 5, srednji podatkovni element, premaknil navzgor, 3 in 21 pa bosta postala njegovo levo oziroma desno vozlišče.
Slika 4.3. Vstavljanje 21 - Zdaj je čas, da vstavite naslednji podatkovni element, tj. 11, ki je večji od 5, vendar manjši od 21. Zato bo 11 vstavljen kot ključ na levi strani vozlišča, ki ga sestavlja 21 kot ključ.
Slika 4.4. Vstavljanje 11 - Podobno bomo v drevo vstavili naslednji podatkovni element 1 in kot lahko opazimo, je 1 manjši od 3; zato bo vstavljen kot ključ na levi strani vozlišča, sestavljenega iz 3 kot ključ.
Slika 4.5. Vstavljanje 1 - Zdaj bomo v drevo vstavili podatkovni element 16, ki je večji od 11, vendar manjši od 21. Vendar pa število ključev v tem vozlišču presega največje število ključev. Zato se bo vozlišče razdelilo in premaknilo srednji ključ v koren. Zato bo 16 vstavljeno desno od 5, pri čemer bosta 11 in 21 razdeljena na dve ločeni vozlišči.
Slika 4.6. Vstavljanje 16 - Podatkovni element 8 bo vstavljen kot ključ levo od 11.
Slika 4.7. Vstavljanje 8 - V drevo bomo vstavili 13, ki je manjši od 16 in večji od 11. Zato je treba podatkovni element 13 vstaviti desno od vozlišča, ki ga sestavljata 8 in 11. Ker pa lahko največje število ključev v drevesu samo 2, bo prišlo do delitve, ki bo premaknila srednji podatkovni element 11 v zgornje vozlišče ter 8 in 13 v dve ločeni vozlišči. Zdaj bo zgornje vozlišče sestavljeno iz 5, 11 in 16, kar spet presega največje število ključev. Zato bo prišlo do nove delitve, zaradi česar bo podatkovni element 11 korensko vozlišče s 5 in 16 kot otrokoma.
Slika 4.8. Vstavljanje 13 - Ker je podatkovni element 4 manjši od 5, vendar večji od 3, bo vstavljen desno od vozlišča, sestavljenega iz 1 in 3, kar bo ponovno preseglo največje število ključev v vozlišču. Zato bo znova prišlo do razlitja, pri čemer se bo 3 premaknilo na zgornje vozlišče poleg 5.
Slika 4.9. Vstavljanje 4 - Končno bo podatkovni element 9, ki je večji od 8, vendar manjši od 11, vstavljen desno od vozlišča, ki ga sestavlja 8, kot ključ.
Slika 4.10. Vstavljanje 9
V zgornjem primeru smo izvedli različne primerjave. Prva vrednost je bila neposredno vstavljena v drevo; po tem je bilo treba vsako vrednost primerjati z vozlišči, ki so na voljo v tem drevesu. Časovna zahtevnost operacije vstavljanja v drevo B je odvisna od števila vozlišč in .
Brisanje operacije na drevesu B
Brisanje podatkovnega elementa na drevesu B vsebuje tri primarne dogodke:
- Iskanje vozlišča, kjer obstaja ključ, ki ga želite izbrisati,
- Brisanje ključa in
- Uravnoteženje drevesa, če je potrebno.
Med brisanjem elementa iz drevesa lahko pride do stanja, znanega kot Underflow. Do pretoka pride, ko je vozlišče sestavljeno iz manj kot najmanjšega števila ključev; naj drži.
Sledi nekaj izrazov, ki jih morate razumeti, preden vizualizirate operacijo izbrisa/odstranitve:
Sledijo trije vidni primeri operacije brisanja v drevesu B:
Primer 1: Izbris/Odstranitev ključa je v listnem vozlišču - Ta primer je nadalje razdeljen na dva različna primera:
1. Brisanje/odstranitev ključa ne krši lastnosti najmanjšega števila ključev, ki jih mora imeti vozlišče.
Predstavimo si ta primer s primerom, kjer bomo izbrisali ključ 32 iz naslednjega drevesa B.
Slika 4.1: Brisanje ključa listnega vozlišča (32) iz drevesa B
Kot lahko opazimo, brisanje 32 iz tega drevesa ne krši zgornje lastnosti.
kako najti skrite aplikacije na androidu
2. Brisanje/odstranitev ključa krši lastnost najmanjšega števila ključev, ki jih mora imeti vozlišče. V tem primeru si moramo izposoditi ključ od njegovega bližnjega bratskega vozlišča v vrstnem redu od leve proti desni.
Najprej bomo obiskali bližnjega levega brata in sestro. Če ima levo bratsko vozlišče več kot minimalno število ključev, si bo izposodilo ključ od tega vozlišča.
V nasprotnem primeru bomo preverili izposojo iz bližnjega desnega bratskega vozlišča.
Predstavimo zdaj ta primer s pomočjo primera, kjer bomo izbrisali 31 iz zgornjega drevesa B. V tem primeru si bomo izposodili ključ od levega bratskega vozlišča.
Slika 4.2: Brisanje ključa listnega vozlišča (31) iz drevesa B
Če sta obe bližnji sorodni vozlišči že sestavljeni iz minimalnega števila ključev, bomo vozlišče združili bodisi z levim sorodnim vozliščem bodisi z desnim. Ta postopek združevanja poteka prek nadrejenega vozlišča.
Ponovno vizualizirajmo tako, da izbrišemo ključ 30 iz zgornjega drevesa B.
Slika 4.3: Brisanje ključa listnega vozlišča (30) iz drevesa B
2. primer: Brisanje/odstranitev ključa je v vozlišču, ki ni list – Ta primer je nadalje razdeljen na različne primere:
1. Nelistno/notranje vozlišče, ki je odstranjeno, se nadomesti s predhodnikom v vrstnem redu, če ima levo podrejeno vozlišče več kot minimalno število ključev.
Predstavimo si ta primer s primerom, kjer bomo izbrisali ključ 33 iz drevesa B.
Slika 4.4: Brisanje ključa listnega vozlišča (33) iz drevesa B
2. Ne-listno/notranje vozlišče, ki je odstranjeno, se nadomesti z naslednikom po vrstnem redu, če ima desno podrejeno vozlišče več kot minimalno število ključev.
Če ima kateri koli od otrok najmanjše število ključev, bomo združili levo in desno podrejeno vozlišče.
Predstavimo si ta primer tako, da izbrišemo ključ 30 iz drevesa B.
Slika 4.5: Brisanje ključa listnega vozlišča (30) iz drevesa B
Če ima po združitvi nadrejeno vozlišče manj kot minimalno število ključev, lahko poiščemo brate in sestre, kot v Primer 1 .
Primer 3: V naslednjem primeru se višina drevesa zmanjša. Če je ciljni ključ v notranjem vozlišču in odstranitev ključa povzroči manj ključev v vozlišču (kar je manj od najmanjšega potrebnega), potem poiščite predhodnika po vrstnem redu in naslednika po vrstnem redu. Če imata oba otroka minimalno število ključev, potem do izposoje ne more priti. To vodi do Primer 2(3) , tj. združevanje podrejenih vozlišč.
Spet bomo iskali brata ali sestro, da bi si izposodili ključ. Vendar, če je sestra sestavljena tudi iz minimalnega števila ključev, potem bomo združili vozlišče s sorodnikom skupaj z nadrejenim vozliščem in razporedili podrejena vozlišča v skladu z zahtevami (naraščajoče vrstni red).
Predstavimo si ta primer s pomočjo primera, kjer bomo izbrisali podatkovni element 10 iz danega drevesa B.
Slika 4.6: Brisanje ključa listnega vozlišča (10) iz drevesa B
Časovna zahtevnost v zgornjih primerih se razlikuje glede na lokacijo, s katere je treba izbrisati ključ. Tako je časovna kompleksnost za operacijo brisanja v drevesu B O(log?n) .
Sklep
V tej vadnici smo se naučili o drevesu B in vizualizirali njegove različne operacije z različnimi primeri. Razumeli smo tudi nekatere temeljne lastnosti in pravila drevesa B.