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ą.