==== Odpojení jednoho prvku ze stromu ====

[[zalg::strom_src|zdrojový text]]

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

<code C++>
Item * remove (Item * & p, int k) 
</code>

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. 

<code C++>
    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 */ }
</code>

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.

<code C++>
        Item* temp = p;
        /* ... */
        temp->left = nullptr;
        temp->right = nullptr;
        return temp;
</code>

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; //
<code C++>
       if (p->left == nullptr) { p = p->right;  }
       else if (p->right == nullptr) { p = p->left;}
       else { /* MAME DVA PODSTROMY, s tim bude trochu prace */ }
</code>

==== Hledání náhradníka ====

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.

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

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.
<code C++>
            Item * t = findUnlink (p->left);
            t->left = p->left;
            t->right = p->right;
            p = t;
</code>

Zde je vysledna funkce,

<code C++>
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;
    }
}
</code>

==== Zobrazení stromu a mazání celého stromu. ====

Podívejte na různé způsoby zobrazení stromu
(funkce print, print2, print3)
<code C++>
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 << " ";
    }
}
</code>

Nakonec celý strom vymažeme,
<code C++>
void clean(Item* p)
{
    if (p != NULL)
    {
        clean(p->left);
        clean(p->right);
        delete p;
    }
}
</code>