C/C++ & Visual C++

DatovΘ struktury a algoritmy (11.)

┌vodem  |  DatovΘ struktury |  Kurz DirectX  |  Downloads  |  Otßzky a odpov∞di

11.1 Pojmy a zßklady

Stromy jsou, podobn∞ jako lineßrnφ spojovΘ seznamy, slo₧eny z uzl∙ (angl. nodes). Tyto uzly jednak obsahujφ data a pak obsahujφ takΘ ukazatele na dalÜφ uzly. Tφm nßm vznikß rekurzivnφ datovß struktura. Ukß₧eme si grafickou interpretaci obecnΘho stromu:

Pokud si obrßzek obrßtφte, pak uvidφte proΦ tuto datovou strukturu naz²vßme stromem. Uvedeme si n∞kterΘ pojmy, kterΘ se vyskytujφ ve spojitosti se stromy:

• ko°en (angl. root) - je poΦßteΦnφm uzlem stromu a je v₧dy jen jeden. Lze takΘ definovat jako uzel, kter² nemß rodiΦe. V naÜem obrßzku to je tedy uzel oznaΦen² 1

• potomek (angl. child) - pokud k n∞kterΘmu uzlu vede Φßra z uzlu nad nφm (ten je na ni₧Üφ hladin∞, jak se povφme nφ₧e), pak je tento prvek potomkem prvku z kterΘho vede Φßra. Nap°φklad uzly 2, 3, 4 jsou potomky uzlu (ko°enu) 1

• rodiΦ (angl. parent) - uvedeme p°φklad - rodiΦem prvku 3 je uzel 1

• list (ang. leaf) - uzel, kter² nemß potomka naz²vßme listem. V naÜem diagramu jsou to uzly 5, 3, 6 a 7

• v∞tev (branch) - spojnice dvou uzl∙

Prvky, kterΘ nejsou listy se takΘ n∞kdy oznaΦujφ jako vnit°nφ uzly stromu a listy se n∞kdy oznaΦujφ jako koncovΘ uzly.

Typ stromu je pak urΦen tφm, kolik potomk∙ majφ jednotlivΘ uzly. OznaΦme n poΦet potomk∙ uzlu, pak pro:

• n = 2 - binßrnφ strom

• n = 3 - ternßrnφ strom

• n = 4 - quadtree

Pokud polo₧φme n = 1, vidφme, ₧e datovou strukturou, kterou dostaneme je jednosm∞rn² lineßrnφ spojov² seznam.

DalÜφ d∙le₧itou v∞cφ, kterou vidφme v diagramu je, ₧e ka₧d² uzel stromu vlastn∞ tvo°φ nov² strom - °φkßme mu podstrom. StaΦφ vzφt uzel 4 a dostßvßme strom s ko°enem 4 a jeho dv∞ma potomky - uzly 6 a 7.

Pokud bychom cht∞li, a v naÜφ implementaci se nßm to hodilo, pak je mo₧nΘ do ka₧dΘho uzlu navφc ulo₧it i ukazatel na rodiΦe tohoto uzlu, co₧ by v n∞kter²ch p°φpadech ulehΦilo pr∙chod stromem.

Spojov² seznam byla vlastn∞ Φßra, na kterΘ byly ulo₧eny jednotlivΘ uzly - ostatn∞ proto jsme mu takΘ °φkali lineßrnφ. Narozdφl od toho, u strom∙ zavßdφme hladiny. Vφce nßm o tom povφ obrßzek:

Na 0-tΘ hladin∞ le₧φ pouze ko°en a vÜichni jeho potomci majφ hladinu o jedna vyÜÜφ. Jako poΦßteΦnφ hladinu jsme si zvolili 0, nebo¥ pole nßm v naÜem oblφbenΘm C/C++ zaΦφnajφ takΘ od nuly.

11.2 ObecnΘ stromy

To jsou stromy, jejich₧ uzly ukazujφ na nekoneΦn² poΦet dalÜφch uzl∙. A₧ si prohlΘdnete obrßzek, uvidφte, ₧e se v ₧ivot∞ pou₧φvajφ celkem Φasto:

Jak takov²to strom, hlavn∞ s ohledem na nekoneΦn² poΦet potomk∙ jednotliv²ch uzl∙ realizovat? JednoduÜe, staΦφ si na pomoc vzφt spojov² seznam a do ka₧dΘho uzlu stromu umφstit jen odkaz na prvnφho potomka uzlu. Samoz°ejm∞ to nenφ jedinß mo₧nost, lze pou₧φt i dynamicky se zv∞tÜujφcφ pole nebo jinou strukturu. Uzly tedy budou v tomto p°φpad∞ obsahovat dva ukazatele - ukazatel na prvnφho potomka a na uzly na stejnΘ hladin∞ (dalo by se °φci na sourozence). To ovÜem krom∞ ko°ene, kter² bude mφt ukazatel na sourozence s hodnotou NULL.

