Bináris keresőfa

Utasítások

Szúrj be és keress számokat egy bináris fában.

Amikor rendezett adatokat kell reprezentálnunk, 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 az [1, 3, 4, 5, 2] lesz. Most újra rendeznünk kell a teljes tömböt! Ezen úgy javíthatunk, ha felismerjük, hogy csak helyet kell csinálnunk az új elemnek: [1, nil, 3, 4, 5], majd beillesztjük az elemet az imént létrehozott helyre. De ez még mindig azt jelenti, hogy sok elemet eggyel el kell tolnunk.

A bináris keresőfák azonban sokkal hatékonyabban tudnak működni a rendezett adatokkal.

A 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), egy left nevű változót és egy right nevű változót. A left és right változók a nil-re vagy más csomópontokra mutatnak. Mivel ezek alatt is további csomópontok vannak, azt mondjuk, hogy a left és right változók részfákra mutatnak. A bal részfában lévő összes adat kisebb vagy egyenlő, mint az aktuális csomópont adata, a jobb részfában lévő összes adat 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