Kihagyás

11 - search tree

Ebben a leckében egy olyan keresőfának nevezett adatszerkezetet fogunk implementálni, ami Inteket tárol halmazban:

  • lehet bele Intet beszúrni funkcionálisan - visszaad egy új fát, amiben pluszban ott van ez az int is; ha már eleve benne volt, akkor az adatszerkezet nem változik
  • lehet belőle Intet törölni funkcionálisan - ez is új fát ad vissza, ha nem volt benne a törölni próbált elem, akkor az adatszerkezet nem változik
  • lehet benne Intet keresni, ez egy Booleant ad vissza, igaz, ha az adott érték benne van az adatszerkezetben

A keresőfa lényege: bináris fa, melyben minden csúcsnak lehet egy bal- és egy jobb oldali gyereke (melyek szintén fák). Minden csúcsban tárol egy intet. A tulajdonság, amitől ,,keresőfa'': bármelyik csúcsot is nézzük, annak a baloldali gyerekében lévő összes csúcsban kisebb számok vannak, mint az adott csúcsban, a jobboldaliban pedig csak nagyobbak.

Az alábbi képen pl. egy keresőfát látunk, melynek a gyökércsúcsa a 8-at tárolja mint adatot:

keresőfa

Technikailag lesz egy ,,üres'' elemünk, ami nem tárol értéket, őt fogjuk mindenhol, ahol hiányzik a bal- és/vagy a jobboldali gyerek, feltüntetni mint gyereket (ez nem okoz gondot, mert felfelé nem lesz hivatkozás, csak lefelé).

Akkor hogyan néz ki ez a fenti fa az üres gyerekkel?

![keresőfa ÜRES](11/keresofaURES.png) Válasz mutatása

algebrai adattípus

Próbáljuk meg leírni, milyen algebrai adattípus adja meg nekünk ezt a Tree adatszerkezetet!

Egy `Tree` ahogy a képen is látszik, lehet **kétféle**: vagy `Ures`, vagy `Nemures` (mondjuk). Az `Ures` nem tárol semmilyen adatot, a `Nemures` **hármat** is: * magát az adatot, ami egy `Int`, * a bal gyerekre egy referencát, ami egy `Tree`, * és a jobb gyerekre is egy referenciát, ami egy `Tree`. Ez alapján írjuk fel az algebrai adattípust és implementáljuk is! Hint mutatása 
1
2
3
Tree    = Ures + Nemures
Ures    = 1
Nemures = Tree x Int x Tree
Mindez Scalában: 
1
2
3
sealed trait Tree
case object Ures extends Tree
case class Nemures( left: Tree, data: Int, right: Tree ) extends Tree
Válasz mutatása

Írjuk meg a contains, inserted és erased metódusok fejléceit, melyekről az intróban szó volt! Mik a paraméterek és a visszatérési érték típusa?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
sealed trait Tree {
  def contains( value: Int ): Boolean     // contains: int jön be, boolean ki
  def insert( value: Int ): Tree          // vissza kell adjon egy újat
  def erase( value: Int ): Tree           // ez is
}
case object Ures extends Tree {
  override def contains( value: Int ) = ???
  override def inserted( value: Int ) = ???
  override def erased( value: Int ) = ???
}
case class Nemures( left: Tree, data: Int, right: Tree ) extends Tree {
  override def contains( value: Int ) = ???
  override def inserted( value: Int ) = ???
  override def erased( value: Int ) = ???
}
A nevezéktanról: Scalában (ahol léteznek mutable adatszerkezetek is) az a jellemző metódusneveknél, hogy az `insert`, `erase`, `sort` stb. aktív igék arra utalnak, hogy **megváltoztatják az eredeti adatszerkezetet**, az `inserted`, `erased`, `sorted` nevek pedig arra, hogy **újat adnak vissza**. Válasz mutatása

handling Ures

Talán célszerű mindig a hierarchia legegyszerűbb elemein kezdeni az absztrakt metódusok implementálását. Írjuk meg az Ures objektum három függvényét!

1
2
3
4
5
6
7
8
case object Ures extends Tree {
  override def contains( value: Int ) = false //az üres fa nem tartalmaz semmit

  override def inserted( value: Int ) = 
    Nemures(Ures, value, Ures)                //így hozhatunk létre egyelemű fát: két üres gyerek + adat

  override def erased( value: Int ) = Ures     //üres fából törölve üres marad
}
Válasz mutatása

