C/C++ & Visual C++

DatovΘ struktury a algoritmy (12.)

Minule jsme si ukßzali zßkladnφ implementaci binßrnφho vyhledßvacφho stromu. Dnes se k nφ vrßtφme a ukß₧eme si rekurzivnφ implementace metod, kterΘ jsme implementovali minule. TakΘ budeme pokraΦovat metodou Smaz(), kterß bude mφt za ·kol mazßnφ prvk∙ binßrnφho stromu. P°eji p°φjemnΘ Φtenφ!

12.1. Binßrnφ strom - jinß implementace metod

Ji₧ minule jsme se zmφnili o tom, ₧e strom je rekurzivnφ datovou strukturou. Nynφ si ukß₧eme jak tyto metody naprogramovat, definice t°φdy stromu je stejnß jako v minulΘm dφlu, jen p°idßme metody VlozR() a VlozDoStromuR(). Nejprve v²konnß metoda:

    template<class T> void CBinStrom<T>::VlozDoStromuR(CUzel<T>* &_lpUzel, const T& _Data)
    {
        if(!_lpUzel)
        {
            _lpUzel = new CUzel<T>(_Data); // osetrime prazdny strom
        }
        else
        {
            if(_Data == _lpUzel->VratData())
            {
                return;
            }

            if(_lpUzel->VratData() > _Data)
            {
                VlozDoStromuR(_lpUzel->VratLevy(), _Data);
            }
            else
            {
                VlozDoStromuR(_lpUzel->VratPravy(), _Data);
            }
        }
    }

Nynφ metoda zajiÜ¥ujφcφ vlo₧enφ do kompletnφho stromu:

    template<class T> void CBinStrom<T>::VlozR(const T& _Data)
    {
        VlozDoStromuR(m_lpKoren, _Data);
    }

Metoda vyhledßvßnφ byla v minulΘm dφlu uvedena v rekurzivnφ verzi. Ukß₧eme si tedy pro ·plnost jejφ nerekurzivnφ verzi NajdiVeStromu() (a metodu z minulΘho dφlu p°ejmenujeme na NajdiVeStromuR() a stejn∞ tak i s metodou Najdi()):

    template<class T> CUzel<T>* CBinStrom<T>::NajdiVeStromu(CUzel<T> *_lpUzel, const T& _Data)
    {
        CUzel<T> *lpRet = NULL;

        while(_lpUzel != NULL)
        {
            if(_lpUzel->VratData() == _Data)
            {
                lpRet = _lpUzel;
                break;
            }
            else
            {
                if(_lpUzel->VratData() < _Data)
                {
                    _lpUzel = _lpUzel->VratPravy();
                }
                else
                {
                    _lpUzel = _lpUzel->VratLevy();
                }
            }
        }

        return lpRet;
    }

JeÜt∞ ve°ejnß metoda Najdi():

    template<class T> CUzel<T>* CBinStrom<T>::Najdi(const T& _Data)
    {
        return NajdiVeStromu(m_lpKoren, _Data);
    }

Metoda pro mazßnφ stromu byla takΘ rekurzivnφ v minulΘm dφlu. Ta by se na nerekurzivnφ verzi p°episovala mnohem h∙°e, s nejv∞tÜφ pravd∞podobnostφ bychom byli nuceni pou₧φt n∞jakΘ jinΘ datovΘ struktury pro ulo₧enφ vrchol∙.

Vidφme, ₧e ani jedna z verzφ metod nenφ o moc slo₧it∞jÜφ na naprogramovßnφ. OvÜem pokud se naskytne rekurzivnφ i nerekurzivnφ verze metody, pak je v∞tÜinou v²hodn∞jÜφ pou₧φt nerekurzivnφ verze - nebude dochßzet ke ztrßt∞ Φasu, kterß je d∙sledkem re₧ie p°i volßnφ funkce (uklßdßnφ nßvratovΘ hodnoty apod.). V²jimku ud∞lßme u metody mazßnφ stromu, kde nßm rekurze uÜet°φ programßtorskou prßci, aΦkoliv mo₧nß bude o trochu pomalejÜφ.

12.2. Binßrnφ strom - mazßnφ prvk∙

Poslednφ zßkladnφ metoda bude provßd∞t operaci mazßnφ prvk∙ binßrnφho vyhledßvacφho stromu. Z t∞ch metod, se kter²mi jsme se seznßmili je nejslo₧it∞jÜφ. Musφme si uv∞domit, ₧e p°i mazßnφ prvku mohou nastat nßsledujφcφ t°i p°φpady:

