Parengė Justina Burneikaitė, Ana Griščenko

ADT  Lentelės

 

Duomenų struktūras galima suskirstyti į  orientuotas pagal poziciją (position oriented) ir pagal reikšmę (value oriented). Susipažinkime su orientuotomis pagal reikšmę ADT lentelėmis (ADT tables).  Su jomis galima atlikti tokias operacijas:

 

Operacijos, grindžiamos duomenų reikšmėmis, o ne pozicijomis, yra pakankamai paplitusios. Pateiksime kelis pavyzdžius operacijų pagal reikšmes, o ne pagal pozicijas:

 

Miestas

Šalis

Gyventojų skaičius

Atėnai

Graikija

2,500,000

Barselona

Ispanija

1,800,000

Kairas

Egiptas

9,500,000

Londonas

Anglija

9,400,000

Niujorkas

JAV

7,300,000

Paryžius

Prancūzija

2,200,000

Roma

Italija

2,800,000

Toronto

Kanada

3,200,000

Venecija

Italija

300,000

 

 

Lentelė sudaryta iš trijų pagrindinių dalių: miestai, šalys, gyventojų skaičius. Vieni duomenys yra svarbesni už kitus. Pavyzdžiui, norėdami sužinoti Londone gyvenančių žmonių skaičių, mes turėtume peržvelgti miestų pavadinimų stulpelį, pradedant nuo viršaus, kol surasime Londoną. Tačiau žinodami, kad miestai surūšiuoti pagal abėcėlę, galime naudoti dvejetainę paiešką ir pradėti ieškoti nuo vidurio ir pan. (tai yra efektyviau). Bet jeigu mes norime rasti, pvz., didžiausią miestą Italijoje, turime peržiūrėti visą lentelę, todėl tas faktas, kad miestų pavadinimai išdėstyti abėcėlės tvarka nepadeda išspręsti šios problemos. 

 

Norint suprogramuoti tokią abstraktaus duomenų tipo lentelę reikia organizuoti duomenis taip, kad galima būtų atlikti paiešką pagal reikšmę, o ne pagal poziciją. Patogiausia apibrėžti jos elementus record tipu o vieną iš laukų pažymėti paieškos raktu (search key) .  Pavyzdžiui, jei dažnai reikia gauti informaciją apie miestus tai ” Miestas” gali būti paieškos raktu.

 

ADT lentelės bendra realizacija: 

 

unit DataDef;

interface

  type Tkey=...;

  type Tdata=...;

implementation

...

end.

 

unit ADT_Table;

uses DataDef;

interface

  type TTable=...;

  function Create(var L: Table):boolean;

  function Insert (var T: Table; Key: Tkey;

                   Elem: TData):boolean;

  function Retrieve(var T: Table; Key: Tkey;

                    var GetElem: TData):boolean;

  function Delete(var T: TTable; K: TKey):boolean;

  procedure Output(var T: TTable);

  function Destroy(var T: TTable):boolean

end.          


Medis. Dvejetainis medis. Dvejetainis paieškos medis.

 

1. Medžiai yra hierarchinės struktūros, t.y. tarp medžio viršūnių yra ”tėvo-vaiko” santykiai. Paprastas medis atrodo taip:

 

Oval: F
Oval: E
Oval: D
Oval: C
Oval: A
Oval: B
                                                      

 

 

 

 

 

                              

                                                 1 pav.

 

A, B, C, D, E, F – medžio viršūnės (nodes). A yra B ir C tėvas (parent), analogiškai, B yra D, E ir F tėvas, o B ir C yra tėvo A vaikai (children).B ir C turi tą patį tėvą, todėl jie vadinami broliais (siblings). A neturi tėvo ir vadinama medžio šaknimi (root). Jei viršūnė neturi vaikų, ji vadinama lapu (leaf). 1 pav. lapai yra D, E, F ir C.

    Medis, kuris neturi viršūnių yra tuščias (empty).   

 

