Adatszerkezetek és algoritmusok

Adatszerkezetek és algoritmusok 10. El®adás Bináris keresési fák

2010. január 8.

Bevezet®

Fa adatszerkezet és m¶veletei

Bevezet®

10. El®adás Bináris keresési fák Adatszerkezetek és algoritmusok

Binkerfa

Kupac

Összefoglaló

Bevezet®


Binkerfa

El®z® órák anyagainak áttekintése

Ismétlés

Adatszerkezetek osztályozása Sor, Verem, Lengyelforma Statikus, tömbös reprezentáció Dinamikus, láncolt reprezentáció

Láncolt lista Lassú rendez® algoritmusok


Kupac

Összefoglaló

Bevezet®


Binkerfa

Kupac

El®z® órák anyagainak áttekintése

Ismétlés Hierarchikus adatszerkezetek A hierarchikus adatszerkezet olyan

hA, R i

rendezett pár,

amelynél van egy kitüntetett r elem, ez a gyökérelem, úgy, hogy: r nem lehet végpont

∀a ∈ A \ {r } ∀a ∈ A \ {r }

elem egyszer és csak egyszer végpont elem r-b®l elérhet®

Az adatelemek között egy-sok jelleg¶ kapcsolat áll fenn. Minden adatelem csak egy helyr®l érhet® el, de egy adott elemb®l akárhány adatelem látható (pl. fa, összetett lista, B-fa). A hierarchikus adatszerkezetek valamilyen értelemben a lista általánosításai. 10. El®adás Bináris keresési fák Adatszerkezetek és algoritmusok

Összefoglaló

Bevezet®


Fa adatszerkezet


Binkerfa

Kupac

Összefoglaló

Bevezet®


Binkerfa

Kupac

Fa adatszerkezet

Fa adatszerkezet

A fa egy hierarchikus adatszerkezet, mely véges számú csomópontból áll, és igazak a következ®k: Két csomópont között a kapcsolat egyirányú, az egyik a kezd®pont, a másik a végpont. Van a fának egy kitüntetett csomópontja, ami nem lehet végpont. Ez a fa gyökere. Az összes többi csomópont pontosan egyszer végpont.


Összefoglaló

Bevezet®


Binkerfa

Kupac

Fa adatszerkezet

Fa adatszerkezet

A fa rekurzív deníciója: A fa vagy üres, vagy Van egy kitüntetett csomópontja, ez a gyökér. A gyökérhez 0 vagy több diszjunkt fa kapcsolódik. Ezek a gyökérhez tartozó részfák. A fával kapcsolatos algoritmusok gyakran rekurzívak.


Összefoglaló

Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa adatszerkezet

Fa deníciók I A fa csúcsai az adatelemeknek felelnek meg, Az élek az adatelemek egymás utáni sorrendjét határozzák meg egy csomópontból az azt követ®be húzott vonal egy él. A gyökérelem a fa els® eleme, amelynek nincs megel®z®je.

Levélelem a fa azon eleme, amelynek nincs rákövetkez®je. Közbens® elem az összes többi adatelem. Minden közbens® elem egy részfa gyökereként tekinthet®, így a fa részfákra bontható:

részfa: t részfája a-nak, ha az a gyökere, azaz közvetlen megel®z® eleme t-nek, vagy t részfája a valamely részfájának 10. El®adás Bináris keresési fák Adatszerkezetek és algoritmusok

Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa adatszerkezet

Fa deníciók II Elágazásszám: közvetlen részfák száma A fa szintje a gyökért®l való távolságot mutatja. A gyökérelem a 0. szinten van. A gyökérelem rákövetkez®i az 1. szinten. stb.

A fa szintjeinek száma a fa magassága. További deníciók

Csomópont foka: a csomóponthoz kapcsolt részfák száma Fa foka: a fában található legnagyobb fokszám Levél: 0 fokú csomópont Elágazás (közbens® vagy átmen® csomópont):

>0

