LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> C++ Binární vyhledávací stromy

V tomto článku se podíváme na binární stromy. Řekneme si tedy, co vlastně binární strom je, proč se používá, probereme si některé operace, které se nad binárními stromy provádějí a nebude chybět ani ukázka některých metod v jazyce C++.

9.11.2010 00:00 | Petr Sklenička | Články autora | přečteno 21272×

Úvod do binárních stromů

Binární strom je datová struktura, která se skládá z několika uzlů, přičemž každý z nich má maximálně dva potomky (proto binární strom). Takto by se dal jednoduše definovat binární strom, pro lepší představu se však podívejte na následující obrázek.

Všechny "kroužky", které na obrázku vidíte, se nazývají uzly stromu. Speciální případem uzlu je červený kroužek, kterému se říká kořen stromu. Kořen stromu jako jediný nemá žádného rodiče, zjednodušeně řečeno, není nad ním žádný uzel. Dále si na obrázku všimněte, že ne každý uzel má právě dva potomky. To však není v rozporu s naší definicí, proto se opravdu jedná o binární strom. Dále si zavedeme pojem hloubka uzlu - jde o délku cesty od kořene k danému uzlu. Největší hloubka libolného uzlu se pak označuje jako výška stromu.

Binární vyhledávací stromy

Nyní, když víme, co je to binární strom a máme zavedeny nejdůležitější pojmy, můžeme se podívat na binární vyhledávací stromy. Jedná se o speciální případ binárních stromů, kdy každý uzel obsahuje nějaký klíč, na jehož základě je definováno nějaké uspořádání. Celý problém lze říci i jednodušším způsobem - v každém uzlu stromu je nějaká hodnota a platí, že v levém podstromu jsou hodnoty menší, naopak v pravém podstromu jsou hodnoty větší. Aby to bylo úplně jasné, nakreslíme si strom, který vznikne postupným přidáváním těchto prvků: 9, 12, 10, 24, 3, 0, 30.

Kořen stromu je 9. Dále jsme přidali číslo 12, které je větší než 9, proto je číslo 12 na pravé straně pod číslem 9. Následovalo číslo 24, které je větší než 9, je také větší než 12 a proto je číslo 24 pravým potomkem čísla 12. Číslo 3 je menší než 9, je tedy levým potomkem čísla 9. Tímto způsobem jsme do stromu uložili i další zbylá čísla. Je snad tedy jasné, že při přidávání prvků do binárního vyhledávacího stromu začínáme od kořene a postupujeme podle toho, zda je číslo menší nebo větší.
Použití binárních vyhledávacích stromů je velké, jako úplně nejjednodušší příklad lze uvést toto: Máte v textovém souboru uloženo 10 000 000 čísel. Mezi těmito čísly potřebuje nějaké vyhledat. Někoho by napadlo, že si čísla uloží do pole a poté bude pole prohledávat. Pokud by prohledával metodou "pokus omyl", čili by procházel prvky hezky postupně za sebou, mohl by mít tu smůlu, že jeho číslo by bylo úplně až na konci pole, tudíž by potřeboval 10 000 000 porovnání. To je v dnešní době počítačů poměrné dlouhá doba. Metoda půlením intervalu by byla jistě efektivnější, jenže aby fungovala, muselo by se pole nejprve setřídit, což také nějakou dobu potrvá. V případě, že bychom ale čísla uložili do stromu, maximální počet porovnávání by byl roven výšce stromu, která by v 99 procentech případů nebyla 10 000 000. Binární vyhledávací stromy tedy slouží k jakési organizaci dat s následných rychlejším vyhledáváním.

Implementace binárního vyhledávacího stromu

Jestliže již tedy víme, jak vypadá binární vyhledávací strom a jaké je pravidlo pro přidávání prvků, nezbývá nic jiného, než vymyslet, jak binární vyhledávací strom uložit do paměti počítače. Víme, že strom je tvořen několika uzly, proto si můžeme napsat třídu, která nám takový uzel bude reprezentovat. Každý uzel ve stromu obsahuje nějaký klíč, data (záleží na povaze aplikace) a také si pamatuje svého levého a pravého potomka. Levý a pravý potomek opět není nic jiného než zase uzel.

Pozn.: Předpokládá se základní znalost syntaxe C++, znalost OOP a rekurze.



