Medžiai – paprasčiausia grafų klasė

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. Jungusaciklinis grafas vadinamas laisvu medžiu. Jungi grafo elementai sudaromedžius ir gaunasi miškas, sudarytas iš medžių. Jungus grafas yra medistada, 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ėssujungtos tik viena grandine. Jungūs grafo elementai sudaro medžius, 0medžiai – miškus. Jungus grafas vadinamas laisvuoju medžiu. Jungus grafasyra tada ir tik tada medis, kai jo briaunų skaičius lygus m = n – 1. Pagalviršūnės laipsnį medžiai gali būti binariniai (maksimalus viršūnės laipsnis2), 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ė, paprastaivirš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 ilgisorientuotame 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 Gvadinamas 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 jungeiskomponentais ir z paprastais ciklais. Tegul x – briauna, jungianti betkurią norimą negretimą porą į grafą G. Tada sekantys teiginiaiekvivalentū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 jomsincidentiškos dukterinėmis medžio viršūnėmis.

5. Viršūnės, kurios neturi dukterinių, vadinamos terminalinėmis arbalapais.

Medžiai pritaikomi labai įvairiai. Čia paminėsime, kad bet kurį rūšiavimoprocesą galima išreikšti medžiu. Dauguma klasifikacinių schemų ar tiesiogklasifikatorių 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. Šiviršū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 kuriosviršūnės, yra orientuotas medis, kurio šaknis yra atitinkama viršūnė. Jeilaisvame grafe bet kurią viršūnę pavadinsime šaknimi, gausime orientuotąmedį.Orientuotame medyje viršūnės V, pasiekiamos iš viršūnės U, vadinamospalikuonimis, jei tarp tam tikrų viršūnių U ir V yra laukas, tai viršūnė Uvadinama 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ųsilaisvasis 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, yraorientuotas medis su šaknimi v.6. Jeigu laisvame medyje bet kurią viršūnę pažymėsime šaknimi, gausimeorientacinį medį.