2. Dvejetainis medis (binary tree) – tai toks medis, kurio kiekviena viršūnė turi ne daugiau kaip 2 vaikus.

Medis yra dvejetainis, jeigu:

·        tuščias,

·        arba yra pavidalo,

 

r

Tk       Td

 

kur r – viršūnė, Tk kairysis pomedis (left subtree) ir Td dešinysis pomedis (right subtree) D taip pat yra dvejetainiai medžiai.  Dvejetainio medžio pavyzdys:

 

 

Oval: L
Oval: A
                        

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                       2 pav.

 

3. Medžio aukštis ir viršūnės lygis. Medžio aukštis (height) – tai viršūnių skaičius nuo šaknies iki toliausio lapo. Pavyzdžiui, 2 pav. medžio aukštis yra 5 (ieškojome atstumo nuo A iki L). Aukštį galima rasti naudojant viršūnės lygio (level) apibrėžimą:

·        Jei n medžio šaknis, tai jos lygis 1.

·        Jei n nėra medžio šaknis, jos lygis vienetu didesnis už tėvo lygį.

 

Tada aukštį galima apibrėžti taip:

·        Jei medis tuščias, jo aukštis  0.

·        Jei medis nėra tuščias,  jo aukštis lygus maksimaliam viršūnių lygiui

 

4. Pilnas (full) dvejetainis medis  tai medis, kurio aukštis h , turi visus lapus h lygyje ir visos viršūnes, kurių  aukštis mažesnis už  h, turi 2 vaikus. Pilno dvejetainio medžio, kurio aukštis 3, pavyzdys:

 

 

Oval:  
                        

 

 

 

 

 

 

 

                                                      3 pav.

 

 

Labai patogu naudotis šiais rekursyviais apibrėžimais :

·        Jei T yra tuščias, tai T yra pilnas dvejetainis medis, kurio aukštis 0;

·        Jei T nėra tuščias ir aukštis h > 0 , tai T yra pilnas dvejetainis medis, jeigu jo šaknies pomedžiai irgi yra pilni dvejetainiai medžiai

Šie apibrėžimai yra panašūs į dvejetainių medžių rekursinius apibrėžimus.

 

5. Užbaigtas (complete) dvejetainis medis, kurio aukštis h, tai dvejetainis medis, kuris yra pilnas iki aukščio h-1, o pradedant nuo lygio h pildomas iš kairės į dešinę. Kitaip tariant, dvejetainis medis T, kurio aukštis h yra iki galo užbaigtas, kai:

                                

Oval:  
                        

                                                

 

 

 

 

 

 

 


                                 

 

                                                           4 pav.

 

 

                                                                   

 

6. Subalansuotas pagal aukštį (height balanced) medis tai medis, kurio kiekvienos viršūnės kairiojo ir dešiniojo pomedžio aukščiai skiriasi ne daugiau kaip vienu lygiu. Dvejetainis medis yra visiškai subalansuotas (completely balanced), jei kairieji ir dešinieji kiekvienos viršūnės pomedžiai yra to pačio aukščio..

 

 

 

7. Dvejetainis paieškos medis (binary search tree) – tai dvejetainis medis, kuris surūšiuotas pagal reikšmes jo viršūnėse. Kiekvienai viršūnei jis tenkina tokias tris savybes:

  1. n-osios viršūnės reikšmė yra didesnė už visas reikšmes jos kairiąjame pomedyje.
  2. n-osios viršūnės reikšmė yra mažesnė už visas reikšmes jos dešiniąjame pomedyje.
  3. Kairysis ir dešinysis pomedžiai yra dvejetainiai paieškos medžiai.

 

          

Dabar pateiksime kelias svarbias teoremas:

 

Teorema 1: Pilnas h (h >= 0) lygio medis turi 2h – 1 viršūnių.

 

Teorema 2: H lygio medis turi maximaliai. 2h – 1 viršūnę.

 

Teorema 3: N viršūnių medžių minimalus aukštis yra [log2(N+1)].