Čteme lineární datové struktury jako pole, propojený seznam, zásobník a frontu, ve kterých jsou všechny prvky uspořádány sekvenčním způsobem. Pro různé druhy dat se používají různé datové struktury.

Při výběru datové struktury se berou v úvahu některé faktory:

Jaký typ dat je třeba ukládat?: Je možné, že určitá struktura dat může být pro určitý druh dat nejvhodnější.Náklady na operace:Chceme-li minimalizovat náklady na operace u nejčastěji prováděných operací. Máme například jednoduchý seznam, na kterém musíme provést operaci vyhledávání; pak můžeme vytvořit pole, ve kterém jsou prvky uloženy v seřazeném pořadí, aby se provedlo binární vyhledávání . Binární vyhledávání funguje velmi rychle pro jednoduchý seznam, protože rozděluje vyhledávací prostor na polovinu.Využití paměti:Někdy chceme datovou strukturu, která využívá méně paměti.

Strom je také jednou z datových struktur, které představují hierarchická data. Předpokládejme, že chceme zobrazit zaměstnance a jejich pozice v hierarchické formě, pak to může být znázorněno níže:

Výše uvedený strom ukazuje organizační hierarchie nějaké společnosti. Ve výše uvedené struktuře John je výkonný ředitel společnosti a John má dva přímé podřízené pojmenované jako Steve a Rohan . Steve má jmenované tři přímé podřízené Lee, Bob, Ella kde Steve je manažer. Bob má jmenované dva přímé podřízené Musí a Emma . Emma má dvě přímé podřízené jmenované Tome a Raj . Tom má jmenovanou jednu přímou podřízenou Účtovat . Tato konkrétní logická struktura je známá jako a Strom . Jeho struktura je podobná skutečnému stromu, proto se nazývá a Strom . V této struktuře, vykořenit je nahoře a jeho větve se pohybují směrem dolů. Můžeme tedy říci, že stromová datová struktura je efektivní způsob ukládání dat hierarchickým způsobem.

Pojďme pochopit některé klíčové body stromové datové struktury.

jak převést celé číslo na řetězec v java

• Stromová datová struktura je definována jako kolekce objektů nebo entit známých jako uzly, které jsou vzájemně propojeny, aby reprezentovaly nebo simulovaly hierarchii.
• Stromová datová struktura je nelineární datová struktura, protože se neukládá sekvenčním způsobem. Jedná se o hierarchickou strukturu, protože prvky ve stromu jsou uspořádány do více úrovní.
• Ve stromové datové struktuře je nejvyšší uzel známý jako kořenový uzel. Každý uzel obsahuje nějaká data a data mohou být libovolného typu. Ve výše uvedené stromové struktuře uzel obsahuje jméno zaměstnance, takže typ dat by byl řetězec.
• Každý uzel obsahuje nějaká data a odkaz nebo odkaz na jiné uzly, které lze nazvat děti.

Některé základní pojmy používané ve stromové datové struktuře.

Podívejme se na stromovou strukturu, která je zobrazena níže:

Ve výše uvedené struktuře je každý uzel označen nějakým číslem. Každá šipka zobrazená na obrázku výše je známá jako a odkaz mezi dvěma uzly.

Vykořenit:Kořenový uzel je nejvyšší uzel ve stromové hierarchii. Jinými slovy, kořenový uzel je ten, který nemá žádného rodiče. Ve výše uvedené struktuře je uzel s číslem 1 kořenový uzel stromu. Pokud je uzel přímo spojen s nějakým jiným uzlem, nazývá se vztah rodič-dítě.Podřízený uzel:Pokud je uzel potomkem libovolného uzlu, pak je uzel označován jako podřízený uzel.Rodič:Pokud uzel obsahuje jakýkoli poduzel, pak se o tomto uzlu říká, že je rodičem tohoto poduzlu.Sourozenec:Uzly, které mají stejného rodiče, se nazývají sourozenci.Listový uzel: -Uzel stromu, který nemá žádný podřízený uzel, se nazývá listový uzel. Listový uzel je nejspodnější uzel stromu. V obecném stromu může být libovolný počet listových uzlů. Listové uzly lze také nazývat vnější uzly.Vnitřní uzly:Uzel má alespoň jeden podřízený uzel známý jako an vnitřní Uzel předka:-Předkem uzlu je jakýkoli předchůdce na cestě od kořene k tomuto uzlu. Kořenový uzel nemá žádné předky. Ve stromu zobrazeném na obrázku výše jsou uzly 1, 2 a 5 předky uzlu 10.Potomek:Bezprostřední následník daného uzlu je znám jako potomek uzlu. Na obrázku výše je 10 potomkem uzlu 5.