Kiekvieną laisvą medį apibrėžia ne daugiau p orientuotų medžių. Tokiubū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 pviršū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žioaukšč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 kporose neperkiriami daugybe T1, …,Ta, iš kurių yra orientuotas medis(k(=0), T={ {r}, T1 ,.., Ta} .

Daugybe Tl,…, Ta orientuotuose medžiuose tampa pomedžiais. Orientuotasmedis, turintis fiksuotą po medžių išsidėstymą, vadinamas sutvarkytumedžiu.Orientuoti ir sutvarkyti orientuoti medžiai intensyviai naudojamiprogramavime. 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ėsnukreiptos iš viršaus į apačią, todėl rodyklių galima net nevaizduoti.Tokiu būdu laisvų, orientuotų ir sutvarkytų medžių schemos grafiškai atrodoneatskiriamos, ir todėl reikalaujama išsamaus nurodymo, kokios klasės medisyra 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, arbasudaryta iš šaknies ir dviejų nesusikertančių binarinių medžių – kairiojoir 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šeinane daugiau dviejų. Tai baigtinė viršūnių aibė, kuri yra arba tuščia, arbasudaryta iš šaknies ir dviejų nesusikertančių binarinių medžių: kairiojo irdeš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 betkuri dvejetainio medžio viršūnė turi ne daugiau dviejų šakų. Viena jųdažniausiai vadinama kairiąja, kita – dešiniąja šaka. Medžio šaknimivadinama 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škosmedž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 kokipertvarkytą medi galima pavaizduoti kaip binarini medį pervedant dešinisąryši vyresniam broliui, o kairįjį jaunesniam sūnui.

Pavyzdys: pavaizduotos diagramos pertvarkytos ir atitinkančios binariniusmedž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ų paeiliuireikia sudaryti dvejetainio medžio struktūrą. Pirmasis P1 elementaspatalpinamas š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ą nukreipiamedeš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ą atliekameanalogiškai dešinėn.Tokiu būdu iš kiekvienos viršūnės gali išeiti nedaugiau dviejų briaunų, kaip ir reikalaujama dvejetainiam medžiui. Jeigupožymiai sudaro gerai išmaišytą seką, tai šis algoritmas duoda gerusrezultatus.Dvejetainis medis turėtų būti kiek galima taisyklingesnis –subalansuotas.Subalansuotų dvejetainių medžių viršūnių laipsniai lygūsdviem (išskyrus paskutinį ir priešpaskutinį lygius).Žemiau parodytas pagal paprasčiausią algoritmą iš skaičių sekos 5 2 18 3 810 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 irspausdinti 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 {kairiojimedž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ą: nuomedžio viršūnės leidžiamės “žemyn”, kol rasime tuščią rodyklės lauką. Čiair įrašome naujo elemento rodyklę.Procedūra Spausdinti (medis) atspausdina medžio elementų reikšmes didėjimotvarka. 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 (rasimereikš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 irpasukame į dešinę). Jeigu tokio elemento nėra (esame viršūnėje), tuomet jauturime rezultatą.Medyje aplankytų elementų adresams atsiminti naudojamas masyve sudarytasstekas. Steką galima būtų realizuoti ir dinaminiu sąrašu.Tą pačią spausdinimo procedūrą galima užrašyti paprasčiau,jeigu taikysimerekursiją. Tačiau, kadangi rekursijos gylis yra neribojamas, tai, esantdidelei 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 kairiojopomedž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 saugotipapildomus ryšius.Galinis medžio apėjimas išreikštas a+b*c užrašomas atvirkščiu lenkiškuaprašymu: abc*+.

4.3.4 Binarinio medžio algoritminis simetrinis apėjimas

Binarinio medžio apėjimas, naudojant rekursines procedūras, ne sukeliasunkumų. 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 thenifT=0 thenstop {apėjimas baigtas} end ifp T {kairinis pomedis apeitas}yield p {sekantis mazgas simetriniame apėjime}p:=p.r {pradedam apeiti dešinįpomedį}elsep T {atsimename tekanti mazgą. .. }p:=p.1 { . .. ir pradedame pomedžio kairijį apėjimą }end ifgoto M

4.4. Medžių rūšiavimas

Šioje dalyje aptariamas vienas konkretus medžių taikymas programavime, 0tiksliau, 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 kaikuriais gretimais klausimais.

4.4.1 Asocijuotoji atmintis

Praktiniame programavime organizacijoms, duomenų saugojimui ir priėjimuiprie jų, dažnai naudojamas mechanizmas, kuris paprastai vadinamasasociatyvia 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ėtilaisvą prigimtį ir skirtingus parametrus. Priėjimas prie duomenų vykdomaspagal reikšmę rakto, kuris paprastai pasirenkamas paprastu, kompaktiniu irpatogiu darbui.

PavyzdysAsocijuotoji atmintis naudojama daugelyje gyvenimo sričių:1. Aiškinamasis žodynas arba enciklopedija: žodyno straipsnis yra įrašas, oraktas – ž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 trispagrindines operacijas: 1. idėti (raktas, įrašas);2. rasti (raktas): įrašas;3. pašalinti (raktas).

Kiekvienos operacijos efektyvumas priklauso nuo duomenų struktūrosnaudojamos dėl asocijuotosios atminties pateikimo.Asocijuotosios atmintiesefektyvumas bendrai priklauso nuo įvairių operacijų duotojoje konkrečiojeprogramoje, 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ėsduomenų struktūras: 1. nesutvarkytas masyvas; 2. sutvarkytas masyvas; 3.medžio rūšiavimas – binarinis medis, kurio kiekvienas mazgas turiraktą ir sekančias savybes: visuose kairiojo po medžio mazguose rakto

reikšmių mažiau, o visuose dešiniojo pomedžio mazguose daugiau negu raktoreikšmė mazge; 4. lentelės išdėstymas .Naudojant nesutvarkyto masyvo algoritmus, realizuojant asocijuotosiosatminties 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 tovisus sekančius įrašus perkeliame viena pozicija į priekį.Sutvarkytas masyvas turi efektyvų paieškos algoritmą aprašytą sekančiameskyriuje. Likusių operacijų realizacija akivaizdi. Šiame skyriujepagrindinis 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šopaieš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škosalgoritmas.

Algoritmas: Binarinė paieška

Įėjimas: sutvarkytas masyvas A : array [1..n] of record k: key;I: info endrecord; raktas a: key.Išėjimas: įrašo indeksas su paieškos raktu a masyve A arba 0, jeigu įrašosu tokiu raktu nėra.b : = 1 {masyvo dalies pradinis indeksas paieškai}e : =n {masyvo dalies galinis indeksas paieškai}while b<= e doc : =(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 pagrindiniociklo ž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 log2 n.

4.4.4 Medžio rūšiavimo paieškos algoritmas

Sekantis algoritmas medžio rūšiavime randa mazgą su nurodytu raktu, jei jisten 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 returnend irend while

PagrindimasŠitas algoritmas dirba tiksliai atitikdamas rūšiavimo medžio apibūdinimą:jeigu einamasis mazgas neieškomas, tai priklausomai nuo to, daugiau armaž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. Jeigumazgas 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 Tend ir p : = T {rodyklė į einamąjį mazgą}

M : {einamojo mazgo analizė}if a< p.i thenif p.1 = nil thenq : = 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 thenif p.1 = nil thenq : = NewNode (a) {sukuriame naują mazgą}

p.r : = q {ir prikabinam jį prie p iš dešinės}return Telsep : = p.r {tęsiame vietos paiešką pastatymui iš dešinės} goto M end ifend ifreturn T { čia pataikėt, jei jau yra toks raktas! }

PagrindimasIš esmės įterpimo algoritmas analogiškas paieškos algoritmui: medyjeieškomas toks mazgas turintis laisvą ryšį naujo mazgo prikabinimui, kadnepažeisti medžio rūšiavimo sąlygų. O tiksliau, jeigu naujas raktasmaž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, jeigunaujas 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ėsprocedū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 elementuarba jo dešiniosios šakos pačiu kairiausiu elementu. Žemiau esančiuosepaveikslėliuose pavaizduotas elementų šalinimas iš sutvarkyto dvejetainiomedž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 thenreturn T {nėra tokio mazgo – nieko daryti nereikia} end ifif 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.1while vJ;t: nil do w: = v; v: = v.1end whilep.i : = v.iDelete (v,w,v.r,-l) {3 variantas, piešinio dešinėje} end ifend ifreturn T

PagrindimasMazgo pašalinimas vykdomas perstatant rūšiavimo medį. Galimi trys atvejai(neskaitant to atvejo, kai šalinamojo mazgo nėra medyje ir nieko darytinereikia). 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 mazgoq iš tos pačios pusės, kaip buvo prikabintas mazgas p. Rūšiavimo medžiosą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 kairiojopomedžio 1 mazgas p prikabinamas prie mazgo u iš kairės, o pats mazgas uprikabinamas prie tėviškojo mazgo q iš tos pačios pusės, iš kurios buvoprikabintas mazgas p. Nesunku patikrinti, rūšiavimo medžio sąlygos vykdomosir š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šinys9.11 dešinėje). Tokiu atveju vykdomas medžio pertvarkymas. Iš pradžiųinformacija mazge p pakeičiama informacija mazge v. Kadangi mazgas v yradeš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] + 2log 2 p.

Subalansuoti medžiai nusileidžia išlygintiems medžiams pagal paieškosgreitį (mažiau nei 2 kartus), tačiau jų pirmenybė yra tame, kad žinomisubalansuoto medžio įvedimo ir išvedimo mazgų algoritmai, kurie išsaugosubalansavimą ir tuo pat metu liečia tik mazgų paskutinį skaičių. Todėldaugeliu atvejų, ABL- medis tampa geriausiu variantu pristatant medžiųrūšiavimą.