fokú

csomópont

Szül® (®s) : kapcsolat kezd®pontja (csak a levelek nem szül®k) 10. El®adás Bináris keresési fák Adatszerkezetek és algoritmusok

Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa adatszerkezet

Fa deníciók III Gyerek (leszármazott): kapcsolat végpontja (csak a gyökér nem gyerek) Ugyanazon csomópont leszármazottai egymásnak testvérei

Szintszám: gyökért®l mért távolság. A gyökér szintszáma 0. Ha egy csomópont szintszáma n , akkor a hozzá kapcsolódó csomópontok szintszáma n

+ 1.

Útvonal: az egymást követ® élek sorozata Minden levélelem a gyökért®l pontosan egy úton érhet® el.

Ág: az az útvonal, amely levélben végz®dik Üresfa az a fa, amelyiknek egyetlen eleme sincs.


Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa adatszerkezet

Fa deníciók IV Fa magassága: a levelekhez vezet® utak közül a leghosszabb. Mindig eggyel nagyobb, mint a legnagyobb szintszám.

Minimális magasságú az a fa, amelynek a magassága az adott elemszám esetén a lehet® legkisebb. (Valójában ilyenkor minden szintre a maximális elemszámú elemet építjük be.) Egy fát kiegyensúlyozottnak nevezünk, ha csomópontjai azonos fokúak, és minden szintjén az egyes részfák magassága nem ingadozik többet egy szintnél.

Rendezett fa: ha az egy szül®höz tartozó részfák sorrendje lényeges, azok rendezettek.


Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa adatszerkezet

Fa adatszerkezet Gyökér

0. szint 2 Részfa 1. szint

2. szint


Levél 6

5

7

4

0

Bevezet®


Binkerfa

Kupac

Összefoglaló

Bináris fa

Bináris fa A bináris fa olyan fa, amelynek csúcspontjaiból maximum 2 részfa nyílik (azaz fokszáma 2). A szül® mindig a gyerekek között helyezkedik el. (Ennek a bejárásoknál lesz szerepe.) Egy bináris fa akkor tökéletesen kiegyensúlyozott, ha minden elem bal-, illetve jobboldali részfájában az elemek száma legfeljebb eggyel tér el.

Teljesnek nevezünk egy bináris fát, ha minden közbens® elemének pontosan két leágazása van.

Majdnem teljes: ha csak a levelek szintjén van esetleg hiány.


Bevezet®


Binkerfa

Kupac

Bináris fa

Speciális bináris fa Kiszámítási- vagy kifejezésfa Az a struktúra, amely egy nyelv szimbólumai és különböz® m¶veletei közötti precedenciát jeleníti meg. Aritmetikai kifejezések ábrázolására használják. Minden elágazási pont valamilyen operátort, A levélelemek operandusokat tartalmaznak. A részfák közötti hierarchia fejezi ki az operátorok precedenciáját, illetve a zárójelezést. A következ® kifejezés fája:


((10/3) − x ) + (5 ∗ y 2 )

Összefoglaló

Bevezet®


Binkerfa

Kupac

Bináris fa

Speciális bináris fa + / 10 10. El®adás Bináris keresési fák Adatszerkezetek és algoritmusok

* x

3

5

^ y

2

Összefoglaló

Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa m¶veletek

Fa m¶veletek I Lekérdez® m¶veletek: Üres-e a fa struktúra Gyökérelem lekérdezése Meghatározott elem megkeresése, az arra vonatkozó referencia visszaadása Módosító m¶veletek: Üres fa létrehozása konstruktor Új elem beszúrása Meghatározott elem kitörlése Összes elem törlése Egy részfa törlése 10. El®adás Bináris keresési fák Adatszerkezetek és algoritmusok

Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa m¶veletek

Fa m¶veletek II

Részfák kicserélése egymással Gyökér megváltoztatása Fák bejárása. Megadott stratégia (algoritmus szerint végiglépkedni az elemeken.)


Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa m¶veletek

