Bináris keresőfa implementációját már egy korábbi blogbejegyzésben átnéztük. Ebben a posztban annyit módosítunk a korábbi implementáción, hogy a bináris keresőfa gyökerére és a node-ok leszármazottjaira nem raw pointerrel, hanem unique pointerekkel hivatkozunk.

Adatszerkezet

A raw pointeres adatszerkezethez képest módosítani kell, hogy Node* helyett std::unique_ptr<Node> típusú legyen a Node típus left és right adattagja, illetve a fa root-ja. Mindegyik említett adattagot alapértelmezett módon nullptr-re állíthatjuk. A fába beszúrás, illetve a fából törlés során ezeket majd megfelelő módon módosítjuk.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

template<typename T>
class BinarySearchTree
{
private:
    struct Node
    {
        T value;
        std::unique_ptr<Node> left{ nullptr };
        std::unique_ptr<Node> right{ nullptr };
    };

public:
    BinarySearchTree() = default;
    ~BinarySearchTree() = default;

private:
    std::unique_ptr<Node> root{ nullptr };
};

Lényeges módosulás a raw pointeres implementációhoz képest, hogy nem szükséges az alapértelmezettől eltérő destruktort készíteni a bináris keresőfához. Ennek oka, hogy unique pointerek használatával a fa képes “önmagát felszámolni”.

Ha a BinarySearchTree típusú objektum kikerül a scope-ból, akkor megszűnik az objektum és automatikusan meghívódik az adattagjának (root) destruktora. A unique pointer destruktora felszámolja a hivatkozott node-ot. Viszont minden Node típusú objektum megszűnésekor is automatikusan meghívódik mind a left, mind a right unique pointer destruktora, amivel lényegében rekurzív módon automatizáltan felszabadul az adott node bal- és jobboldali részfája is.

Új elem beszúrása

Az elem beszúrásnak most a nem rekurzív módját választottam. Így nincsen szükség két metódusra, elég csak a publikus, új értéket fogadó metódus implementálása.

Egy adott node-ra hivatkozásnál figyelembe kell venni, hogy unique pointerek használata miatt, egy node-ra csak egy unique pointer hivatkozhat. Hogyan tudjuk így megtalálni azt a helyet, ahova az új elem beszúrható?

Erre megoldás lehet, ha egy olyan pointert használunk (current), amelyik a fa bejárása során az aktuális node-ra mutató unique pointer memória címét tárolja el. Ez kezdetben a root címe lesz. Szóval current egy std::unique_ptr<Node> típusú objektum memória címe lesz, magát a unique pointer objektumot pedig dereferencián keresztül (*current) módon érhetjük el. Így egy adott node-ban tárolt érték a (*current)->value módon hivatkozható, a node bal gyermeke pedig a (*current)->left kifejezéssel.

A fában lefelé lépkedünk mindaddig, amíg meg nem találjuk az újonnan létrehozandó node helyét. Ha már bent volt a beszúrandó érték a fában, akkor false-szal kilépünk a metódusból, egyéb esetben viszont vagy a bal-, vagy a jobb oldali részfába lépünk tovább.

Ha kilépünk a ciklusból, akkor biztosak lehetünk abban, hogy *current == nullptr. Mit is jelent ez pontosan? Két eset fordulhat elő.

  1. Ha a fa még üres volt, akkor root-ban, mint unique pointer objektumban eltárolt mutató értéke lesz nullptr. Nem a root a nullptr, hiszen az egy létező std::unique_ptr<Node> típusú objektum. Ebben az esetben annyit kell tennünk, hogy a root az újonnan létrehozandó node-ra hivatkozzon.

  2. Ha a fa bejárása nem a gyökérnél akadt meg, akkor éppen egy létező node left-jére vagy right-jára hivatkozik a current, és a hivatozott unique pointer típusú objektum aktuálisan még nullptr-t tárol. Ilyenkor létrehozunk egy új node-ot és arra fog hivatkozni a már korábban létező unique pointer objektum.

Az std::make_unique<Node>(value) utasítás csak akkor fog működni, ha a Node típusnak van olyan egyparaméteres konstruktora, amin keresztül a value-val létrehozható új Node típusú példány. Emiatt létre kell hozni az explicit Node(const T& value) szignatúrájú konstruktort.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

template<typename T>
bool BinarySearchTree<T>::Insert(const T& value)
{
    std::unique_ptr<Node>* current = &root;

    while (*current != nullptr) {
        if (value == (*current)->value) return false;

        current = value < (*current)->value 
                  ? &(*current)->left 
                  : &(*current)->right;
    }

    *current = std::make_unique<Node>(value);
    return true;
}

A unique pointer használatnak köszönhetően a beszúrás művelet jelentősen leegyszerűsödött. Természetesen raw pointeres implementáció esetén is lehetne iteratív implementációt adni a beszúrásra, viszont akkor külön le kéne kezelni a gyökérbe szúrás esetét, illetve meg kéne vizsgálni, hogy az új node-ot a szülőjének bal- vagy jobb gyermekeként kell-e bekötnünk. Itt ezek “automatikusan” működnek, mert már a beszúrás előtt léteznek a unique pointer objektumok, csak azok belső tartalmát módosítjuk nullptr-ről egy konkrét címre.

