Všude nás obklopují hierarchické struktury – například struktura podnikového managementu, adresy, obsah v knihách. Hierarchii najdeme také v programování, například při práci se standardními datovými typy, jako jsou pole. Protože taková data nelze uspořádat lineárně, programátoři používají stromy. Jsou považovány za jednu z nejdůležitějších nelineárních struktur, se kterými se lze setkat při práci s algoritmy.
V této lekci budeme mluvit o stromech, dozvíme se, jaké problémy řeší a jaké vlastnosti a způsoby reprezentace stromů existují.
Co jsou stromy a k čemu slouží?
Stromy se používají k reprezentaci hierarchických vztahů v paměti počítače. Používají se pro registr Windows, dokumenty XML, struktury DOM stránek HTML, rodokmeny, katalogy dílů nebo systémy souborů. Například takto vidí koncoví uživatelé strukturu souborů:
Pro programátory to však vypadá jinak:
Toto je stromová reprezentace struktury. Z tohoto diagramu lze usoudit, že strom je konečná množina, která se skládá z vrcholy nebo uzlya existuje také vyhrazený uzel – kořen stromu. Ve výše uvedeném příkladu jsou nahoře všechny složky a kořen stromu je „Nová složka“.
Každý uzel obsahuje data a odkazy na další nesouvislé stromy. V tomto případě je pro ně každá složka ve stromu, ze které pocházejí další data kořenový uzel. V tomto případě tato data tvoří podstrom hlavního stromu.
Kromě znázornění hierarchických vztahů se stromy používají v následujících případech:
Organizace rychlého vyhledávání v setříděných datech, například v databázových indexech
Shlukování dat. Možnost rozdělit data do clusterů se využívá v databázích a strojovém učení
Řešení složitých aritmetických výrazů. Strom se používá k uložení pořadí operací, hodnot argumentů a mezivýsledků.
Rozhodovací algoritmy. Rozhodovací strom je nástroj pro dolování dat a vytváření předpovědí. Je považován za snáze použitelný nástroj než neuronové sítě, protože formuluje pravidla v přirozeném jazyce
Síťová interakce. Stromy se používají pro směrování a mechanismy pro určování IP adres na základě adres URL webu, například server DNS
Stromy se často používají v projektech vývoje softwaru. V důsledku toho vývojáři zdůraznili terminologii pro popis uzlů a tvarů stromů.
Jaké uzly jsou ve stromech?
Vzhledem k tomu, že vzhled stromu je podobný rodokmenu, používají se v programování také genealogické termíny. Například ve vztahu k algoritmickým stromům můžete slyšet pojmy jako „zakladatel dynastie“, „matka“, „dítě“, „bratr“, „bratranec“. Existují však standardizované konvence pojmenování pro vztahy uzlů:
Nadřazený uzel nebo předchůdce – uzel, který je na první úrovni hierarchie
Dětský uzel nebo potomek — uzel, na který existují odkazy z příslušného uzlu
Kořenový uzel – uzel, na který nevedou žádné vazby z jiných uzlů
Sesterské uzly – dva uzly, které mají společné rodiče
Listový uzel, list stromu nebo terminálový uzel — uzel, jehož počet podstromů je nula
Uzel větve nebo vnitřní vrchol – uzel, který má podřízené struktury
Počet podstromů, které uzel má, se nazývá jeho stupeň. Maximální hodnota stupně uzlu je stromový stupeň. Pokud je stromový stupeň dva, pak každý uzel může mít maximálně dva potomky:
Jaké tvary stromů existují?
Kvůli určitým vlastnostem úkolů a algoritmů používají vývojáři různé formy stromů s vlastními charakteristikami organizace vrcholů:
Objednaný strom — strom, ve kterém jsou seřazeny všechny vrcholy. Takové stromy se také nazývají byt, protože sekvenční procházení vrcholů povede k seřazenému poli:
Plný strom — strom, ve kterém se počet podřízených uzlů v každém vnitřním vrcholu rovná stupni stromu:
Dokončený strom – strom, ve kterém je každá úroveň, kromě poslední, dokončena:
Ideální strom — úplný strom, ve kterém jsou všechny koncové uzly umístěny na stejné úrovni:
Seznámili jsme se se základní terminologií, která se při práci se stromy používá. Nyní se podívejme na to, jaké existují způsoby, jak stromy graficky a v kódu znázornit.
Jak mohou stromy vypadat
Chcete-li zobrazit hierarchické struktury, použijte následující možnosti:
Podívejme se na každý způsob zobrazení stromu.
Schéma stromu
Hlavním způsobem reprezentace stromů jsou názvy, čísla vrcholů nebo obsah užitečného zatížení uzlů. Jsou spojeny čarami, které označují spojení mezi vrcholy:
Tato metoda je podobná přírodním stromům, pouze v informatice se kořen stromu obvykle kreslí v horní části diagramu.
Eulerovy kruhy
Algoritmický strom můžeme znázornit podle pravidel teorie množin pomocí Eulerových kruhů:
Tato metoda je v praxi poměrně vzácná, protože podstromy se obvykle navzájem neprotínají. V takové situaci je použití schematického znázornění pro člověka vizuálnější.
Odsazené seznamy
Hierarchický vztah lze znázornit pomocí očíslovaného, odsazeného seznamu, kde odsazení nebo číslo řádku udává jeho úroveň:
Tento formát se používá při práci s knihou, protože obsah je strom.
Abyste mohli pracovat se stromy, musíte je umět nejen kreslit, ale také ukládat do paměti počítače.
Ve formě kódu získáme následující třídu uzlů:
Chcete-li uspořádat strom z uzlu, musíte přidat metody, které naplní odkazy na podstromy child1 a child2. V následujících lekcích podrobně prozkoumáme, jak jsou stromy implementovány v kódu.
Před kódováním stromu vývojáři často zobrazují hierarchii graficky, aby viděli úplný obraz vztahů.