Vlastnosti stromové datové struktury

Rekurzivní datová struktura:Strom je také známý jako a rekurzivní datová struktura . Strom lze definovat jako rekurzivně, protože rozlišovací uzel ve stromové datové struktuře je znám jako a kořenový uzel . Kořenový uzel stromu obsahuje odkaz na všechny kořeny jeho podstromů. Levý podstrom je na obrázku níže zobrazen žlutou barvou a pravý podstrom červenou barvou. Levý podstrom lze dále rozdělit na podstromy zobrazené ve třech různých barvách. Rekurze znamená snížit něco podobným způsobem. Tato rekurzivní vlastnost stromové datové struktury je tedy implementována v různých aplikacích.
Počet hran:Pokud existuje n uzlů, pak by bylo n-1 hran. Každá šipka ve struktuře představuje odkaz nebo cestu. Každý uzel, kromě kořenového, bude mít alespoň jedno příchozí spojení známé jako okraj. Pro vztah rodič-dítě by existoval jeden odkaz.Hloubka uzlu x:Hloubku uzlu x lze definovat jako délku cesty od kořene k uzlu x. Jedna hrana přispívá jednou jednotkou délky v cestě. Hloubku uzlu x lze tedy také definovat jako počet hran mezi kořenovým uzlem a uzlem x. Kořenový uzel má hloubku 0.Výška uzlu x:Výšku uzlu x lze definovat jako nejdelší cestu z uzlu x do listového uzlu.

Na základě vlastností stromové datové struktury jsou stromy klasifikovány do různých kategorií.

css zarovnání textu

Implementace stromu

Stromovou datovou strukturu lze vytvořit dynamickým vytvářením uzlů pomocí ukazatelů. Strom v paměti může být znázorněn následovně:

Výše uvedený obrázek ukazuje znázornění stromové datové struktury v paměti. Ve výše uvedené struktuře obsahuje uzel tři pole. Druhé pole ukládá data; první pole ukládá adresu levého potomka a třetí pole adresu pravého potomka.

V programování lze strukturu uzlu definovat jako:

 struct node { int data; struct node *left; struct node *right; } 

Výše uvedenou strukturu lze definovat pouze pro binární stromy, protože binární strom může mít maximálně dva potomky a generické stromy mohou mít více než dva potomky. Struktura uzlu pro generické stromy by byla odlišná ve srovnání s binárním stromem.

Aplikace stromů

Níže jsou uvedeny aplikace stromů:

Ukládání přirozeně hierarchických dat:Stromy se používají k ukládání dat v hierarchické struktuře. Například souborový systém. Souborový systém uložený na disku, soubor a složka jsou ve formě přirozeně hierarchických dat a jsou uloženy ve formě stromů.Uspořádat data:Používá se k organizaci dat pro efektivní vkládání, mazání a vyhledávání. Například binární strom má čas logN pro vyhledávání prvku.Zkuste:Je to speciální druh stromu, který se používá k uložení slovníku. Je to rychlý a efektivní způsob dynamické kontroly pravopisu.Halda:Je to také stromová datová struktura implementovaná pomocí polí. Používá se k implementaci prioritních front.B-strom a B+strom:B-Strom a B+Strom jsou stromové datové struktury používané k implementaci indexování v databázích.Směrovací tabulka:Stromová datová struktura se také používá k ukládání dat do směrovacích tabulek ve směrovačích.