Törlés a fából

A törlést is iteratív módon valósítottam most meg. A beszúrásnál már megismert technikát használtam: az aktuális node-ra std::unique_ptr<Node>* típusú pointerrel hivatkozom.

 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

template<typename T>
bool BinarySearchTree<T>::Erase(const T& value)
{
    std::unique_ptr<Node>* current = &root;

    while (*current != nullptr && (*current)->value != value) {
        current = value < (*current)->value 
                  ? &(*current)->left 
                  : &(*current)->right;
    }
    if (*current == nullptr) return false;

    if ((*current)->left == nullptr) {
        *current = std::move((*current)->right);
        return true;
    }
    if ((*current)->right == nullptr) {
        *current = std::move((*current)->left);
        return true;
    }

    std::unique_ptr<Node>* next = &(*current)->right;
    while ((*next)->left != nullptr) {
        next = &(*next)->left;
    }
    (*current)->value = (*next)->value;
    *next = std::move((*next)->right);
    return true;
}

Először meg kell keresni a törlendő elemet. Ha benne van a fában, akkor az első while ciklus után current annak a unique pointer objektumnak lesz a címe, amely a törlendő Node objektumot tulajdonolja. Ha ennek node-nak nincs bal gyereke, akkor a jobb gyermeket “felemeljük” a helyére. Hasonlót teszünk akkor is, ha nincs jobb gyermek, akkor a bal gyereket “emeljük fel”.

Érdemes végiggondolni, hogy mi történik, amikor felülírünk egy unique pointer objektumot, egy másik unique_pointer-rel. Nézzük például a *current = std::move((*current)->right) utasítást. A háttérben az std::unique_ptr<Node> move assignment operátora fut le. Ennek hatása az lesz, hogy a (*current)->right által tulajdonolt Node típusú objektum tulajdonjoga átkerül *current-hez, és a korábban *current által tulajdonolt objektum fel lesz szabadítva. Viszont ezen felszabadításnál nem szűnik meg (*current)->right-ja? A helyzet az, hogy nem, mivel a move-olás miatt onnan már korábban ki lett mozgatva a hivatkozott objektum. Ez azt jelenti, hogy a *current = std::move((*current)->right) utasítás mögött a (*current).reset((*current)->right.release()) művelet áll. Először lefut a release(), emiatt a korábban (*current)->right által tulajdonolt objektum tulajdonjogát elengedjük és átadjuk *current-nek úgy, hogy *current korábbi tulajdonoltját felszabadítjuk.

A törlés megvalósítása ezeken kívül ugyanazt a logikát követő, amit a raw pointeres implementációnál alkalmaztunk, ezért itt nem részletezzük tovább a megvalósítást.

Tartalmazás vizsgálat

Elem keresésénél is a beszúrásnál és törlésnél látott technikát használtam, ahogy az alábbi kódban látható.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

template<typename T>
bool BinarySearchTree<T>::Contains(const T& value) const
{
    const std::unique_ptr<Node>* current = &root;

    while (*current != nullptr) {
        if (value == (*current)->value) {
            return true;
        }

        current = value < (*current)->value
                  ? current = &(*current)->left
                  : current = &(*current)->right;
    }

    return false;
}

Az implementációnál current-et const pointerként kell definiálnunk, mert egyébként a root értéke módosítható lenne rajta keresztül, ami ellentmondana a metódus const-ságának.

Fontos megemlíteni, hogy nem csak unique pointerre mutató pointer alkalmazásával tudunk eljutni a keresett elemig a fában.

Másik lehetséges technika, ha ténylegesen a unique pointer által tulajdonolt Node típusú objektumra hivatkozunk a bejárásnál. Ne felejtsük el viszont, hogy erre a Node-ra nem tudunk unique pointerrel hivatkozni, mert ez ellentmondana a unique pointer egyértelmű tulajdonlási képességének.

Viszont, ha az std::unique_ptr<Node>::get() metódusát használjuk, akkor a unique pointerből ki tudjuk olvasni a hivatkozott Node típusú objektumot. Így a megvalósítás a következő módon alakul:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

template<typename T>
bool BinarySearchTree<T>::Contains(const T& value) const
{
    const Node* current = root->get();

    while (current != nullptr) {
        if (value == current->value) {
            return true;
        }

        current = value < current->value
                  ? current = current->left.get()
                  : current = current->right.get();
    }

    return false;
}

Egyéb műveletek

A többi művelet nem tartalmaz túl sok újdonságot már, ezért azokról külön nem írok. A teljes kód viszont github-on elérhető.

Kapcsolódó bejegyzések

Kapcsolódó kódok

A kódok github-on is elérhetők.