Bináris keresőfa

Utasítások

Számok beszúrása és keresése bináris fában.

Amikor rendezett adatokat kell ábrázolnunk, egy tömb nem jó adatszerkezet.

Tegyük fel, hogy van egy [1, 3, 4, 5] tömbünk, és hozzáadunk 2-t, így [1, 3, 4, 5, 2] lesz. Most újra rendeznünk kell a teljes tömböt! Ezen javíthatunk, ha felismerjük, hogy csak helyet kell csinálnunk az új elemnek: [1, nil, 3, 4, 5], majd be kell szúrnunk az elemet az imént készített helyre. Ez azonban még mindig azt igényli, hogy sok elemet eggyel lejjebb toljunk.

A bináris keresőfák viszont sokkal hatékonyabban tudnak működni rendezett adatokon.

Egy bináris keresőfa összekapcsolt csomópontok sorozatából áll. Minden csomópont tartalmaz egy adatot (például a 3-as számot), valamint egy left és egy right nevű változót. A left és right változók nil-re vagy más csomópontokra mutatnak. Mivel ezeknek a más csomópontoknak is vannak további csomópontok alattuk, azt mondjuk, hogy a left és right változók részfákra mutatnak. A bal részfa minden adata kisebb vagy egyenlő, mint az aktuális csomópont adata, a jobb részfa minden adata pedig nagyobb, mint az aktuális csomópont adata.

Például ha lenne egy 4-es adatot tartalmazó csomópontunk, és hozzáadnánk a 2-es adatot, a fánk így nézne ki:

      4
     /
    2

Ha ezután hozzáadnánk a 6-ot, így nézne ki:

      4
     / \
    2   6

Ha ezután hozzáadnánk a 3-at, így nézne ki

       4
     /   \
    2     6
     \
      3

És ha ezután hozzáadnánk az 1-et, 5-öt és 7-et, így nézne ki

          4
        /   \
       /     \
      2       6
     / \     / \
    1   3   5   7

Köszönet

A képeket habere-et-dispertire készítette a Till Tantau-féle PGF/TikZ segítségével.

Megvalósítás

Hatékony és módosítható fastruktúra megvalósítása a Cairo nyelvben (vagy bármely tisztán funkcionális, változtathatatlan memóriájú nyelvben) komoly kihívást jelent, mert ezeket a nyelveket eleve arra tervezték, hogy ne változtassák meg az adatokat, miután létrejöttek. Ez a változtathatatlanság azt jelenti, hogy egy facsomópontot nem frissíthetsz közvetlenül: valahányszor módosítod a fát, annak egy új változatát kell létrehozni.

Hogy lássuk, miért van ez így, képzelj el egy egyszerű bináris fastruktúrát, amelyben minden csomópontnak van bal és jobb gyermeke. Tegyük fel, hogy egy ilyen kis fából indulunk ki:

       1
      / \
     2   3

Most tegyük fel, hogy hozzá szeretnénk adni egy új 4 csomópontot a 2 csomópont bal gyermekeként. Egy tisztán funkcionális nyelvben (például Cairóban vagy Haskellben) a memória változtathatatlan, ezért a 4 csomópontot nem adhatjuk hozzá egyszerűen közvetlenül a 2-höz. Ehelyett a gyökértől a módosított csomópontig vezető úton minden csomópontból új változatot kell létrehoznunk, mert ezen az úton minden csomópont egy új vagy módosított részfára mutat.

Így nézne ki a folyamat:

1. A 4-es csomópont hozzáadása a 2-es csomóponthoz:

   • Hozd létre a 2 csomópont új változatát, amelynek most a 4 a bal gyermeke.

       2'
      / 
     4   
   

2. A gyökércsomópont frissítése:

   • Mivel az 1 csomópont eredetileg a régi 2-re mutatott, létrehozzuk az 1' gyökércsomópont új változatát, amely most a bal oldalon a frissített 2' csomópontra mutat, a jobb oldalon pedig megtartja a 3 csomópontot.

       1'
      / \
     2'  3
   

A kapott fa tehát ez lesz:

       1'
      / \
     2'  3
    /
   4

Ez az új fa (1') továbbra is hasonlít az eredetire, de az egyik útvonal benne frissült. A lényeg az, hogy a változtathatatlanság megőrzéséhez az útvonal (1-től 2-ig) mentén minden csomópontot újra kellett hoznunk, mert a meglévő csomópontok helyben nem módosíthatók. Az eredeti fa továbbra is létezik (például minden olyan hivatkozás számára, amely az eredeti 1 gyökerére mutat), az új fa pedig a módosított állapotot képviseli.

Nagy fák esetében ez a megközelítés költségessé válhat, mert minden újabb módosításnál újra kell hozni a csomópontok egy útvonalát a gyökértől a frissített csomópontig, akkor is, ha a fának valójában csak egy kis része változik.