Bejárások

Rekurziós módszerek tetsz®leges fa esetén: Pre-order bejárás (El®ször a gyökér kiírása (érintése) majd a részfák ugyanilyen módszer¶ bejárása) Post-oreder bejárás (El®ször a részfák bejárása, majd legvégül a gyökér érintése) Bináris fák esetén még egy bejárási módszer: In-order bejárás (El®ször a balgyerek bejárása, majd a gyökér érintése, azután a jobbgyerek bejárása) Például tekintsük a következ® fát.


Bevezet®


Binkerfa

Kupac

Fa m¶veletek

Bejárások példák 6 4 2 1 10. El®adás Bináris keresési fák Adatszerkezetek és algoritmusok

9 0

3

7

5 8

Összefoglaló

Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa m¶veletek

Bejárások példák

Preorder 6, 4, 2, 1, 3, 0, 9, 7, 5, 8

Postorder 1, 3, 2, 0, 4, 7, 8, 5, 9, 6 Mivel bináris fa volt a példa ezért lehetséges az inorder bejárás is: Inorder 1, 2, 3, 4, 0, 6, 7, 9, 8, 5


Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa reprezentáció

Fa reprezentáció

Általános fa esetén:

Balgyerek-jobbtestvér: Minden csomópont ismeri a szül®jét, egyetlen (legbaloldalibb) gyermekét és a közvetlen jobbtestvért. Ezzel lehetséges, hogy bármely csomópontnak tetsz®leges gyereke legyen, amik gyakorlatilag egy láncolt listát alkotnak.

Multilistás ábrázolás: Minden csomópont egy láncolt lista. A lista els® eleme tartalmazza az adatot, a többi csomópont már csak hivatkozásokat a leszármazottakra (gyermekcsomópontokra)


Bevezet®


Binkerfa

Kupac

Fa reprezentáció

Fa reprezentáció példa

2

6

5


7

4

0

Összefoglaló

Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa reprezentáció

Fa reprezentáció Bal gyerek - Jobb testvér null

2

6

null

4

null null

5

7 null


0 null

null null

Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa reprezentáció

Fa reprezentáció Multilista

2

null

6

null


4

5

7

0

null

null

null

null

Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa reprezentáció

Fa reprezentáció

Bináris vagy korlátos fokszámú fa esetén:

Aritmetikai ábrázolás: Tömbben is lehetséges, szintfolytonosan. (Balra tömörített, minimális magasságú fa esetén ideális lehet.)

Láncolt ábrázolás: Minden csomópont ismeri a szül®jét, valamint a jobb és balgyerekét. (Ez általánosítása a kétirányú láncolt listának.)


Bevezet®


Binkerfa

Kupac

Fa reprezentáció

Fa reprezentáció Példa 6 4 2 1 10. El®adás Bináris keresési fák Adatszerkezetek és algoritmusok

9 0

3

7

5 8

Összefoglaló

Bevezet®


Binkerfa

Kupac

Fa reprezentáció

Fa reprezentáció Példa

Aritmetikai ábrázolása: 6

4

9

2

0


7

5

1

3

-

-

-

-

8

-

Összefoglaló

Bevezet®


Binkerfa

Kupac

Összefoglaló

Fa reprezentáció

Fa reprezentáció Példa null

6

4

9

2

0 null

1 null

7 null

null

5 null

null

3 null

null


8 null

null

null

Bevezet®


Binkerfa

Bináris keresési fák


Kupac

Összefoglaló

Bevezet®


Binkerfa

Kupac

Összefoglaló



A rendezési fa (vagy keres®fa) olyan fa adatszerkezet, amelynek kialakítása a különböz® adatelemek között meglév® rendezési relációt követi. A fa felépítése olyan, hogy minden csúcsra igaz az, (bináris esetben) hogy a csúcs értéke nagyobb, mint tetsz®leges csúcsé a t®le balra lév® leszálló ágon és a csúcs értéke kisebb minden, a t®le jobbra lév® leszálló ágon található csúcs értékénél. A T fa bármely x csúcsára és bal (x ) bármely y csúcsára és

