4. MEDŽIAI
4.1. Įvadas
Medžiai nusipelno išsamios apžvalgos dėl šių dviejų priežasčių:
• Medžiai yra paprasčiausia grafų klasė. Juos tenkina daugelis savybių, tačiau jos ne visada tinka bendru grafų atveju. Taikant medžiams daugumą įrodymų ir pamąstymų, jie iš tikrųjų yra daug paprastesni nei atrodo.Grafų uždavinių sprendimui iškeliama hipotezė, tikslinga juos pirmiausia patikrinti medžių pagalba.
• Medžiai yra pati populiariausia grafų klasė, kyri yra taikoma programavime įvairiausiose situacijose.
4.2. Laisvieji medžiai
Grafas, kuriame nėra ciklų, vadinamas acikliniu arba mišku. Jungus aciklinis grafas vadinamas laisvu medžiu. Jungi grafo elementai sudaro medžius ir gaunasi miškas, sudarytas iš medžių. Jungus grafas yra medis tada, kai jo briaunų skaičius yra lygus q(G)=p(G)-1.
Medžiu vadinamas susietas grafas, kuriame nėra ciklų. Toks grafas, suprantama, neturi kartotinių briaunų ir kiekvienos dvi jo viršūnės sujungtos tik viena grandine. Jungūs grafo elementai sudaro medžius, 0
medžiai – miškus. Jungus grafas vadinamas laisvuoju medžiu. Jungus grafas yra tada ir tik tada medis, kai jo briaunų skaičius lygus m = n – 1. Pagal viršūnės laipsnį medžiai gali būti binariniai (maksimalus viršūnės laipsnis
2), ternariniai ir t.t. Medžio viršūnės, kurių laipsnis lygus vienam, vadinamos kabančiomis viršūnėmis arba lapais. Medis, kurio viršūnių skaičius n [pic] 2, turi bent du lapus. Pirmoji medžio viršūnė, paprastai viršutinė, vadinama šaknimi – tai viršūnė, iš kurios šakos išeina, bet nė viena neįeina.
Viršūnės, kurios nutolusios nuo šaknies vienodu atstumu, sudaro vieną lygį.
Kelias iš šaknies į lapą vadinamas šaka. Didžiausias šakos ilgis orientuotame medyje vadinamas medžio aukščiu. Paprasčiausi ir, beje, labiausiai paplitę yra binarinės ( dvejetainės) struktūros medžiai.
[pic]
1 pav. Iliustracinė medžio tipo struktūra
Acikliniame grafe G z(G)=O. Tegul u, v – grafo G viršūnės, x =(u,v) E.
Jeigu grafas G+x turi tik tai vieną paprastą ciklą, z(G+x)=l, tai grafas G
vadinamas subcikliniu.
Pavyzdys:
Čia yra laisvieji medžiai su penkiom viršūnėm:
[pic]
Laisvieji medžiai su šešiom viršūnėm:
[pic]
4.2.1 Bendros medžių savybės
Teorema: Tegul G(V,E) – grafas su p viršūnėmis, q briaunomis, k jungeis komponentais ir z paprastais ciklais. Tegul x – briauna, jungianti bet kurią norimą negretimą porą į grafą G. Tada sekantys teiginiai ekvivalentūs:
1. G – medis, tai yra surištas grafas be ciklų, k(G)=l & z(G)=O;
2. Bet kurios dvi viršūnės sujungtos į grafą G vienguba paprasta grandimi,
( u, v (! (u,v);
3. G – sujungtas grafas, ir bet kuri briauna yra tiltas, k(G)=l& ;feEE k
(G-e»l;
4. G – surištas ir medžio pavidalo, k(G)=l & q(G)=p(G)-l;
5. G – aciklinis ir medžio pavidalo, z(G)=O & q(G)= p(G)-l;
6. G – aciklinis ir subciklinis, z(G)=O & z(G+x)=l;
7. G – jungus, subciklinis ir nepilnas, k(G)=l & K & p 3 & z(G+x)=l;
8. G – medžio pavidalo ir subciklinis, q(G)=p(G)-l & G(K1 U K3&G( K2 U K3
&z(G+x)=1.
4.2.2. Pagrindinės medžių savybės:
1. Medžiai turi vieną viršūnę, į kurią neįeina jokia kita. Ši viršūnė vadinama šaknimi.
2. Į kiekvieną viršūnę, išskyrus šaknį, įeina ne daugiau kaip viena viršūnė (incidentiška).
3. Iš šaknies į kiekvieną viršūnę veda vienintelis kelias.
4. Viršūnės, kurių laipsnis nelygus 0, vadinamos tėvinėmis, 0 joms incidentiškos dukterinėmis medžio viršūnėmis.
5. Viršūnės, kurios neturi dukterinių, vadinamos terminalinėmis arba lapais.
Medžiai pritaikomi labai įvairiai. Čia paminėsime, kad bet kurį rūšiavimo procesą galima išreikšti medžiu. Dauguma klasifikacinių schemų ar tiesiog klasifikatorių turi tipišką medžio struktūrą.
4.3. Orientuoti, sutvarkyti ir binariniai medžiai
Orientuotu medžiu vadinamas medis turintis šias savybes:
1. Egzistuoja vienintelė viršūnė, kurios įėjimo puslaipsnis yra lygus 0. Ši viršūnė vadinama šaknimi.
2. Įėjimo puslaipsnis lygus 1 kitų viršūnių atžvilgiu.
3. Kiekviena viršūnė yra pasiekiama iš šaknies.
Pavyzdys:
Orientuoti medžiai su trim viršūnėm:
[pic]
Orientuoti medžiai su keturiom viršūnėm:
[pic]
Orientuotas medis – tai aibė viršūnių, kur tam tikra viršūnė U yra medžio šaknis, 0 kitos viršūnės yra poromis nesikertančiose aibėse, kurių kiekviena yra orientuotas medis.
Pografis, kurį sudaro viršūnių aibė, kurį galima pasiekti iš bet kurios viršūnės, yra orientuotas medis, kurio šaknis yra atitinkama viršūnė. Jei laisvame grafe bet kurią viršūnę pavadinsime šaknimi, gausime orientuotą medį.
Orientuotame medyje viršūnės V, pasiekiamos iš viršūnės U, vadinamos palikuonimis, jei tarp tam tikrų viršūnių U ir V yra laukas, tai viršūnė U
vadinama tėvu, o V – sūnumi. Visi vienos viršūnės sūnūs vadinami broliais.
Teorema: Orientuotas medis turi šiai savybes:
1. q=p-1;
2. Jeigu orientuotame medyje panaikinus orientacines ribas, tai gautųsi laisvasis medis;
3. Orientuotas medis neturi kontūrų;
4. Kiekvienam mazgui egzistuoja vienintelis kelias, vedantis jį iš šaknis;
5. Pografis apibrėžiamas daugelio mazgų, pasiekiamų iš mazgo v, yra orientuotas medis su šaknimi v.
6. Jeigu laisvame medyje bet kurią viršūnę pažymėsime šaknimi, gausime orientacinį medį.
Kiekvieną laisvą medį apibrėžia ne daugiau p orientuotų medžių. Tokiu būdu, bendras skaičius skirtingų orientuotų medžių su p mazgais ne daugiau kaip p kartų pralenkia bendrą skaičių skirtingų orientuotų medžių su p viršūnėmis.
Paskutinė orientuoto medžio viršūnė vadinama lapu. Kelias iš šaknies į lapą vadinamas šaka. Orientuoto medžio didžiausios šakos ilgį vadiname medžio aukščiu. Pirmoji medžio viršūnė, paprastai viršutinė, vadinama šalutine.
Orientuoto medžio mazgo lygis – tai atstumas nuo šaknies iki mazgo. Pati šaknis yra lygi 0. Vieno lygio mazgai sudaro medžio aukštį.
Orientuotas medis T – tai žinoma daugybė mazgų, kurie: 1. turi vieną mazgą r, kuris vadinasi šaknimi iš duoto medžio; 2. likusieji mazgai būna k porose neperkiriami daugybe T1, …,Ta, iš kurių yra orientuotas medis (k(=0), T={ {r}, T1 ,.., Ta} .
Daugybe Tl,…, Ta orientuotuose medžiuose tampa pomedžiais. Orientuotas medis, turintis fiksuotą po medžių išsidėstymą, vadinamas sutvarkytu medžiu.
Orientuoti ir sutvarkyti orientuoti medžiai intensyviai naudojami programavime. pavyzdys: panaudota išraiška a+b*c [pic]
Orientuotu medžiu vadiname katalogų ir failų išsidėstymo struktūra.
Vaizduojant orientuotus medžius, šaknis yra viršuje ir visos rodyklės nukreiptos iš viršaus į apačią, todėl rodyklių galima net nevaizduoti.
Tokiu būdu laisvų, orientuotų ir sutvarkytų medžių schemos grafiškai atrodo neatskiriamos, ir todėl reikalaujama išsamaus nurodymo, kokios klasės medis yra pavaizduotas schemoje.
Pavyzdys:
Turime tris medžių schemas, kurie iš pirmo žvilgsnio atrodo skirtingi.
[pic]
a) b) c)
Jie visi atrodo, kad yra skirting: a)(b), b)(c), c)(a).
Binariniai medžiai – tai baigtinė viršūnių aibė, kuri yra arba tuščia, arba sudaryta iš šaknies ir dviejų nesusikertančių binarinių medžių – kairiojo ir dešiniojo.
Binarinis medis nėra sutvarkytas orientuotas medis.
Pavyzdys:
[pic]
Susipažinsime su plačiausiai naudojama hierarchine dinamine duomenų struktūra – dvejetainiu medžiu ir jos tvarkymo funkcijomis: keltimi, paieška, šalinimu, įterpimu, apėjimu ir spausdinimu.
Binarinio medžio pavyzdys:
[pic]
Dvejetainiu (arba binariniu, angl. binary) vadinamas orientuotas medis, kuriame į kiekvieną viršūnę, išskyrus šaknį, įeina viena briauna, 0 išeina ne daugiau dviejų. Tai baigtinė viršūnių aibė, kuri yra arba tuščia, arba sudaryta iš šaknies ir dviejų nesusikertančių binarinių medžių: kairiojo ir dešiniojo. Bet kurį medį mes galime suorientuoti vieną iš jo viršūnių padarydami šaknimi. Ir kiekvieną medį mes galime sutvarkyti kaip binarinį medį – perkeliant dešinėje esantį ryšį vyresniam broliui, o kairėje esantį ryšį – jaunesniam sūnui.
Medžio dalis, išeinanti iš bet kurios viršūnės, vadinama šaka. Taigi bet kuri dvejetainio medžio viršūnė turi ne daugiau dviejų šakų. Viena jų dažniausiai vadinama kairiąja, kita – dešiniąja šaka. Medžio šaknimi vadinama viršūnė, iš kurios šakos išeina, bet nė viena neįeina.
Žemiau pavaizduotas dvejetainis medis, kuriame įrašyta tokia išraiška:
(a + b/c) * (d – e * f).
Paieškos (sutvarkytas) medis
Dažniausiai medis yra sutvarkytas taip, kad kiekvienos viršūnės ti kairės šakos šaknies reikšmė mažesnė už dešinės. Toks medis vadinamas paieškos medžiu.
4 pav. Paieškos (sutvarkytas) medis
[pic]
4.3.1 Laisvų, orientuotų ir sutvarkytų medžių atvaizdavimas
Bet koki laisvą medi galima orientuoti, paskyrus vieną iš mazgų šaknimi. Bet koki orientuotą medi galima laisvai pertvarkyti. Bet koki pertvarkytą medi galima pavaizduoti kaip binarini medį pervedant dešini sąryši vyresniam broliui, o kairįjį jaunesniam sūnui.
Pavyzdys: pavaizduotos diagramos pertvarkytos ir atitinkančios binarinius medžius.
[pic]
4.3.2 Binarinių medžių atvaizdavimas
Dažnai naudojamasi sekančiais binarinių medžių atvaizdavimais:
1. Raštiška struktūra: kiekvienas mazgas atvaizduojamas tipu N, laikantis du polius (l ir r) su rodyklėmis į kairijį ir dešinįjį mazgus ir dar vieną potį i, kad saugotu informaciją apie mazgą. Medis vaizduojamas rodyklėmis į šaknį. Tipas N įprastai nustatomas sekančiu būdu: N=
record i: info; 1, r: tN end record. Dėl to pristatymas n(p)= 3p, kur p – mazgų skaičius.
2. Masyvai: visi mazgai išsidėsto masyve taip, kad visi pomedžio mazgai išsidėsto taip, kaip prieš tai buvęs mazgas. Kartu su kiekvienu mazgu saugomas mazgo indeksas, kuris yra paskutinis mazgas pomedžio duoto mazgo. Medis T atpažįstamas sekančiu būdu: T: array [L.p] of record i:
info, k: L.p end record. Dėl to pristatymas n(p )=2p.
3. Lenkiškas įrašymas: analogiška, bet vietoj ryšio fiksuojamas kiekvienas mazgas. (Pavyzdžiui, 0 reiškia, kad tai lapas, 1- kairysis ryšys, bet nėra dešinio, 2- dešinysis ryšys, bet nėra kairiojo, 3- yra abu ryšiai). Medis Tatpažįstamas sekančiu būdu: T: array [L.p] of record i: info, d: 0..3 end record. Dėl to pristatymas n(p )=2p. Jeigu mazgo laipsnis aiškus iš informacijos saugomos pačiam mazge, tai nebūtina išsaugoti pačio laipsnio. Toks medžio pristatymo būdas vadinamas lenkišku įrašymu ir įprastai naudojamas dėl išraiškų pristatymo. Tokiu atveju medžio pristatymas atrodo daug kompaktiškesnis: atminties apimtis n(p)=p.
Binarinis medis ir jo sąrašinis vaizdavimas:
[pic]
|Viršūnės |Kairioji |Dešinioji |Tėvinė |
|nr. |dukterinė |dukterinė |viršūnė |
|1 |2 |6 |0 |
|2 |3 |4 |1 |
|3 |0 |0 |2 |
|4 |0 |5 |2 |
|5 |0 |0 |4 |
|6 |7 |8 |1 |
|7 |0 |0 |6 |
|8 |0 |9 |6 |
|9 |0 |0 |8 |
Paprasčiausias sutvarkyto binarinio medžio formavimo algoritmas.
Sakykime, kad turime seką duomenų: P1, P2, … , pn, iš kurių paeiliui reikia sudaryti dvejetainio medžio struktūrą. Pirmasis P1 elementas patalpinamas šaknyje.
Toliau, antrasis p2 elementas lyginamas su pirmuoju. Jeigu p2< p1, tai prie šaknies prijungiame briauną, nukreiptą į kairę ir antrąjį elementą patalpiname šios briaunos gale. Jeigu p2> p1, tai briauną nukreipiame dešinėn. Bendru atveju, naujo pi elemento reikšmę, pradedant nuo šaknies, lyginame su medžio k-tojo elemento reikšme pk.Jeigu pipk, tai viską atliekame analogiškai dešinėn.Tokiu būdu iš kiekvienos viršūnės gali išeiti ne daugiau dviejų briaunų, kaip ir reikalaujama dvejetainiam medžiui. Jeigu požymiai sudaro gerai išmaišytą seką, tai šis algoritmas duoda gerus rezultatus.
Dvejetainis medis turėtų būti kiek galima taisyklingesnis –
subalansuotas.Subalansuotų dvejetainių medžių viršūnių laipsniai lygūs dviem (išskyrus paskutinį ir priešpaskutinį lygius).
Žemiau parodytas pagal paprasčiausią algoritmą iš skaičių sekos 5 2 18 3 8
10 14 1 2 7 6 4 sudarytas dvejetainis medis.
[pic]
5 pav. Paprasčiausiu algoritmu sudarytas dvejetainis medis
Dvejetainio medžio sudarymo ir spausdinimo programa
Aukščiau esančiame paveikslėlyje pavaizduotą dvejetainį medį sudaryti ir spausdinti gali tokia programa:
program Formavimas;
type sar=↑k;
K = record sk : real;
ka, de: sar;
end;
var medis: sar; d : sar;
F : text;
procedure Iterpti (P, R : sar) ;
var t : sar;
begin
while P <> Nil do begin begin t := P;
if R↑. sk < P↑ . sk then P := P↑ . ka else P := P↑ . de;
end;
if R↑. sk < t↑ . sk then t↑. ka := R
else t↑ . de := R;
end;
procedure Spausdinti (medis: sar) ;
const L = 100;
type mas = array [ 1 . . L ] of sar;
stekas = record nr : integer;
rodo : mas;
end;
var S: stekas; H: Boolean;
begin
S . nr := 0; H:= True;
while ( (S.nr <> 0) or (medis <> Nil) ) and H do if (medis <> Nil) and (S.nr = L ) then {kairioji medžio šaka}
begin
Write (‘ Stekas perpildytas ‘);
H := False;
end else if medis <> Nil then begin
S.nr := S.nr + 1;
{Viršūnės adresą į steką}
S.rodo [ S.nr] := medis;
medis := medist.ka; {Pereinam į kairę dukterinę viršūnę}
end else begin
{pasiekta kairiosios šakos pabaiga}
medis := S.rodo [ S.nr];
S. nr:= S.nr-1; {į tėvinę viršūnę}
Write (medis↑.sk);
Medis := medis↑.de; { į dešinę pusę}
end;
end;
begin
Assign (F, ‘duom.txt’);
Medis := Nil;
if not Eof (F) then begin {sukuria šaknį}
New (medis);
with medis↑ do begin
Read (F, sk);
ka := Nil; de := Nil;
end;
end;
while not Eof (F) do begin
New (d);
{sukuria naują viršūnę}
with d↑ do begin
Read (F, sk);
ka := Nil;
de := Nil;
end;
Iterpti (medis, d);
{viršūnę d įrašo į medį}
end;
Spausdinti (medis);
end.
Kreipiniai į procedūrą Iterpti (medis, d) įterpia naują elementą d į dinaminę struktūrą medis pagal paprasčiausią formavimo algoritmą: nuo medžio viršūnės leidžiamės „žemyn”, kol rasime tuščią rodyklės lauką. Čia ir įrašome naujo elemento rodyklę.
Procedūra Spausdinti (medis) atspausdina medžio elementų reikšmes didėjimo tvarka. Elemento, kurio reikšmę reikia spausdinti, ieškome pagal tą patį dėsnį: kairiąja medžio puse leidžiamės „žemyn” tol, kol galime (rasime reikšmę Nil). Tuomet spausdiname paskutinio elemento reikšmę ir pasukame į dešinę. Nuo čia vėl leidžiamės kairėn.
Jeigu, pasukę į dešiniąją pusę randame Nil, tai grįžtame atgal į elementą, iš kurio kairiosios pusės buvome išėję (to elemento reikšmę spausdiname ir pasukame į dešinę). Jeigu tokio elemento nėra (esame viršūnėje), tuomet jau turime rezultatą.
Medyje aplankytų elementų adresams atsiminti naudojamas masyve sudarytas stekas. Steką galima būtų realizuoti ir dinaminiu sąrašu.
Tą pačią spausdinimo procedūrą galima užrašyti paprasčiau,jeigu taikysime rekursiją. Tačiau, kadangi rekursijos gylis yra neribojamas, tai, esant didelei duomenų apimčiai gali susidaryti avarinė situacija.
procedure Spausdinti (medis: sar);
begin medis <> Nil then begin
Spausdinti (medis↑.ka);
Write (medis↑. sk);
Spausdinti (medis↑.de);
end;
end;
4.3.3 Binarinių medžių apėjimas
Didžioji dalis medžių algoritmų pritaikyti apėjimams. Galimi šie binarinių medžių apėjimai:
Tiesus (karinis) apėjimas: patekti į šaknį, apeiti keirįjį pomedį, apeiti dešinįjį pomedį.
Atvirkščias (simetrinis) apėjimas: apeiti kairįjį pomedį, patekti į šaknį, apeiti dešinįjį pomedį.
Galinis apėjimas: apeiti kairįjį pomedį, patekti į šaknį.
Išskyrus šiuos tris apėjimus, galimi dar trys atitinkami apėjimai, skiriantys vienas nuo kito peržiūrėjimo tvarka dešiniojo ir kairiojo pomedžio. Tuo baigiasi apėjimai, jeigu pristatyme užfiksuoti ryšiai „tėvas-
sūnus”.
Jeigu be „tėvo-sūnaus” ryšio yra kiti ryšiai, tai galimi kiti apėjimai.
„Medžiai”, kuriuose tušti laukai 1 ir r struktūroje N naudojami saugoti papildomus ryšius.
Galinis medžio apėjimas išreikštas a+b*c užrašomas atvirkščiu lenkišku aprašymu: abc*+.
4.3.4 Binarinio medžio algoritminis simetrinis apėjimas
Binarinio medžio apėjimas, naudojant rekursines procedūras, ne sukelia sunkumų. Sekantis akivaizdus algoritmas realizuoja daug populiaresnį simetrinį apėjimą, bet panaudojant steką.
Įėjimas: binarinis medis pristatomas raštiškoje struktūroje, r – rodyklė į šaknį.
Išėjimas: binarinio medžio nuoseklus mazgas simetrinio apėjimo tvarkoje. T:
=0; p:=r {pradžioje steko tegul p nurodo į medžio šaknį}
M: {analizuoja mazgą, kurį rodo p}
if p= nil then ifT=0 then stop {apėjimas baigtas}
end if p T {kairinis pomedis apeitas}
yield p {sekantis mazgas simetriniame apėjime}
p:=p.r {pradedam apeiti dešinįpomedį}
else p T {atsimename tekanti mazgą. .. }
p:=p.1 { . .. ir pradedame pomedžio kairijį apėjimą }
end if goto M
4.4. Medžių rūšiavimas
Šioje dalyje aptariamas vienas konkretus medžių taikymas programavime, 0
tiksliau, medžių rūšiavimas. Peržiūrima kaip teoriniai klausimai susiję, pavyzdžiui, su medžių aukščio vertinimu, praktine algoritmų realizacija, taip pat visa eile medžių rūšiavimo taikymu, pragmatiniu aspektu ir kai kuriais gretimais klausimais.
4.4.1 Asocijuotoji atmintis
Praktiniame programavime organizacijoms, duomenų saugojimui ir priėjimui prie jų, dažnai naudojamas mechanizmas, kuris paprastai vadinamas asociatyvia atmintimi. Asociatyvios atminties naudojimui, duomenys dalinami į porcijas (vadinamais įrašais) ir su kiekvienu įrašu asocijuojasi raktas.
Raktas – tai pilna sutvarkytos daugybės reikšmė, 0 įrašai gali turėti laisvą prigimtį ir skirtingus parametrus. Priėjimas prie duomenų vykdomas pagal reikšmę rakto, kuris paprastai pasirenkamas paprastu, kompaktiniu ir patogiu darbui.
Pavyzdys
Asocijuotoji atmintis naudojama daugelyje gyvenimo sričių:
1. Aiškinamasis žodynas arba enciklopedija: žodyno straipsnis yra įrašas, o raktas
– žodyno straipsnio pavadinimas (paprastai jį išskiria riebiu šri:ftu).
2. Adresų knyga: abonento vardas yra raktas, o įrašas – adreso informacija (telefonas(ai), pašto adresas ir t.t.).
3. Banko sąskaitos: sąskaitos numeris yra raktas, o įrašas – :finansinė informacija (kuri gali būti labai sudėtinga).
Tokiu būdu asocijuotoji atmintis privalo išlaikyti mažiausiai tris pagrindines operacijas: 1. idėti (raktas, įrašas);
2. rasti (raktas): įrašas;
3. pašalinti (raktas).
Kiekvienos operacijos efektyvumas priklauso nuo duomenų struktūros naudojamos dėl asocijuotosios atminties pateikimo.Asocijuotosios atminties efektyvumas bendrai priklauso nuo įvairių operacijų duotojoje konkrečioje programoje, atlikimo dažnumo santykių.
Pastaba
Tokiu būdu neįmanoma nurodyti asocijuotosios atminties organizavimo būdo, kuris būtų pačiu geriausiu visais galimais atvejais.
4.4.2 Asocijuotosios atminties realizavimo būdai
Dėl asocijuotosios atminties pateikimo naudojami sekančios pagrindinės duomenų struktūras:
1. nesutvarkytas masyvas;
2. sutvarkytas masyvas;
3.medžio rūšiavimas – binarinis medis, kurio kiekvienas mazgas turi raktą ir sekančias savybes: visuose kairiojo po medžio mazguose rakto reikšmių mažiau, o visuose dešiniojo pomedžio mazguose daugiau negu rakto reikšmė mazge;
4. lentelės išdėstymas .
Naudojant nesutvarkyto masyvo algoritmus, realizuojant asocijuotosios atminties operacijas akivaizdu:
1. Operacija „pridėti (raktas, įrašas)” realizuojama pridedant įrašą masyvo gale;
2. Operacija „rasti (raktas): įrašas” realizuojama visų masyvo įrašų ciklo patikrinimu;
3. Operacija „pašalinti (raktas)” realizuojama panaikinamo įrašo paieška, o po to visus sekančius įrašus perkeliame viena pozicija į priekį.
Sutvarkytas masyvas turi efektyvų paieškos algoritmą aprašytą sekančiame skyriuje. Likusių operacijų realizacija akivaizdi. Šiame skyriuje pagrindinis dėmesys skiriamas operacijų su medžių rūšiavimo algoritmų vykdymu.
4.4.3 Binarinės paieškos algoritmas
Naudojant sutvarkytą masyvą asocijuotosios atminties pristatymui, įrašo paieškos operacija raktu gali būti įvykdyta per laiką O(1og2 n) ( kur n-
įrašų kiekis) sekančio algoritmo pagalba, žinomas kaip binarinės paieškos algoritmas.
Algoritmas: Binarinė paieška
Įėjimas: sutvarkytas masyvas A : array [1..n] of record k: key;I: info end record; raktas a: key.
Išėjimas: įrašo indeksas su paieškos raktu a masyve A arba 0, jeigu įrašo su tokiu raktu nėra.
b : = 1 {masyvo dalies pradinis indeksas paieškai}
e : =n {masyvo dalies galinis indeksas paieškai}
while b<= e do c : =(b+e )/2 {tikrinamojo elemento indeksas (suapvalintas iki sveikų) }
if A[c].k > a then e : == c-l {tęsiame paiešką pirmoje pusėje}
else if A[c].k < a then b : = c+ 1 {tęsiame paiešką antroje pusėje}
else return c {radome ieškomą raktą}
end if end while return 0 {ieškomo rakto nėra masyve}
Pagrindimas
Šio algoritmo pagrindimui užtenka pastebėti, kad kiekviename pagrindinio ciklo žingsnyje ieškomas masyvo elementas (jei jis yra) randasi tarp (imtinai) elementų su indeksais b ir e. Kadangi paieškos diapazonas kiekviename žingsnyje mažinamas dvigubai, bendras darbingumas neviršija log
2 n.
4.4.4 Medžio rūšiavimo paieškos algoritmas
Sekantis algoritmas medžio rūšiavime randa mazgą su nurodytu raktu, jei jis ten yra.
Algoritmas: Mazgo paieška rūšiavimo medyje.
Įėjimas: rūšiavimo medis T, nurodytas rodykle į šaknį; raktas a. Išėjimas:
rodyklė p į surastą mazgą arba nil, jeigu nėra medyje tokio rakto. p : =T
{rodyklė į tikrinamąjį mazgą}
while p :;tnil do ir a< p.i then p : = p.l {tęsiame paiešką iš kairės}
else ir a > p.i then p : = p.r {tęsiame paiešką iš dešinės}
else return end ir end while
Pagrindimas
Šitas algoritmas dirba tiksliai atitikdamas rūšiavimo medžio apibūdinimą:
jeigu einamasis mazgas neieškomas, tai priklausomai nuo to, daugiau ar mažiau ieškomas raktas, lyginant su einamuoju, reikia pratęsti paiešką atitinkamai iš kairės arba iš dešinės.
4.4.5 Rūšiavimo medžio įterpimo algoritmas
Sekantis algoritmas įterpia rūšiavimo medžio mazgą su nurodytu raktu. Jeigu mazgas nurodytu raktu jau yra medyje, tai nieko nedaroma. Pagalbinė funkcija NewNode aprašyta skyrelyje.
Algoritmas Įterpimas į rūšiavimo medžio mazgą.
Įėjimas: rūšiavimo medis T, su rodykle į šaknį; faktas a.
Išėjimas: modifikuotas rūšiavimo medis T.
if T = nil then
T : = NewNode (a) {pirmas mazgas medyje}
return T
end ir p : = T {rodyklė į einamąjį mazgą}
M : {einamojo mazgo analizė}
if a< p.i then if p.1 = nil then q : = NewNode (a) {sukuriame naują mazgą}
p.1 : = q {ir prikabinam jį prie p iš kairės}
return T
else p: = p.1 {tęsiame vietos paiešką įterpimui iš kairės}
goto M
end if end if if a > p.i then if p.1 = nil then q : = NewNode (a) {sukuriame naują mazgą}
p.r : = q {ir prikabinam jį prie p iš dešinės}
return T
else p : = p.r {tęsiame vietos paiešką pastatymui iš dešinės} goto M
end if end if return T { čia pataikėt, jei jau yra toks raktas! }
Pagrindimas
Iš esmės įterpimo algoritmas analogiškas paieškos algoritmui: medyje ieškomas toks mazgas turintis laisvą ryšį naujo mazgo prikabinimui, kad nepažeisti medžio rūšiavimo sąlygų. O tiksliau, jeigu naujas raktas mažesnis už einamąjį tai jį arba galima prikabinti iš kairės Gai kairė pusė laisva), arba reikia rasti iš kairės reikiamą vietą. Analogiškai, jeigu naujas raktas didesnis už einamąjį.
4.4.6 Rūšiavimo medžio pašalinimo algoritmas
Sekantis algoritmas pašalina iš rūšiavimo medžio mazgą su nurodytu raktu.
Jeigu mazgo su nurodytu raktu nėra med)je, tai nieko nedaroma. Pagalbinės procedūros Find ir Delete, aprašytos sekančiame skyrelyje.
Sutvarkytame medyje pašalinti elementą nėra sunku. Sunkiau yra tuomet, kai šalinamas elementas turi ir kairę, ir dešinę šakas. Tokiu atveju šalinamą elementą reikia pakeisti jo kairiosios šakos pačiu dešiniausiu elementu arba jo dešiniosios šakos pačiu kairiausiu elementu. Žemiau esančiuose paveikslėliuose pavaizduotas elementų šalinimas iš sutvarkyto dvejetainio medžio.
Procedūra šalinti nagrinėja tris atvejus:
1. Elemento x medyje nėra.
2. Šalinamas elementas x turi ne daugiau vienos šakos.
3. Šalinamas elementas turi ir kairę, ir dešinę šakas.
Algoritmas 9.5. Mazgo pašalinimas iš rūšiavimo medžio
Įėjimas: rūšiavimo medis T, nurodytas rodykle į šaknį; raktas a.
Išėjimas: modifikuotas rūšiavimo medis T.
Find (T,a,p,q, s) {pašalinto mazgo paieška}
if p = nil then return T {nėra tokio mazgo – nieko daryti nereikia} end if if p.r = nil then
Delete (p,q,p.1,s) { 1 variantas, piešinio 9.11, iš kairės}
else u: =p.r if u.1 = nil then u.1 : = p.1
Delete (p,q, u,s) {2 variantas, piešinio 9.11 centre}
else
w : =u; v: =u.1
while vJ;t: nil do w: = v; v: = v.1
end while p.i : = v.i
Delete (v,w,v.r,-l) {3 variantas, piešinio dešinėje}
end if end if return T
Pagrindimas
Mazgo pašalinimas vykdomas perstatant rūšiavimo medį. Galimi trys atvejai (neskaitant to atvejo, kai šalinamojo mazgo nėra medyje ir nieko daryti nereikia).
1. Šalinamojo mazgo p dešinysis ryšys tuščias ( 9.11 piešinys kairėje).
Tokiu atveju, kairiojo pomedžio 1 mazgas prikabinamas prie tėviškojo mazgo q iš tos pačios pusės, kaip buvo prikabintas mazgas p. Rūšiavimo medžio sąlygos akivaizdžiai vykdomos.
2. Šalinamojo mazgo p dešinysis ryšys ne tuščias ir vedamas į mazgą u, kairysis ryšys – tuščias (piešinio 9.11 centre). Tokiu atveju kairiojo pomedžio 1 mazgas p prikabinamas prie mazgo u iš kairės, o pats mazgas u prikabinamas prie tėviškojo mazgo q iš tos pačios pusės, iš kurios buvo prikabintas mazgas p. Nesunku patikrinti, rūšiavimo medžio sąlygos vykdomos ir šiuo atveju.
[pic] 3. Ša1inamojo mazgo p dešinysis ryšys.. ne tuščias ir vedamas į mazgą u, kairysis ryšys ne tuščias. Kadangi žinomas medžio rūšiavimas, galima nusileisti iš mazgo u iki mazgo v, kairysis ryšys tuščias ( piešinys
9.11 dešinėje). Tokiu atveju vykdomas medžio pertvarkymas. Iš pradžių informacija mazge p pakeičiama informacija mazge v. Kadangi mazgas v yra dešiniojo pomedžio mazge p ir kairiojo pomedžio mazge u, turime p.i [pic]).
Turime: ( [pic]) h =2 h/2 ( P h =p, seka, [pic] ( log 2 p ir h ( 2 log 2
p.
Pastaba
Žinomas labiau tikslus ABL- medžio aukščio įvertinimas: h< log [pic] + 2
log 2 p.
Subalansuoti medžiai nusileidžia išlygintiems medžiams pagal paieškos greitį (mažiau nei 2 kartus), tačiau jų pirmenybė yra tame, kad žinomi subalansuoto medžio įvedimo ir išvedimo mazgų algoritmai, kurie išsaugo subalansavimą ir tuo pat metu liečia tik mazgų paskutinį skaičių. Todėl daugeliu atvejų, ABL- medis tampa geriausiu variantu pristatant medžių rūšiavimą.