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.