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. 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 vviršū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 nneį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ų, kk(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 & GG(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 kkatalogų 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: ttN 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 ppaskutinis 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 vvaizdavimas:

[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< pp1, 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↑ . dde := 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 ssteko 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, ppragmatiniu 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 oorganizavimo 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 vvisų 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 ddvigubai, 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 tthen

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 ppač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 iiš 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ą.