Takto jednoduše by mohla vypadat třída uzel. Metod, které obsahuje, si prozatím nevšímejte, hned se k nim dostaneme. Třída uzel obsahuje proměnnou key, do které bychom v našem případě uložili nějaké číslo. Dále obsahuje dva pointery (nebo chcete-li ukazatele) - jeden slouží jako ukazatel na levého potomka, druhý na pravého potomka. Celý strom se potom skládá z několika instancí třídy Node, přičemž pointery left a right ukazují na dané uzly, neboli na objekty třídy Node.

Konstruktor třídy

Náš konstruktor přebírá jeden parametr typu int, který nám reprezentuje číslo, které uzel obsahuje. Číslo x se tedy v konstruktoru přiřadí do členské proměnné key. Dále se v konstruktoru musí nastavit pointery left a right. Vytvoříme-li ale nový uzel, nemá ještě žádné potomky - proto pointery nastavíme na NULL. Celý tělo konstruktoru je velmi snadné, takže jej určitě dokážete napsat sami.

Přidávání prvků do stromu

To, podle jakého pravidla se do stromu přidávají prvky, jsme si už řekli, ve stručnosti si to ale ještě připomeneme. Začíná se od kořene, kde zjišťujeme, zda je číslo, které chceme přidat, větší nebo menší, než číslo, které obsahuje kořen. Podle toho se rozhodneme pro pravou či levou stranu a celý tento postup se opakuje na dalších uzlech do doby, než najdeme to správné místo pro přidávaný prvek. To poznáme tak, že narazíme na uzel, který nebude mít potomka na té straně, kam budeme chtít prvek přidat - pointer na danou stranu bude mít hodnotu NULL. V té chvíli přidáme prvek do stromu a prvek je úspěšně přidán. Nyní se podívejte jak to lze realizovat v kódu.



Metoda je napsána tak, že pokud bychom náhodou chtěli přidat prvek, který již ve stromu je, bude tento prvek zařazen na levou stranu. Klidně by se dalo napsat, aby se uložil na pravou stranu, nebo aby se neuložil vůbec. Vidíte, že v metodě je použita rekurze. Pokud Vám není jasné proč, přečtěte si znovu předchozí odstavec, kde se píše o tom, že se nějaký postup opakuje na dalších uzlech. V tom je skryto použití rekurze. Nicméně celou metodu lze přepsat za pomocí cyklu.

Vyhledávání prvků