contains

Próbáljuk meg rekurzióval implementálni a contains metódust! Gondoljuk végig: hogyan keresnénk meg egy értéket? Mikor merre kéne haladni a fában?

* Ha az adat a fa gyökerében megegyezik a keresett értékkel, akkor true, benne van a fában. * Ha az adat a fa gyökerében **kisebb**, mint a keresett érték, akkor csak jobbra van értelme folytatnunk a keresést, hiszen balra csak még kisebb értékek vannak. * Ha pedig nagyobb, akkor csak balra. Hint mutatása
Az `inserted` és `erased` metódusokat most nem írom ki. 
1
2
3
4
5
6
case class Nemures( left: Tree, data: Int, right: Tree ) extends Tree {
  override def contains( value: Int ) = 
    if( data == value ) true
    else if( data < value ) right.contains( value )
    else left.contains( value )  
}
Válasz mutatása

A mintamegoldással ismét az a baj, hogy tölti a call stacket. Extrém rossz esetben egy ilyen keresőfa lehet mély, mert ebben a formában nincs garancia arra, hogy alacsony lesz (pl. ha az 1 fia a 2, annak fia 3, stb, akkor tulajdonképpen egy láncolt listánk van), ezért ez így ne maradjon: oldjuk meg, hogy ne töltse a call stacket!

Itt is működhet a privát helper metódus, de most másképp oldjuk meg: * implementáljunk egy `contains: (Tree,Int) => Boolean` függvényt, mely kap egy fát és egy intet, amit keres benne; * a fán pattern matching alapján keresse az értéket; * így már lehet tail rekurzív; * hogy hova tegyük? Deklaráljunk egy `object Tree`-t is a `trait Tree` mellett és tegyük ebbe (hogy ez pontosan mit jelent, a [companion object](../../eloadas/22)ről szóló anyagból kiderül) * rejtsük el ezt a függvényt mások elől! Hint mutatása 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
sealed trait Tree {
  def contains( value: Int ): Boolean  = Tree.contains( this, value ) //így hívjuk meg
  def inserted( value: Int ): Tree          
  def erased( value: Int ): Tree           
}
object Tree {
  @tailrec
  protected def contains( tree: Tree, value: Int ) = tree match {
    case Ures => false
    case Nemures( _, `value`, _ ) => true // ` érték szerinti egyezést kér 
    case Nemures( left, data, _ ) if ( value < data ) => contains( left, value )
    case Nemures( _, _, right ) => contains( right, value )
  }
}
Válasz mutatása

insert

Gondoljuk végig: hogyan szúrunk be értéket egy keresőfába?

Arra kell mennünk, amerre keresnénk az értéket; * ha megtaláljuk az értéket a fában, akkor le is állhatunk és visszaadhatjuk a fát változatlan formában, * ha elérünk az Ures-ig, akkor egy új olyan fát adunk vissza, melyben ez az egy adatpont van, * ha egyik sem, akkor rekurzívan beszúrjuk a megfelelő oldali fába és **létrehozunk egy új fát**, ami annyiban különbözik az eredeti fától, hogy a megváltozott részfája van rákötve Implementáljuk ezt most le egyből úgy, mint a `contains` végleges változatát! Hint mutatása 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
sealed trait Tree {
  def contains( value: Int ): Boolean  = Tree.contains( this, value ) //így hívjuk meg
  def inserted( value: Int ): Tree     = Tree.insert( this, value )
  def erased( value: Int ): Tree           
}
object Tree {
  @tailrec
  protected def contains( tree: Tree, value: Int ) = tree match {
    case Ures => false
    case Nemures( _, `value`, _ ) => true // ` érték szerinti egyezést kér 
    case Nemures( left, data, _ ) if ( value < data ) => contains( left, value )
    case Nemures( _, _, right ) => contains( right, value )
  }

  protected def insert( tree: Tree, value: Int ) = tree match {
    case Ures => Nemures( Ures, value, Ures )
    case Nemures( _, `value`, _ ) => tree
    case Nemures( left, data, _ ) if ( value < data ) =>
      tree.copy( left = insert( left, value ) )
    case Nemures( _, _, right ) =>
      tree.copy( right = insert( right, value ) )
  }
}
Itt egy eddig még nem tárgyalt nyelvi elemet látunk: a `copy` metódust. Case classokhoz automatikusan generál a fordító `copy` metódust, mely egy másolatot készít az objektumunkról (alapesetben a `tree.copy()` tehát egy új objektumot ad vissza, minden mező ugyanaz), azzal, hogy `mező = új érték` szintaxissal megadhatunk olyan mező(ke)t, melyek más értéket kapjanak. Így például a `tree.copy( left = insert(left,value) )` kifejezés visszaad egy olyan **új** fát, melynek a bal gyereke az `insert(left,value)` fa lesz, az adatmezője és a jobb gyereke pedig ugyanaz, mint `tree`nek. Válasz mutatása