jobb (x ) bármely z csúcsára y


<x
Bevezet®


Binkerfa

Kupac

Összefoglaló



A rendezési fa az ®t tartalmazó elemek beviteli sorrendjét is visszatükrözi. Ugyanazokból az elemekb®l különböz® rendezési fák építhet®k fel. Els® sorrend 6,3,1,9,7,5,10

Második sorrend 9,7,6,5,10,3,1


Bevezet®


Binkerfa

Kupac


Fa reprezentáció Példa 9

6 3 1

9 5

7

7 10

6 5 3 1


10

Összefoglaló

Bevezet®


Binkerfa

Kupac

Összefoglaló


Bináris keresési fák tulajdonság

Fontos tulajdonság: inorder bejárással a kulcsok rendezett sorozatát kapjuk. Az algoritmus helyessége a bináris-keres®-fa tulajdonságból indukcióval adódik. Egy n csúcsú bináris keres® fa bejárása

O(n)

ideig tart, mivel a

kezd®hívás után a fa minden csúcspontja esetében pontosan kétszer (rekurzívan) meghívja önmagát, egyszer a baloldali részfára, egyszer a jobboldali részfára.


Bevezet®


Binkerfa

Kupac

Összefoglaló

Bináris keresési fák m¶veletek

Bináris keresési fák keresés m¶velet Keresés: A T fában keressük a k kulcsú elemet (csúcsot) Ha ez létezik, akkor visszaadja az elem címét, egyébként NULL-t. Az algoritmust megadjuk rekurzív és iteratív megoldásban is, ez utóbbi a legtöbb számítógépen hatékonyabb.

Fában-keres(x, k) rekurzív HA x = NULL VAGY k = kulcs[x] akkol return x HA k < kulcs[x] AKKOR RETURN Fában-keres(bal[x], k) KÜLÖNBEN RETURN Fában-keres(jobb[x], k) 10. El®adás Bináris keresési fák Adatszerkezetek és algoritmusok

Bevezet®


Binkerfa


Bináris keresési fák keresés m¶velet

Fában-keres(x, k) iteratív CIKLUS AMÍG x 6= NULL ÉS k 6= kulcs[x] HA k < kulcs[x] AKKOR x ← bal[x] KÜLÖNBEN x ← jobb[x] RETURN x


Kupac

Összefoglaló

Bevezet®


Binkerfa

Kupac

Összefoglaló


Bináris keresési fák Minimum keresés Minimum keresés: tegyük fel, hogy T

6=

NULL Addig követjük a

baloldali mutatókat, amíg NULL referenciát nem találunk.

Fában-minimum (T) iteratív x ← gyökér[T] CIKLUS AMÍG bal[x] 6= NULL x ← bal[x] RETURN x Helyessége a bináris-keres®-fa tulajdonságból következik. Lefut

O(h)

id® alatt, ahol h a fa magassága.

Hasonlóan megkereshet® a maximum érték is, ami a legjobboldalibb elem.


Bevezet®


Kupac (Heap)


Binkerfa

Kupac

Összefoglaló

Bevezet®


Binkerfa

Kupac

Összefoglaló

Bináris fák teljessége

Bináris fák teljessége Egy bináris fa teljes, ha a magassága h , és

h

2

−1

csomópontja van

Egy h magasságú bináris fa majdnem teljes

⇐⇒

üres; vagy: a magassága h , és a bal részfája h

majdnem teljes és jobb részfája h

−2


−1

magas és

magas és teljes;

vagy: a magassága h , és a bal részfája h jobb részfája h

−1 −1

magas és teljes és

magas és majdnem teljes.

Bevezet®


Binkerfa

Kupac

Összefoglaló