Vyhledat prvek v binárním stromu je velmi snadné. Algoritmus je příjemně jednoduchý, věřím tomu, že někteří z Vás už ví, jak na to. Začneme tím, že srovnáme hledané číslo s číslem kořenu. Mohou nastat tři možnosti:

  • číslo, které obsahuje kořen, je rovno hledanému číslu - hledání končí úspěšně
  • číslo, které hledáme, je větší než číslo, které obsahuje kořen - pak pokračujeme rekurzivně na pravém potomkovi
  • číslo, které hledáme, je menší než číslo, které obsahuje kořen - pak pokračujeme rekurzivně na levém potomkovi

  • Při posledních dvou možnostech je nutné pohlídat, zda uzel má nějakého potomka - v případě že ne, hledané číslo ve stromu není.



    Vidíte, že metoda má návratový typ bool, čili v případě, že prvek byl nalezen, vrací true, jinak false. Celá metoda je opět napsána rekurzivně, ale opět je možné napsat řešení s využitím cyklu.

    Mazání uzlů

    Už jsme si řekli, jak prvky do stromu přidat a jak je následně vyhledat, zatím však ještě nevíme, jakým způsobem prvky ze stromu smazat. Nejprve je nutné daný prvek ve stromu najít. Potom, co jej najdeme, můžeme přejít k samotnému smazání. Jak na to? To, že se k tomu používá klíčové slovo delete je snad jasné, nicméně otázkou zůstavá, jak prvek smazat, aby přitom zůstala zachována stromová struktura. Případ mazání prvku si můžeme rozdělit do tří skupin.
    1. Mažeme uzel, který nemá žádného potomka
    V tomto případě se jedná o velmi jednoduchou záležitost. Uzel, který nemá žádného potomka, můžeme bez problému odstranit a nehrozí, že bychom přišli o nějaké další uzly. Žádné další uzly totiž pod tímto uzlem nejsou.
    2. Mažeme uzel, který má právě jednoho potomka
    V tomto složitějším případě již nemůžeme uzel jen tak odstranit. Pokud bychom to udělali, přišli bychom i o jeho potomka. Potomek by sice čistě teoreticky zůstal v paměti počítače, nebylo by však možné se k němu dostat, protože bychom na něj ztratili ukazatel. Proto tedy celou situaci musíme vyřešit tak, že vezmeme potomka rušeného uzlu (nezáleží na tom, zda je levý, nebo pravý) a napojíme na něj ukazatel z rodiče rušeného uzlu. Jde si to představit tak, že rušený uzel "obejdeme".
    3. Mažeme uzel, který má dva potomky
    Jde o nejsložitější případ mazání uzlu ze stromu. Pro lepší vysvětlení si uzel, který chceme smazat, označme například "a". Uzel "a" má dva potomky a nezapomeňte, že i tito potomci mohou mít další potomky. Čím tedy nahradit uzel "a"? Jednoduše řečeno, uzel "a" nahradíme nejpravějším uzlem z levého podstromu uzlu "a", nebo nejlevějším uzlem z pravého podstromu. Kdybych to měl převést do jednoduché formy, řekl bych, že z uzlu "a" se vydáme na libovolnou stranu a hned poté půjdeme na stranu druhou, dokud nedojdeme na konec. Pro názornější pochopení se podívejte na obrázek.

    Zkusme si smazat uzel s číslem 12. Budeme jej nahrazovat nejlevějším uzlem jeho pravého podstromu, což znamená uzlem s číslem 13. Z uzlu číslo 12 jsme udělali jeden krok doprava a poté jsme postupovali pořád doleva, až jsme došli k uzlu s číslem 13. Po odebrání uzlu s číslem 12 bude strom vypadat takto:

    Můžete vidět, že způsob uspořádání uzlů ve stromu zůstal zachován. Mazání uzlů ze stromu tedy není vůbec nic těžkého, stačí pouze vědět, jak postupovat v daném případě.

    Nalezení největšího prvku

    Někdy se může stát, že potřebujeme zjistit, jaký největší prvek se ve stromu nachází. Pokud se podíváte na organizaci prvků v binárním vyhledávacím stromu, zjistíte, že najít největší prvek je velmi snadné - nachází se totiž úplně vpravo. Stačí tedy od kořene postupovat směrem doprava, dokud nenarazíme na uzel, který již pravého potomka mít nebude. V tu chvíli jsme našli největší prvek.



    Myslím si, že způsob, jak najít nejmenší prvek je zcela jasný, proto to zde ani nebudu rozebírat.

    Průchody stromem

    Poslední častou operací, která se nad binárními stromy provádí, je průchod celým stromem. To znamená, že podle jistého pravidla projdeme celý strom, uzel po uzlu. Pravidla, která určují, jak strom projít, jsou tři:

    • Pre order - toto pravidlo nám říká, že při procházení stromem navštívíme nejprve rodiče, poté levého a pravého potomka.
    • In order - v tomto případě je nejprve navštíven levý potomek, poté rodič a nakonec pravý potomek.
    • Post order - poslední případ je asi jasný - nejprve levý potomek, pak pravý a nakonec rodič.
    Všechny tyto způsoby procházení stromem lze zapsat rekurzivně, není na tom nic těžkého. Na ukázku uvádím způsob implementace průchodu In order. U tohoto způsobu je možno si všimnout, že prvky se navštíví podle velikosti (od nejmenšího po největší).



    O binárních vyhledávacích stromech by se určitě ještě dalo něco napsat. Můžeme třeba chtít metodu, která vrátí výšku celého stromu. Dále můžeme počítat celkový počet uzlů atd... Věřím ale tomu, že na to už dokáže každý přijít sám, stačí pokud pochopí co to vlastně binární stromy jsou, jak jsou organizovány a jak fungují některé nejčastější metody, používáné v souvisloti se stromy.

    Verze pro tisk

    pridej.cz

     

    DISKUZE

    strom a les 9.11.2010 20:50 Jan Němec
    L Re: strom a les 9.11.2010 23:16 Petr Sklenička
    Rekurze 13.12.2010 21:39 Aleš Hakl




    Příspívat do diskuze mohou pouze registrovaní uživatelé.
    > Vyhledávání software
    > Vyhledávání článků

    15.5.2017 23:50 /František Kučera

    Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 18. května od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).


    Přidat komentář

    12.5.2017 16:42 /Honza Javorek
    PyCon CZ, česká konference o programovacím jazyce Python, se po dvou úspěšných ročnících v Brně bude letos konat v Praze, a to 8. až 10. června. Na konferenci letos zavítá např. i Armin Ronacher, známý především jako autor frameworku Flask, šablon Jinja2/Twig, a dalších projektů. Těšit se můžete na přednášky o datové analytice, tvorbě webu, testování, tvorbě API, učení a mentorování programování, přednášky o rozvoji komunity, o použití Pythonu ve vědě nebo k ovládání nejrůznějších zařízení (MicroPython). Na vlastní prsty si můžete na workshopech vyzkoušet postavit Pythonem ovládaného robota, naučit se učit šestileté děti programovat, efektivně testovat nebo si v Pythonu pohrát s kartografickým materiálem. Kupujte lístky, dokud jsou.
    Přidat komentář

    2.5.2017 9:20 /Eva Rázgová
    Putovní konference československé Drupal komunity "DrupalCamp Československo" se tentokrát koná 27. 5.2017 na VUT FIT v Brně. Můžete načerpat a vyměnit si zkušenosti z oblasti Drupalu 7 a 8, UX, SEO, managementu týmového vývoje, využití Dockeru pro Drupal a dalších. Vítáni jsou nováčci i experti. Akci pořádají Slovenská Drupal Asociácia a česká Asociace pro Drupal. Registrace na webu .
    Přidat komentář

    1.5.2017 20:31 /Pavel `Goldenfish' Kysilka
    PR: 25.5.2017 proběhne v Praze konference na téma Firemní informační systémy. Hlavními tématy jsou: Informační systémy s vlastní inteligencí, efektivní práce s dokumenty, mobilní přístup k datům nebo využívání cloudu.
    Přidat komentář

    15.4.2017 15:20 /František Kučera
    Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě IoT a radiokomunikace? Přijď na sraz spolku OpenAlt, který se bude konat ve středu 19. dubna od 18:30 v Šenkovně (Sokolská 60, Praha 2).
    Přidat komentář

    5.3.2017 19:12 /Redakce Linuxsoft.cz
    PR: 23. března proběhne v Praze konferenci na téma Cloud computing v praxi. Hlavními tématy jsou: Nejžhavější trendy v oblasti cloudu a cloudových řešení, Moderní cloudové služby, Infrastruktura současných cloudů, Efektivní využití cloudu, Nástrahy cloudových řešení a jak se jim vyhnout.
    Přidat komentář

    27.2.2017 22:12 /František Kučera
    Pozvánka na 137. sraz OpenAlt – Praha: Tentokrát jsme si pro vás připravili neobvyklou akci. Ve středu 1.3. v 17:30 nás přivítá sdružení CZ.NIC ve svých prostorách v Milešovské ulici číslo 5 na Praze 3, kde si pro nás připravili krátkou prezentaci jejich činnosti. Následně navštívíme jejich datacentrum pod Žižkovskou věží. Provedou nás prostory, které jsou běžnému smrtelníkovi nedostupné!
    Po ukončení prohlídky se všchni odebereme do hostince U vodoucha, Jagelonská 21, Praha 3 pochutnat si na některém z vybraných piv či dát si něco na zub. Rezervaci máme od 19:30, heslo je OpenAlt.
    Ale pozor! Do prostor datového centra máme omezený přístup, dostane se tam pouze 10 lidí! Takže kdo přijde dříve, ten má přednost, a občanky s sebou! Kdo nebude chtít na prohlídku datového centra, může se pomalu přesunout do hostince U vodoucha a u nepřeberné nabídky piv počkat na ostatní.
    Přidat komentář

    18.1.2017 0:49 /František Kučera
    Členové a příznivci spolku OpenAlt se pravidelně schází v Praze a Brně. Fotky z pražských srazů za uplynulý rok si můžete prohlédnout na stránkách spolku. Příští sraz se koná už 19. ledna – tentokrát je tématem ergonomie ovládání počítače – tzn. klávesnice, myši a další zařízení. Také budete mít příležitost si prohlédnout pražský hackerspace Brmlab.
    Přidat komentář

       Více ...   Přidat zprávičku

    > Poslední diskuze

    15.6.2017 9:34 / Ondřej Havlas
    php,

    10.6.2017 10:39 / Temple
    sell home for cash

    11.5.2017 23:32 / lelo
    Re: Problém se správcem balíčků

    11.5.2017 5:45 / davd mašek
    Re: Problém se správcem balíčků

    10.5.2017 22:54 / lelo
    Re: Problém se správcem balíčků

    Více ...

    ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2017) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze