A Bináris Keresés Fa (BST) egy fa, amelyben a csomópontok kövesse az alább említett tulajdonságok −
-
A kulcs értékét a bal al-fa kisebb, mint az érték, a szülő (root) csomópont gombot.
-
A jobb oldali alfa kulcsának értéke nagyobb vagy egyenlő a szülő (gyökér) csomópont kulcsának értékével.,
így a BST minden alfáját két részre osztja; a bal oldali alfa és a jobb oldali alfa, és meghatározható −
left_subtree (keys) < node (key) ≤ right_subtree (keys)
BST olyan csomópontok gyűjteménye, amelyek oly módon vannak elrendezve, hogy fenntartják a BST tulajdonságokat. Minden csomópontnak van egy kulcsa és egy hozzá tartozó értéke. Keresés közben a kívánt kulcs összehasonlításra kerül a BST kulcsaival, ha pedig megtalálható, a hozzá tartozó érték lekérésre kerül.,
A következő a BST −
képi ábrázolása megfigyeljük, hogy a gyökércsomópont kulcs (27) a bal oldali alfán található összes kevésbé értékes kulcs, a jobb oldali alfán pedig a magasabb értékű kulcsok.
alapműveletek
a következők egy fa alapvető műveletei –
-
keresés-egy fa elemében keres.
-
beszúr egy elemet egy fába.
-
előrendelés egy fa előrendelése szerint halad át.
-
In-order Traversal-Traverses a tree in-order módon.,
-
post-order Traversal-Traverses a tree in a post-order módon.
Node
definiáljon egy olyan csomópontot, amely rendelkezik bizonyos adatokkal, hivatkozásokkal a bal és a jobb gyermek csomópontjaira.
struct node { int data; struct node *leftChild; struct node *rightChild;};
keresési művelet
amikor egy elemet meg kell keresni, kezdje el a keresést a gyökér csomópontból. Ezután, ha az adatok kisebbek, mint a kulcsérték, keresse meg az elemet a bal oldali altípusban. Ellenkező esetben keresse meg az elemet a megfelelő altípusban. Kövesse ugyanazt az algoritmust minden csomóponthoz.,
algoritmus
Beszúrási művelet
amikor egy elemet be kell illeszteni, először keresse meg a megfelelő helyet. Indítsa el a keresést a gyökércsomópontból, majd ha az adatok kisebbek, mint a kulcsérték, keresse meg az üres helyet a bal oldali altípusban, majd helyezze be az adatokat. Ellenkező esetben keresse meg az üres helyet a megfelelő altípusban, majd helyezze be az adatokat.