zdrojový text

Skripta, příklad 2.4, odstavec: Zrušení vrcholu

Item * remove (Item * & p, int k)

Funkce remove ma ve stromu s korenem p najit a odpjit prvek s klicem k.

Funkce remove vraci ukazatel na odpojeny prvek.
Nebo nullptr pokud zadany klic nenasla.

Prvni parametr je odkaz na ukazatel na koren stromu: Item * & p
protoze koren stromu (podstromu) se bude menit (pokud obsahuje klic urceny k odpojeni).

Funkce nejprve hleda zadany klic.
Podstrom je prazdny: nenajde.
Hledany klic je mensi nez klic uvnitr vrcholu stromu: rekurzivne pokracuj v levem podstromu.
Vetsi : pravy podstrom.
A zbyva varianta, ze jsme klic urceny k odpojeni nasli.

    if (p == nullptr) { return nullptr; }
    else if (k < p->key) return remove(p->left, k);
    else if (k > p->key) return remove(p->right, k);
    else { /* NASLI JSME */ }

Pokud jsme nasli hledany klic, schovame si odkaz na podstrom do promenne - obycejneho kazatele temp, nebot p se bude menit.
Uplne nakonec nastavime levy a pravy podstrom uvolneneho prvku na null a vratime ukazatel na odpojeny prvek jako vysledek funkce.

        Item* temp = p;
        /* ... */
        temp->left = nullptr;
        temp->right = nullptr;
        return temp;

Pokud uvolnovany prvek ma jeden nebo zadny podstrom, bude odpojeni snadne.
Kdyz chybi levy podstrom p→left == nullptr , pripojime pravy podstrom na misto kde byl puvodne ukazatel na uvolnovany prvek. p = p→right;

       if (p->left == nullptr) { p = p->right;  }
       else if (p->right == nullptr) { p = p->left;}
       else { /* MAME DVA PODSTROMY, s tim bude trochu prace */ }

Pokud uvolnovany prvek ma dva podstromy, musime najit vhodneho nahradnika.
A to nejvetsi prvek z mensich prvku.
( Nebo nejmensi z vetsich prvku. )

Kde je nejvetsi prvek z mensich prvku ?
Jdete do leveho podstromu a potom postupujte stale do prava.
Az narazite na prvek ktery nema pravy podstrom, nasli jste nahranika. Pokud nahradnik ma nejaky levy podstrom, pripojte ho na misto kde byl nahradnik.

Zavolame findUnlink (p→left), vime ze p→left je nenulovy, nebot p ma dva podstromy.
Pomocna funkce findUnlink se vola rekurzive dokud jeji parameter ma pravy podstrom.
Az nebude mit pravy podstrom umisti svuj levy podstrom na misto kde byl prave zpracovavany podstrom.
A vysledkem funkce je prvek, ktery nemel pravy podstrom.

Item* findUnlink (Item * & u) 
{
    if (u->right != nullptr) 
        { return findUnlink (u->right); }
    else 
        { Item * result = u; u = u->left; return result; }
}

A ve funkci remove si ulozime do promenne t nalezeneho nahradnika.
Nahradikovi pripojime podstromy, ktere mel uvolnovany prvek p.
A nahradnika “ukotvime” do stejneho mista, jako uvolnovany prvek.

            Item * t = findUnlink (p->left);
            t->left = p->left;
            t->right = p->right;
            p = t;

Zde je vysledna funkce,

Item* findUnlink (Item * & u) 
{
    if (u->right != nullptr) 
        { return findUnlink(u->right); }
    else 
        { Item * result = u; u = u->left; return result; }
}
 
Item * remove (Item * & p, int k) 
{
    if (p == nullptr) { return nullptr; }
    else if (k < p->key) return remove(p->left, k);
    else if (k > p->key) return remove(p->right, k);
    else {
        Item* temp = p;
        if (p->left == nullptr) { p = p->right;  }
        else if (p->right == nullptr) { p = p->left;}
        else {
            Item * t = findUnlink (p->left);
            t->left = p->left;
            t->right = p->right;
            p = t;
        }
        temp->left = nullptr;
        temp->right = nullptr;
        return temp;
    }
}

Podívejte na různé způsoby zobrazení stromu (funkce print, print2, print3)

void print(Item* p)
{
    if (p != NULL)
    {
        print(p->left);
        cout << p->key << " ";
        print(p->right);
    }
}
 
void print2 (Item* p)
{
    if (p != NULL)
    {
        cout << p->key << " ";
        // cout << "(";
        print2(p->left);
        // cout << ",";
        print2(p->right);
        // cout << ")";
    }
}
 
void print3(Item* p)
{
    if (p != NULL)
    {
        print3(p->left);
        print3(p->right);
        cout << p->key << " ";
    }
}

Nakonec celý strom vymažeme,

void clean(Item* p)
{
    if (p != NULL)
    {
        clean(p->left);
        clean(p->right);
        delete p;
    }
}