• prvek je listem - nemßme ₧ßdn² problΘm, staΦφ prvek smazat a upravit ukazatel v rodiΦovskΘm prvku

• prvek mß jednoho potomka - staΦφ zm∞nit ukazatel rodiΦe mazanΘho prvku na nßsledovnφka tohoto prvku. P°edtφm si vÜak ulo₧φme ukazatel na mazan² prvek, abychom ho mohli smazat

• prvek mß dva nßsledovnφky - budeme muset n∞jak rozumn∞ mazanou hodnotu nahradit jinou ze stromu. Musφme vÜak brßt ohled i na sprßvnΘ uspo°ßdßnφ stromu. Tomu se bude v∞novat p°φsluÜn² odstaveΦek.

12.2.1. Nalezenφ rodiΦe prvku

Abychom nemuseli neustßle hledat rodiΦe mazanΘho prvku, si nejprve upravφme metodu pro hledßnφ prvku. A to takov²m zp∙sobem, ₧e p°idßme jeÜt∞ jeden parametr, ve kterΘm bude ulo₧en prßv∞ tento ukazatel. To pro nßs nebude ₧ßdn² problΘm, nebo¥ p°i vyhledßvßnφ prvku s danou hodnotou musφme p°es rodiΦovsk² prvek p°ejφt - staΦφ p°idat jedin² °ßdek, jak vidφme na v²pisu. Vzhledem k tomu, ₧e budeme tento ukazatel m∞nit, budeme ho p°edßvat jako referenci na ukazatel na vrchol (uzel) stromu. Pou₧ijeme nerekurzivnφ verzi hledßnφ prvku:

    template<class T> CUzel<T>* CBinStrom<T>::NajdiVeStromu(CUzel<T> *_lpUzel, const T& _Data,
    CUzel<T>* &_lpRodic)
    {
        CUzel<T> *lpRet = NULL;

        while(_lpUzel != NULL)
        {
            if(_lpUzel->VratData() == _Data)
            {
                lpRet = _lpUzel;
                break;
            }
            else
            {
                _lpRodic = _lpUzel; // ulozime si rodice

                if(_lpUzel->VratData() < _Data)
                {
                    _lpUzel = _lpUzel->VratPravy();
                }
                else
                {
                    _lpUzel = _lpUzel->VratLevy();
                }
            }
        }

        return lpRet;
    }

Podobn∞ upravφme i funkci pro hledßnφ v celΘm stromu - implementace je v p°ilo₧enΘm projektu.

12.2.2. Mazßnφ listovΘho prvku

Grafickß interpretace situace:

    template<class T> void CBinStrom<T>::SmazList(CUzel<T>* _lpMazany, CUzel<T>* _lpRodic)
    {
        if(_lpRodic)
        {
            // mame-li rodice
            if(_lpMazany == _lpRodic->VratLevy())
            {
                _lpRodic->NastavLevy(NULL);
            }
            else
            {
                _lpRodic->NastavPravy(NULL);
            }
        }
        else
        {
            // mazeme koren stromu
            m_lpKoren = NULL;
        }

        delete _lpMazany; // kazdopadne mazeme mazany prvek
    }

Jde tedy jen o to, zjistit, zda je mazan² prvek lev²m nebo prav²m nßsledovnφkem a p°φsluÜn²m zp∙sobem upravit ukazatele.

12.2.2. Mazßnφ prvku s jednφm nßsledovnφkem

Grafickß interpretace situace:

    template<class T> bool CBinStrom<T>::SmazSJednim(CUzel<T>* _lpMazany, CUzel<T>* _lpRodic)
    {
        // nejprve si uchovame potomka mazaneho prvku - je jen jeden
      CUzel<T>* lpPotomek = (_lpMazany->VratLevy() == NULL) ? _lpMazany->VratPravy() :
      _lpMazany->VratLevy();

        // pokud neexistuje predchudce - budeme mazat koren
        if(!_lpRodic) { m_lpKoren = lpPotomek; }
        else
        {
            // jinak preskocime mazany ve strukture stromu
            if(_lpMazany == _lpRodic->VratLevy())
            {
                _lpRodic->NastavLevy(lpPotomek);
            }
            else
            {
                _lpRodic->NastavPravy(lpPotomek);
            }
        }

        delete _lpMazany; // kazdopadne mazeme mazany prvek
    }

Ma₧eme velice podobn∞, jako v p°φpad∞ listu. Jen je nutnΘ najφt nßsledovnφka mazanΘho prvku a toho za°adit sprßvn∞ pod rodiΦe.

12.2.3. Mazßnφ prvku se dv∞ma nßsledovnφky