Typy stromové datové struktury

Níže jsou uvedeny typy stromové datové struktury:

Obecný strom:Obecný strom je jedním z typů stromové datové struktury. V obecném stromu může mít uzel 0 nebo maximálně n počet uzlů. Neexistuje žádné omezení na stupeň uzlu (počet uzlů, které může uzel obsahovat). Nejvyšší uzel v obecném stromu se nazývá kořenový uzel. Děti nadřazeného uzlu jsou známé jako podstromy .

Může být n počet podstromů v obecném stromu. V obecném stromu nejsou podstromy seřazeny, protože uzly v podstromu nelze seřadit.
Každý neprázdný strom má sestupnou hranu a tyto hrany jsou spojeny s uzly známými jako podřízené uzly . Kořenový uzel je označen úrovní 0. Uzly, které mají stejného rodiče, jsou známé jako sourozenci . Binární strom :Zde samotný binární název naznačuje dvě čísla, tj. 0 a 1. V binárním stromě může mít každý uzel ve stromu maximálně dva podřízené uzly. Maximální zde znamená, zda má uzel 0 uzlů, 1 uzel nebo 2 uzly.

Chcete-li se dozvědět více o binárním stromu, klikněte na níže uvedený odkaz:
https://www.javatpoint.com/binary-tree Binární vyhledávací strom :Binární vyhledávací strom je nelineární datová struktura, ke které je připojen jeden uzel n počet uzlů. Jde o datovou strukturu založenou na uzlech. Uzel může být reprezentován v binárním vyhledávacím stromu se třemi poli, tj. datová část, levý potomek a pravý potomek. Uzel může být připojen k maximálně dvěma podřízeným uzlům v binárním vyhledávacím stromu, takže uzel obsahuje dva ukazatele (levý podřízený a pravý podřízený ukazatel).
Každý uzel v levém podstromu musí obsahovat hodnotu menší než je hodnota kořenového uzlu a hodnota každého uzlu v pravém podstromu musí být větší než hodnota kořenového uzlu.

Uzel lze vytvořit pomocí uživatelem definovaného datového typu známého jako struktura, Jak je ukázáno níže:

převést řetězec na celé číslo

 struct node { int data; struct node *left; struct node *right; } 

Výše je struktura uzlu se třemi poli: datové pole, druhé pole je levý ukazatel typu uzlu a třetí pole je pravý ukazatel typu uzlu.

Chcete-li se dozvědět více o binárním vyhledávacím stromu, klikněte na níže uvedený odkaz:

https://www.javatpoint.com/binary-search-tree

strom AVL

Je to jeden z typů binárního stromu, nebo můžeme říci, že je to varianta binárního vyhledávacího stromu. AVL strom splňuje vlastnost binární strom stejně jako z binární vyhledávací strom . Je to samovyrovnávací binární vyhledávací strom, který vynalezl Adelson Velsky Lindas . Zde samovyvažování znamená vyrovnávání výšek levého podstromu a pravého podstromu. Toto vyvážení se měří v vyrovnávací faktor .

Strom můžeme považovat za AVL strom, pokud se strom podřizuje binárnímu vyhledávacímu stromu a také vyvažujícímu faktoru. Vyrovnávací faktor lze definovat jako rozdíl mezi výškou levého podstromu a výškou pravého podstromu . Hodnota vyvažovacího faktoru musí být buď 0, -1 nebo 1; proto by každý uzel ve stromu AVL měl mít hodnotu vyvažovacího faktoru buď jako 0, -1 nebo 1.

Chcete-li se dozvědět více o AVL stromu, klikněte na níže uvedený odkaz:

seznam polí seřazen

https://www.javatpoint.com/avl-tree

Červeno-černý strom