A mintamegoldás nem tail rekurzív és első blikkre talán nem is világos, hogy hogyan lehet azzá tenni. Most ezt így hagyjuk, de még visszatérünk rá, mikor az úgynevezett trambulinról lesz szó.

erase

A törlés egy kicsit komplikáltabb művelet, mint a másik kettő, hiszen ha egy fa közepéről törlünk egy elemet, valamit oda kell rakjunk, hogy továbbra is maradjon egy fánk. Erre egy megoldás a következő:

  • Ha üres fából akarunk törölni, semmi nem történik, visszakapjuk az üres fát.
  • Ha a törlendő adat nagyobb a fa gyökerében lévő adatnál:
    • a jobb részfából töröljük az adatot, kapunk egy új fát,
    • készítünk egy új fát, ami pont mint a régi, csak a jobb részfája a törlés utáni új fa lesz
  • Ha a törlendő adat kisebb, akkor mint az előző, csak balra.
  • Ha egyenlő, akkor ezt a pontot kell töröljük és visszaadnunk egy új fát.
    • ha nincs bal gyerek: akkor visszaadhatjuk a jobb gyereket, az pont jó lesz.
    • ha nincs jobb gyerek: adjuk vissza a balt.
    • ha mindkettő van:
      • keressük meg (mondjuk) a jobb részfa legkisebb elemét (ez még minidig nagyobb, mint a bal összes eleme)
      • töröljük ki ezt az elemet a jobb részfából, kapunk egy új jobb részfát
      • hozzunk létre új fát, melyben az adat ez a legkisebb elem, a bal részfa mint volt, a jobb meg ez az új

Ehhez szükség van egy minimumkeresésre nemüres keresőfában. Implementáljuk ezt is!

Addig kell mennünk balra, amíg csak lehet: 
1
2
3
4
5
6
7
object Tree {
  protected def min( tree: Tree ): Int = tree match {
    case Ures => ???  //ezt nem így fogjuk később csinálni, most jó lesz egyelőre
    case Nemures( Ures, value, _ ) => value
    case Nemures( left, _, _ ) => min( left )
  }
}
Válasz mutatása

Ezzel a függvénnyel felvértezve a törlés műveletünk nem bonyulult, bár hosszabb, mint az eddigiek, több eset van a mintaillesztésben:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
object Tree {
  protected def erase( tree: Tree, value: Int ): Tree = tree match {
    //üres fából nem fáj a törlés
    case Ures => Ures

    //ha jobbra kell menni
    case Nemures( _, data, right ) if ( data < value ) =>
      tree.copy( right = erase( right, value ) )

    //ha balra kell menni
    case Nemures( left, data, _ ) if ( value < data ) =>
      tree.copy( left = erase( left, value ) )

    //ha megtaláltuk és nincs bal gyerek
    case Nemures( Ures, _, right ) =>
      right

    //ha megtaláltuk és nincs jobb gyerek
    case Nemures( left, _, Ures ) =>
      left

    //ha megtaláltuk és van két gyerek:
    case Nemures( _, _, right ) => {
      //vegyük elő a minimumot a jobb részfából
      val minimum = min( right )
      //töröljük
      val newRight = erase( right, minimum )
      //készíthetjük az új fát
      tree.copy( right = newRight, data = minimum ) //és ez az érték amit kapunk
    }
  }
}
A `copy` metódusban több mezőt is megváltoztathatunk nevük alapján; aki nem szerepel, az másolódik, jelen esetben a `tree.left`. Ne felejtsük el, hogy itt csak referenciák, ,,pointerek'' vannak adattagként, így maga a `copy` metódus gyorsan fut, összesen három darab adatmezőt kell másolni, amiben mindben egy-egy referencia van. Válasz mutatása

Ez az implementáció így ismét nem tail rekurzív - hogy azzá tegyük, még várnunk kell egy keveset.

Utolsó frissítés: 2021-02-07 23:06:47