Bináris fák teljessége Heap tulajdonság Gyakorlatilag ez azt jelenti, hogy a majdnem teljes fákat balról töltjük fel. (Avagy szintenként haladunk a feltöltéssel és balról jobbra . . . ) Egy majdnem teljes bináris fa heap (kupac) tulajdonságú

⇐⇒

üres (vagy) a gyökérben lév® kulcs nagyobb, mint mindkét gyerekében, és mindkét részfája is heap tulajdonságú Reprezentálásuknál kihasználjuk a tömörítettséget és majdnem teljességet aritmetikai reprezentációval tömbben tároljuk az értékeket és az egy indexfüggvény számítja a szül®t és a gyerekeket.


Bevezet®


Binkerfa

Kupac

Összefoglaló


Kupac Példa

X K A


O D

L

M

Bevezet®


Binkerfa

Kupac

Összefoglaló

Kupac M¶veletek

Kupac Gyökér törlése

A gyökér a legnagyobb elem. Eltávolítása után a legalsó szint legjobboldalibb elemét tesszük fel a helyére, hogy a majdnem teljes tulajdonság megmaradjon. Ezzel elrontjuk kupac tulajdonságot, amit helyre kell állítani: Cseréljük fel a gyökeret a nagyobb gyerekével A felcserélt ágon ismételjuk a kupac tulajdonság helyreállítását, amíg szükséges.


Bevezet®


Binkerfa

Kupac

Kupac M¶veletek


X K A


O D

L

M

Összefoglaló

Bevezet®


Binkerfa

Kupac

Kupac M¶veletek


M K A


O D

L

Összefoglaló

Bevezet®


Binkerfa

Kupac

Összefoglaló

Kupac M¶veletek

Kupac Beszúrás

Amikor beszúrunk, tegyük a következ® szabad pozícióra, a legalsó szint legjobboldalibb elemének tesszük fel a helyére, hogy a majdnem teljesség megmaradjon. Ezzel elrontjuk kupac tulajdonségot, amit helyre kell állítani: Cseréljük fel az újonnan beszúrtat a szül®jével, amíg nagyobb az új a szül®jénél. (Ismételjük . . . )


Bevezet®


Binkerfa

Kupac

Összefoglaló

M¶veletigények

Kupac M¶veletigény A kupacnál a beszúrás és maximum törlés m¶veletigénye, legfeljebb a fa magasságával arányos (O(h )), ami az

O(log n)).

A kupacot fejjel lefelé is fel lehet építeni, amikor is a gyökérben a legkisebb elem lesz. Indexfüggvények aritmetikai reprezentáció esetén:

Balgyerek(k) RETURN 2k Jobbgyerek(k) RETURN 2k+1 Szülö(k) RETURN bk/2c 10. El®adás Bináris keresési fák Adatszerkezetek és algoritmusok

Bevezet®


Binkerfa

Kupac

Összefoglaló

M¶veletigények

Kupac M¶veletigény Ennek megfelel®en a kupac adatszerkezet használható rendezésre is. Minden, rendezend® elemet beszúrunk egy kupacba, majd a gyökeret eltávolítva megkapjuk a legnagyobb elemet. Az eltávolításokat folytatva egy rendezést kapunk eredményül. M¶veletigény

O(n log n) n törlés: O(n log n) Összesen: O(n log n )

n beszúrás:

Ami jobb, mint a lassú rendezések.


Bevezet®


Összefoglaló


Binkerfa

Kupac

Összefoglaló

Bevezet®


Binkerfa

Összefoglaló

Összefoglaló

Hiearchikus adatszerkezetek ismétlés Fák Bináris keresési fák Kupac Bejárások


Kupac

Összefoglaló

Bevezet®


Binkerfa

Kupac

Felhasznált el®adások

Felhasznált el®adások

Adatszerkezetek és algoritmusok 6-7. el®adás Nyékyné Gaizler Judit (Illetve új anyagok)


Összefoglaló

Adatszerkezetek és algoritmusok

Recommend Documents