Červeno-černý strom je binární vyhledávací strom. Předpokladem červeno-černého stromu je, že bychom měli vědět o binárním vyhledávacím stromu. V binárním vyhledávacím stromu by hodnota levého podstromu měla být menší než hodnota tohoto uzlu a hodnota pravého podstromu by měla být větší než hodnota tohoto uzlu. Jak víme, časová složitost binárního vyhledávání je v průměrném případě log₂n, nejlepší případ je O(1) a nejhorší případ je O(n).

Když se na stromě provádí jakákoliv operace, chceme, aby byl náš strom vyvážený, aby všechny operace jako vyhledávání, vkládání, mazání atd. trvaly méně času a všechny tyto operace byly časově náročné. log₂n.

Červeno-černý strom je samovyrovnávací binární vyhledávací strom. AVL strom je pak také binární vyhledávací strom vyvažující výšku proč potřebujeme červeno-černý strom . Ve stromu AVL nevíme, kolik rotací by bylo potřeba k vyvážení stromu, ale v červeno-černém stromě jsou k vyvážení stromu potřeba maximálně 2 rotace. Obsahuje jeden extra bit, který představuje buď červenou nebo černou barvu uzlu, aby bylo zajištěno vyvážení stromu.

Rozvětvený strom

Datová struktura splay tree je také binární vyhledávací strom, ve kterém je nedávno zpřístupněný prvek umístěn na kořenovou pozici stromu provedením některých rotačních operací. Tady, rozlévání znamená nedávno použitý uzel. Je to a samovyvažování binární vyhledávací strom bez explicitní podmínky rovnováhy jako AVL strom.

Je možné, že výška rozkládacího stromu není vyvážená, tj. výška levého a pravého podstromu se může lišit, ale operace v rozkládacím stromě mají pořadí uklidnit čas kde n je počet uzlů.

Rozvětvený strom je vyvážený strom, ale nelze jej považovat za výškově vyvážený strom, protože po každé operaci se provádí rotace, která vede k vyváženému stromu.

Treap

Datová struktura Treap pochází z datové struktury Tree a Heap. Zahrnuje tedy vlastnosti jak stromových, tak i haldových datových struktur. V binárním vyhledávacím stromu musí být každý uzel v levém podstromu roven nebo menší než hodnota kořenového uzlu a každý uzel v pravém podstromu musí být roven nebo větší než hodnota kořenového uzlu. V datové struktuře haldy obsahují pravý i levý podstrom větší klíče než kořen; můžeme tedy říci, že kořenový uzel obsahuje nejnižší hodnotu.

V datové struktuře treap má každý uzel obojí klíč a přednost kde klíč je odvozen z binárního vyhledávacího stromu a priorita je odvozena z datové struktury haldy.

The Treap datová struktura má dvě vlastnosti, které jsou uvedeny níže:

• Pravý potomek uzlu>=aktuální uzel a levý potomek uzlu<=current node (binary tree)< li>
• Děti jakéhokoli podstromu musí být větší než uzel (hromada)

B-strom

B-strom je vyvážený m-cesta strom kde m určuje pořadí stromu. Doposud jsme četli, že uzel obsahuje pouze jeden klíč, ale b-strom může mít více než jeden klíč a více než 2 potomky. Vždy udržuje setříděná data. V binárním stromě je možné, že listové uzly mohou být na různých úrovních, ale v b-stromu musí být všechny listové uzly na stejné úrovni.

Pokud je objednávka m, má uzel následující vlastnosti:

• Každý uzel v b-stromu může mít maximum m děti
• Pro minimální děti má listový uzel 0 potomků, kořenový uzel má minimálně 2 děti a vnitřní uzel má minimální strop m/2 děti. Například hodnota m je 5, což znamená, že uzel může mít 5 potomků a vnitřní uzly mohou obsahovat maximálně 3 potomky.
• Každý uzel má maximum (m-1) klíčů.

Kořenový uzel musí obsahovat minimálně 1 klíč a všechny ostatní uzly musí obsahovat alespoň 1 klíč strop m/2 minus 1 klíče.

kdo je urfi javed