Jak se nechat píchnout stromy

Otočte ten strom vzhůru nohama!

Jakmile se vám ve vaší hlavě rozsvítí žárovka datové struktury, je opravdu těžké nevidět datovou strukturu tak, jak vypadáte! Nebo ... možná to jsem jen já.

Před několika týdny jsem objevil radost z propojených seznamů a mnoho různých abstraktních datových typů, které pomocí nich můžeme vytvořit! Jakmile jsem si uvědomil, že tyto jednoduché datové struktury byly ve skutečnosti pod povrchem tolika věcí, které jsem používal ve své práci a životě každý den, byl jsem trochu foukaný pryč. Jak se však ukázalo, byl to jen vrchol ledovce datových struktur! Protože to samozřejmě je. Toto je konec konců počítačová věda, kde lze problémy řešit mnoha různými způsoby! Totéž platí pro data, která lze uspořádat různými způsoby.

Doposud jsme se zabývali většinou pouze jedním typem datové struktury. Ale dnes se trochu zblázníme a vytřepeme naše data z provozu! Je to proto, že se konečně chystáme ponořit do nelineárních datových struktur, počínaje mým osobním favoritem: stromy!

Růst jakéhokoli druhu poboček, které chcete!

Možná si pamatujete, že existuje mnoho různých způsobů, jak kategorizovat datové struktury. Jednou z širších kategorií, jak můžeme ukládat naše data, je to, zda jsou naše data lineární nebo ne - to znamená, zda existuje posloupnost a pořadí, jak jsou naše data konstruována a procházena. V lineárních strukturách dat - jako jsou pole nebo propojené seznamy - jsou data uspořádána a na tomto pořadí záleží; způsob, kterým procházíte lineární datovou strukturu, přímo souvisí s jejím uspořádáním, protože prvky v lineární datové struktuře lze procházet pouze postupně.

Lineární datové struktury ve volné přírodě

Ale jak víme, existují také nelineární datové struktury! Čím více jsem o nich četl a dozvěděl se, tím chladnější se jeví. Mohou však být také trochu složitější a neslušně, což je důvod, proč může být opravdu užitečné mít nejprve dobře zvládnutou strukturu lineárních dat, jen abychom pochopili základní rozdíl mezi nimi od začátku.

V nelineárních datových strukturách data opravdu nesledují pořadí - přinejmenším ne zřejmá numerická, jako u polí nebo propojených seznamů. A protože data nemusí být nutně uspořádána v určitém pořadí, je snadné (a vlastně docela běžné) procházet nelineární datovou strukturu nesekvenčním způsobem.

Jedním z důležitých typů nelineárních datových struktur je strom. A pokud chceme porozumět stromům a jak o nich mluvit, musíme být schopni identifikovat části stromu! Přestože vypadají velmi odlišně od struktur, kterými jsme se dosud zabývali, jsou ve skutečnosti tvořeny stejnými věcmi.

Stromy - jako propojené seznamy - jsou tvořeny uzly a odkazy.

Všechny stromy, ať už jsou to duby, javor nebo ginkové, začnou klíčit pevnou sadou kořenů. Ve stromových strukturách dat musíte mít vždy kořen, i když nemáte nic jiného. Ve skutečnosti, kdybychom měli jen kořen, měli bychom jeden uzel. Ale tady je to zajímavé: kořenový uzel může mít odkazy na více dalších uzlů. A právě tady je zásadní rozdíl mezi lineárními strukturami, na které jsme se dosud dívali, a stromy, o nichž se nyní učíme. Jeden uzel se může připojit k mnoha dalším, což znamená, že stromy mohou růst různými tvary a způsoby.

Identifikace částí struktury dat stromu

Zde je několik dobrých výrazů, které byste měli vědět, pokud jde o stromy:

  • Kořen: nejvyšší vrchol stromu, který k němu nikdy nemá žádné odkazy ani hrany
  • Link / Edge: odkaz, který obsahuje nadřazený uzel a který mu říká, jaký je jeho podřízený uzel
  • Podřízený: jakýkoli uzel, který má nadřazený uzel, který na něj odkazuje
  • Nadřazený: jakýkoli uzel, který má odkaz nebo odkaz na jiný uzel
  • Sibling: jakákoli skupina uzlů, které jsou dětmi stejného uzlu
  • Interní: jakýkoli uzel, který má podřízený uzel (v podstatě všechny nadřazené uzly)
  • Leaf: jakýkoli uzel, který nemá podřízený uzel ve stromu

