Úvod do stromov v dátovej štruktúre

Predtým, ako pochopíme typy stromov v dátovej štruktúre, najprv si preštudujeme stromy v dátovej štruktúre. Strom v počítačovom poli sa označuje aj ako strom skutočného sveta, rozdiel medzi skutočným svetom a stromom výpočtového poľa je však ten, že je vizualizovaný ako hore nohami a koreňom nad ním a vetvením od koreňa k listom stromu. Medzi rôznymi aplikáciami v reálnom svete sa používa stromová dátová štruktúra, ktorá môže demonštrovať vzťahy medzi rôznymi uzlami s hierarchiou rodič - dieťa. Z tohto dôvodu sa nazýva aj hierarchická štruktúra údajov. Je najobľúbenejší na zjednodušenie a zrýchlenie vyhľadávania a triedenia. Je považovaná za jednu z najsilnejších a najmodernejších dátových štruktúr. Strom predstavuje reprezentáciu nelineárnej dátovej štruktúry. Strom môže byť zobrazený pomocou rôznych užívateľom definovaných alebo primitívnych typov údajov. Na implementáciu stromu môžeme použiť polia, triedy spojené zoznamy alebo iné druhy dátových štruktúr. Je to skupina vzájomne prepojených uzlov. Uzly sú pripojené k okrajom, aby sa demonštroval vzťah.

Vzťahy v strome: Vo vyššie uvedenom diagrame je P koreň stromu, P je tiež rodičom Q, R a S. Q je dieťa P. Preto Q, R a S sú súrodenci. Zatiaľ čo P je starým rodičom A, B, C, D a E.

Čo sú to stromy?

Strom je hierarchická dátová štruktúra, ktorá prirodzene ukladá informácie hierarchickým spôsobom. Štruktúra dát stromu je jednou z najúčinnejších a najvyspelejších. Znázornené sú uzly spojené okrajmi.

Vlastnosti stromu: Každý strom má špecifický koreňový uzol. Každý uzol stromu môže byť krížený koreňovým uzlom. Nazýva sa koreň, pretože strom bol jediný koreň. Každé dieťa má iba jedného rodiča, ale rodič môže mať veľa detí.

Typy stromov v dátovej štruktúre

Nižšie sú uvedené druhy stromov v dátovej štruktúre:

1. Všeobecný strom

Ak nie je na hierarchiu stromu kladené žiadne obmedzenie, strom sa nazýva všeobecný strom. Každý uzol môže mať nekonečný počet detí v hlavnom strome. Strom je nadstavbou všetkých ostatných stromov.

2. Binárny strom

Binárny strom je druh stromu, v ktorom možno nájsť najviac dve deti pre každého rodiča. Deti sú známe ako ľavé a pravé dieťa. Toto je obľúbenejšie ako väčšina ostatných stromov. Keď sa v binárnom strome použijú určité obmedzenia a charakteristiky, použije sa tiež množstvo ďalších, ako je napríklad strom AVL, strom BST (strom binárneho vyhľadávania), strom RBT atď. Keď sa pohneme vpred, podrobne vysvetlíme všetky tieto štýly.

3. Binárny vyhľadávací strom

Binárny vyhľadávací strom (BST) je rozšírenie binárneho stromu s niekoľkými voliteľnými obmedzeniami. Ľavá podradená hodnota uzla by mala byť v BST menšia alebo rovná rodičovskej hodnote a správna podradená hodnota by mala byť vždy väčšia alebo rovnaká ako hodnota rodiča. Táto vlastnosť stromu binárneho vyhľadávania je ideálna pre operácie vyhľadávania, pretože v každom uzle môžeme presne určiť, či sa hodnota nachádza v ľavom alebo pravom podskupine. Preto je názov vyhľadávacieho stromu pomenovaný.

4. Strom AVL

Strom AVL je samovyrovnávací binárny vyhľadávací strom. V mene vynálezcov Adelson-Velshi a Landis sa uvádza názov AVL. Bol to prvý strom, ktorý sa dynamicky vyvážil. Vyrovnávací faktor je pre každý uzol v strome AVL pridelený na základe toho, či je strom vyrovnaný alebo nie. Výška uzla deti je najviac 1. AVL viniča. V strome AVL je správny vyvážený faktor 1, 0 a -1. Ak má strom nový uzol, bude sa otáčať, aby sa zabezpečilo vyváženie stromu. Potom sa otočí. Bežné operácie, ako napríklad prezeranie, vkladanie a odstraňovanie, trvajú O (log n) čas v strome AVL. Používa sa väčšinou pri práci s operáciami vyhľadávania.

5. Červeno-čierny strom

Ďalším typom automatického vyváženia je červeno-čierna farba. Červeno-čierny názov je daný, pretože červeno-čierny strom má na každom uzle buď červenú alebo čiernu podľa vlastností červeno-čierneho stromu. Zachováva rovnováhu lesa. Aj keď tento strom nie je úplne vyrovnaný strom, vyhľadávanie trvá iba O (log n). Keď sa nové uzly pridajú do červeno-čierneho stromu, uzly sa znova otočia, aby sa zachovali vlastnosti červeno-čierneho stromu.

6. N-ary strom

Maximálny počet detí v tomto type stromu, ktoré môžu mať uzol, je N. Binárny strom je dvojročný strom, ako najviac 2 deti v každom uzle binárneho stromu. Kompletný strom N-ary je strom, v ktorom sú deti uzla 0 alebo N.

Výhody stromu

Teraz pochopíme výhody stromu:

  • Strom sa odráža v dátových štrukturálnych prepojeniach.
  • Strom sa používa pre hierarchiu.
  • Ponúka efektívny postup vyhľadávania a vkladania.
  • Stromy sú flexibilné. To umožňuje premiestnenie podstromov s minimálnym úsilím.

Záver - Druhy stromov v dátovej štruktúre

Takže tu v tomto článku sme videli, čo je štruktúra stromov, aké sú rôzne druhy stromov v dátovej štruktúre a aké sú jej výhody. Dúfam, že ste získali predstavu o niektorých bežných stromoch v štruktúre údajov.

Odporúčané články

Toto je sprievodca typmi stromov v dátovej štruktúre. Tu diskutujeme o tom, čo sú stromy, 6 typov stromov v dátovej štruktúre, s výhodami. Viac informácií nájdete aj v ďalších súvisiacich článkoch -

  1. Dátový kanál AWS
  2. Oracle Data Warehousing
  3. Viacrozmerná databáza
  4. Otázky týkajúce sa rozhovoru s dátovou štruktúrou Java

Kategórie:

Veľké dáta