Poslednφ a nejslo₧it∞jÜφ metoda je p°ed nßmi. Grafickß interpretace situace:

Rozhodneme-li se smazat nap°. prvek s hodnotou 12, musφme vybrat prvek, kter²m 12 nahradφme, aby z∙stala zachovßna struktura binßrnφho vyhledßvacφho stromu. V tomto p°φpad∞ by to mohl b²t jeden z prvk∙ 9 nebo 13. Pokusφme se tedy vyjmout prvek 8, pak u₧ nem∙₧eme vybφrat libovoln∞. UrΦit∞ by nevyhovoval prvek s Φφslem 13 a prvek s Φφslem 4. Naopak prvky 6 i 9 vyhovujφ uspo°ßdßnφ stromu. Pokud si na papφr nakreslφte rozsßhlejÜφ strom, dojdete k zßv∞ru, ₧e lze v₧dy pou₧φt prvek, kter² le₧φ bu∩ v levΘ v∞tvi nejvφce vpravo nebo prvek v pravΘ v∞tvi co nejvφce vlevo. Tak₧e jedna z mo₧n²ch implementacφ vypadß nßsledovn∞:

    template<class T> void CBinStrom<T>::SmazSeDvema(CUzel<T>* _lpMazany)
    {
        // uchovame si prvek, kterym nahradime nahrazovany prvek - vezmeme nejlevejsi zprava
        CUzel<T>* lpNahrazujici = _lpMazany->VratPravy();

        // soucasne si najdeme i rodice tohoto prvku
        CUzel<T>* lpRodic = _lpMazany;
        while(lpNahrazujici->VratLevy())
        {
            lpRodic = lpNahrazujici;
            lpNahrazujici = lpNahrazujici->VratLevy();
        }

        // nyni mame vse potrebne -> prohodime data
        _lpMazany->NastavData(lpNahrazujici->VratData());

        // a smazeme nepotrebny prvek
        if(lpNahrazujici->VratLevy() || lpNahrazujici->VratPravy())
        {
            SmazSJednim(lpNahrazujici, lpRodic);
        }
        else
        {
            SmazList(lpNahrazujici, lpRodic);
        }
    }

Funkce mß jen jeden parametr, nebo¥ rodiΦe mazanΘho prvku v tomto p°φpad∞ v∙bec nepot°ebujeme. V t∞le jen najdeme pomocφ cyklu while nejlev∞jÜφ prvek v pravΘm podstromu naÜeho originßlnφho stromu a zßrove≥ i jeho rodiΦe. Prvek, kter² ma₧eme bude bu∩ listov²m prvkem nebo prvkem s jednφm nßsledovnφkem a pro tyto p°φpady ji₧ mßme p°ipraveny p°φsluÜnΘ metody.

12.2.4. Metoda pro mazßnφ prvku binßrnφho vyhledßvacφho stromu

Zb²vß nßm u₧ jen doplnit metodu, kterΘ zadßme jako parametr po₧adovanou hodnotu, kterou chceme mazat:

    template<class T> bool CBinStrom<T>::Smaz(const T& _Data)
    {
        bool bNavrat = false;

        CUzel<T>* lpMazany = NULL, *lpRodic = NULL;

        lpMazany = Najdi(_Data, lpRodic);

        if(lpMazany)
        {
            if((lpMazany->VratLevy() == NULL) && (lpMazany->VratPravy() == NULL))
            {
                SmazList(lpMazany, lpRodic);
            }
            else
            {
                if((lpMazany->VratLevy() == NULL) || (lpMazany->VratPravy() == NULL))
                {
                    SmazSJednim(lpMazany, lpRodic);
                }
                else
                {
                    SmazSeDvema(lpMazany);
                }
            }

            bNavrat = true;
        }

        return bNavrat;
    }

Metoda pouze vyhledß p°φsluÜnΘ ukazatele - na prvek a jeho rodiΦe. Pak se jen rozhodne, kterou ze t°φ metod pro mazßnφ prvku zavolß.

12.3. Co bude p°φÜt∞

P°φÜt∞ budeme pokraΦovat povφdßnφm o stromech a s nejv∞tÜφ pravd∞podobnostφ ji₧ opustφme binßrnφ vyhledßvacφ strom. Budeme se v∞novat prochßzenφ stromem do hloubky, o kterΘm jsme se zmφnili ji₧ v minulΘm dφlu. Dßle zavedeme n∞kterΘ vlastnosti strom∙. A nakonec si povφme o problΘmech, kterΘ mohou vzniknout p°i vklßdßnφ prvk∙ do stromu.

Nashledanou p°φÜt∞.