Pokud se tyto podmínky vůbec cítí ohromující, považuji za užitečné myslet na datové struktury stromů, jako je rodokmen nebo dokonce firemní žebřík. Data jsou vždy hierarchická. Nahoře budete mít někoho (kořenový uzel), který deleguje na některé další uzly (nadřazené uzly), které jim mohou nebo mohou podat zprávu někdo jiný (podřízené uzly). Nebo máte obrovskou rodinu, s nadřazenými uzly, podřízenými uzly, všechny vedoucími zpět k kořenům předků.

Stejně tak dlouho, jak si pamatujete, že data mají hierarchickou povahu, by žargon měl snad být o něco méně znepokojující.

Vyslovte svou (stromovou) pravdu

Bez ohledu na to, jak strom vypadá, kolik větví nebo listů má nebo jak roste, existují univerzální „stromové pravdy“, které se chovají jako samozřejmé.

Zjistil jsem, že je to mnohem srozumitelnější, když je vizualizujeme, takže se zde opíráme o některé příklady. Pojďme se podívat na tento strom, který máme níže. Celkem má 10 uzlů, včetně kořenového uzlu.

Stromové pravdy: strom bude mít vždy o jeden odkaz méně, než je jeho celkový počet uzlů

Zajímavá pravda o tomto stromu je, že má 10 uzlů, ale 9 odkazů nebo hran. Existuje vztah, který platí bez ohledu na počet uzlů, a můžeme si snadno zapamatovat:

Pokud má strom uzly, bude mít vždy o jeden menší počet hran (n-1).

A když se podíváme na strom, začíná být jasné, proč tomu tak je. Kořenový uzel je uzel, který nikdy nemůže mít žádné rodiče. Proto na ni nikdy nemůže nic odkazovat. Pokud každý uzel musí mít jeden další uzel, který na něj odkazuje odkazem / hranou (s výjimkou kořenového uzlu), můžeme si být vždy jisti, že náš strom bude mít odkazy n-1, když n je celkový počet uzlů ve stromu. Jak cool (a mocné!) Je to, že můžeme tyto informace znát tak snadno, aniž bychom museli procházet stromem ?!

Ale počkejte - tady je další pravda, která je možná ještě chladnější: stromy ve skutečnosti obsahují stromy v nich!

Stromové pravdy: stromy jsou rekurzivní datové struktury

Stromy jsou rekurzivní datové struktury, protože strom je obvykle složen z menších stromů - často označovaných jako podstromy - uvnitř něj. Dítě jednoho uzlu ve stromu může být velmi dobře rodičem jiného stromu (což z něj činí kořen podstromu). To může být opravdu zajímavé, pokud jde o psaní algoritmů pro procházení nebo prohledávání stromem, protože vnoření stromů nás někdy může vést k psaní rekurzivních vyhledávacích algoritmů.

Ale zatím se nedostaneme do stromového stromu. Místo toho se podíváme na něco, co je důležitější pochopit nejprve: různé způsoby, jak můžeme klasifikovat naše stromy, které se hodí po silnici.

Jak vysoký je váš strom?

Protože stromy mohou mít tolik různých tvarů a velikostí, je velmi důležité, aby bylo možné zjistit a pochopit, jaký typ stromu se zabýváte a jak tato data vypadají. Za tímto účelem existují dvě nejdůležitější vlastnosti, o nichž se hovoří o tom, s jakým druhem stromu se zabýváte a kde v tomto stromu žijete data.

Z velké části jsou dvěma vlastnostmi, které se budeme nejvíce zabývat, buď hloubka uzlu nebo výška uzlu.

Jednoduchý způsob, jak přemýšlet o hloubce uzlu, je odpovědět na otázku: jak daleko je uzel od kořene stromu?

Jak ale víme, co je v tomto případě daleko? I přesto, že jsme se dosud nedostali do všech komplexů stromového křížení, existuje jen jeden způsob, jak stromem procházet nebo hledat: vytvořením cesty a sledováním hran / odkazů z kořenového uzlu dolů. Mohli bychom tedy určit, jak daleko je uzel od kořenového uzlu počítáním počtu odkazů, které je potřeba k dosažení tohoto uzlu z kořenového uzlu.