V reßlnΘm problΘmu se nßm m∙₧e takov²to obecn² strom hodit t°eba k rozhodovßnφ um∞lΘ inteligence poΦφtaΦovΘ hry. V uzlu by byla nap°φklad otßzka, zda postava vidφ ·toΦnφka, mo₧nosti by byly ano/ne. V²hodou pak je, ₧e vybrßnφm nap°. mo₧nosti ano vylouΦφme vÜechny otßzky nßsledujφcφ v podstrom∞ ne, Φφm₧ se vyhneme zkoumßnφ mnoha neperspektivnφch otßzek a tedy i ·spo°e Φasu.

Zpracovßvat stromy rekurzivn∞ m∙₧eme celkem t°emi zp∙soby. Zpracovßnφm rozumφme provedenφ urΦitΘ operace nade vÜemi uzly stromu. U obecn²ch strom∙ se pou₧φvajφ dv∞ metody, kterΘ nßm zajistφ pr∙chod vÜemi uzly stromu - jsou to pre-order a post-order (t°etφ metoda se naz²vß in-order). O funkci vÜech t∞chto t°φ metod se zmφnφme pozd∞ji.

11.3 Binßrnφ stromy a binßrnφ vyhledßvacφ strom

My se nynφ budeme zab²vat a takΘ implementujeme strom, kter² se pou₧φvß velice Φasto. Je to p°φpad stromu pro n = 2, tedy ka₧d² uzel stromu bude ukazovat na dva dalÜφ uzly - oznaΦme si je t°eba lev² a prav². Datov²m prvkem kter² budeme vklßdat do stromu pak bude Φasto hodnota typu int. Pro vklßdßnφ prvku si zavedeme pravidlo, ₧e pokud je prvek menÜφ ne₧li hodnota v uzlu, pak prvek ulo₧φme do levΘ v∞tve uzlu. V opaΦnΘm p°φpad∞ do pravΘ. Pokud prvek bude ve strom∞ ji₧ obsa₧en, nestane se nic. Strom, kter² spl≥uje tyto specißlnφ podmφnky naz²vßme prßv∞ binßrnφ vyhledßvacφ strom a slou₧φ k rychlΘmu zjiÜt∞nφ, zda je hodnota ve strom∞ ulo₧ena Φi ne. JinΘ u₧itΘ pro binßrnφ stromy je pak reprezentace aritmetickΘho v²razu v pam∞ti poΦφtaΦe, pop°. k implementaci datovΘ struktury nazvanΘ halda, se kterou se setkßme v n∞kterΘm z dalÜφch dφl∙. N∞kdy lidΘ oznaΦujφ binßrnφ stromy jako B-stromy, co₧ ale nenφ sprßvnΘ. B-strom je ·pln∞ jinß datovß struktura, kterß nachßzφ uplatn∞nφ t°eba v souborovΘm systΘmu.

Implementujeme si tedy takov² binßrnφ strom:

#ifndef BINSTROM_H
    #define BINSTROM_H

    template<class T> class CUzel {
    private:
        T m_Data;
        CUzel<T> *m_lpLevy;
        CUzel<T> *m_lpPravy;
    public:
        CUzel() : m_lpLevy(NULL), m_lpPravy(NULL) { }
        CUzel(const T& _Data) : m_Data(_Data), m_lpLevy(NULL), m_lpPravy(NULL) { }

        T VratData() const { return m_Data; }
        CUzel<T>* &VratLevy() { return m_lpLevy; }
        CUzel<T>* &VratPravy() { return m_lpPravy; }
        void NastavLevy(CUzel<T> *_lpLevy) { m_lpLevy = _lpLevy; }
        void NastavPravy(CUzel<T> *_lpPravy) { m_lpPravy = _lpPravy; }
        void NastavData(const T& _Data) { m_Data = _Data; }
    };

    template<class T> class CBinStrom {
    private:
        CUzel<T> *m_lpKoren;
    public:
        CBinStrom() : m_lpKoren(NULL) { }
        ~CBinStrom() { if(!JePrazdny()) { SmazStrom(m_lpKoren); } }

        bool VytvorPrazdny();

        bool SmazStrom(CUzel<T>* &_lpUzel);

        bool JePrazdny();

        bool Vloz(const T& _Data); // vklada do stromu
        bool VlozDoStromu(CUzel<T>* &_lpUzel, const T& _Data);

        CUzel<T>* Najdi(const T& _Data); // vrati ukazatel na nalezeny prvek nebo NULL
        CUzel<T>* NajdiVeStromu(CUzel<T> *_lpUzel, const T& _Data);

        bool Smaz(const T& _Data); // smaze data
    };