V ukázaném příkladu je hloubka růžového uzlu 2, protože přesně tam jsou 2 odkazy spojující kořenový uzel s růžovým uzlem. Hloubka fialového uzlu je však 3, protože k přechodu dolů z kořenového uzlu do fialového uzlu trvá 3 odkazy.

Hloubka a výška uzlu ve struktuře dat stromu

Nyní, když víme, jak hloubka funguje, je druhá vlastnost o něco jednodušší. Výška uzlu může být zjednodušena položením otázky: jak daleko je tento uzel od jeho nejdále vzdáleného listu? (Pamatujte: obracíme stromy vzhůru nohama v divokém světě počítačů, což je důvod, proč se výška určuje tímto způsobem!)

Můžeme tedy najít výšku uzlu nalezením jeho nejvzdálenějšího dětského listu a spočítáním cesty odkazů, kterou k dosažení tohoto cíle potřebuje. V příkladu je výška oranžového uzlu 3, protože jeho nejvzdálenější dětské listy (ve skutečnosti jsou tři) jsou tři odkazy od oranžového uzlu. Bonusové body, pokud zjistíte, jaká je hloubka oranžového uzlu!

Skvělá věc zejména o vlastnosti height je, že výška kořenového uzlu je automaticky výškou celého stromu samotného. V podstatě to znamená, že jakmile najdeme listový uzel, který je nejvzdálenější od kořene, víme nyní nejdelší možnou cestu ve stromu, která nám říká, jak je ve skutečnosti vysoká!

Důvod, proč je hloubka a výška tak důležitá, je ten, že nám říkají hodně o tom, jak strom vypadá, hned vedle netopýra. A věc o stromech (jak jsem si jistý, že teď všichni víme) je, že všichni mohou vypadat jinak. Jedním z rychlých příkladů jsou vyvážené stromy proti nevyváženým stromům.

Vyvážené stromy versus nevyvážené stromy

Strom se považuje za vyvážený, pokud se žádné ze dvou sourozeneckých podstromů neliší výškou o více než jednu úroveň. Pokud se však dvě sourozenecké podstromy výrazně liší výškou (a mají více než jednu úroveň hloubky rozdílu), strom je nevyvážený.

Vyvážené stromy se objevují, když mluvíme o stromových operacích, a zejména o traversalu. Myšlenka za tím je, že pokud můžeme procházet stromem a omezit na polovinu počtu operací, budeme mít lepší datovou strukturu. U nevyváženého stromu to však rozhodně není, protože jeden podstrom může být podstatně větší než podstrom jeho sourozence. Mnoho problémů s efektivitou provozu, které řeší vyvážené stromy, se ve skutečnosti nazývá binární stromy - ale příští týden to bude mnohem více!

Odkrývání kořenů stromů

Abychom skutečně ocenili sílu stromu, musíme se na ně dívat v kontextu jejich aplikace. Jinými slovy: pravděpodobně to nebude v pohodě, dokud je neuvidíte ve volné přírodě!

Jeden jednoduchý příklad leží uvnitř objektově orientovaných jazyků: hlavní objekt je kořenový uzel, zatímco třídy, které z něj dědí, jsou děti hlavní třídy. To dává větší smysl, když o tom přemýšlíte; skutečnost, že se často nazývá „hierarchie tříd“, se hodí do struktury dat hierarchického stromu.

Nejviditelnější (možná to dosud nebylo zřejmé!) Je struktura souborů projektu - nebo dokonce souborový systém v počítači! Pokud o tom přemýšlíme, všechny důležité části již existují: kořenový adresář s podřízenými uzly, které mohou být vlastními podadresáři, nebo listy stromu, které končí pouhým jednoduchým souborem. Všechno je to opravdu jen hierarchická stromová struktura dat!

A abychom si mysleli, všichni jsme se tak dlouho vyhřívali ve stínu stromu a neměli jsme ani ponětí.

Zdroje

Pokud jste objímačem stromů nebo nadšencem stromů, nebo se jen chcete dozvědět něco více, podívejte se na tyto užitečné odkazy!

  1. Struktury dat: Úvod do stromů, mycodeschool
  2. Struktury dat: Stromy, HackerRank
  3. Stromy, profesor Jonathan Cohen
  4. Struktury stromových dat, profesor David Schmidt
  5. Vyvažování stromů, profesor R. Clayton