3 pokročilé dátové štruktúry, ktoré by mal poznať každý programátor

Zistíte, že používanie dátových štruktúr je ako programátor celkom bežný jav, takže znalosť základných dátových štruktúr, ako sú binárne stromy, zásobníky a fronty, je životne dôležitá pre váš úspech.

Ale ak chcete zlepšiť svoje zručnosti a vyčnievať z davu, budete sa chcieť zoznámiť aj s pokročilými dátovými štruktúrami.

Pokročilé dátové štruktúry sú základnou súčasťou vedy o údajoch a pomáhajú vyčistiť neefektívne riadenie a poskytujú úložisko pre veľké súbory údajov. Softwaroví inžinieri a dátoví vedci neustále využívajú pokročilé dátové štruktúry na navrhovanie algoritmov a softvéru.

Čítajte ďalej, keď diskutujeme o pokročilých dátových štruktúrach, o ktorých by mal vedieť každý vývojár.

1. Fibonacciho halda

Ak ste už venovali nejaký čas učeniu dátových štruktúr, musíte byť oboznámení s binárnymi haldami. Fibonacciho haldy sú dosť podobné a z toho vyplýva min-hromada alebo max-hromada vlastnosti. Fibonacciho haldu si môžete predstaviť ako zbierku stromov, kde uzol s minimálnou alebo maximálnou hodnotou je vždy v koreni.

Halda tiež spĺňa Fibonacciho vlastnosť tak, že uzol n bude mať aspoň F(n+2) uzly. V rámci Fibonacciho haldy sú korene každého uzla navzájom prepojené, zvyčajne prostredníctvom kruhového dvojito prepojeného zoznamu. To umožňuje vymazať uzol a zreťaziť dva zoznamy len v čase O(1).

Súvisiace: Príručka pre začiatočníkov k pochopeniu frontov a prioritných frontov

Fibonacciho haldy sú oveľa flexibilnejšie ako binárne a binomické haldy, vďaka čomu sú užitočné v širokej škále aplikácií. Bežne sa používajú ako prioritné fronty v algoritme Dijkstra, aby sa výrazne zlepšila doba chodu algoritmu.

2. AVL strom

Stromy AVL (Adelson-Velsky a Landis) sú samovyvažujúce binárne vyhľadávacie stromy. Stromy štandardného binárneho vyhľadávania môžu byť skreslené a majú v najhoršom prípade časovú zložitosť O(n), čo ich robí neefektívnymi pre aplikácie v reálnom svete. Samovyvažovacie stromy automaticky zmenia svoju štruktúru, keď dôjde k narušeniu vyrovnávacej vlastnosti.

V strome AVL každý uzol obsahuje ďalší atribút, ktorý obsahuje jeho vyvažovací faktor. Faktor rovnováhy je hodnota získaná odčítaním výšky ľavého podstromu od pravého podstromu v danom uzle. Vlastnosť samovyvažovania stromu AVL vyžaduje, aby faktor vyváženia bol vždy -1, 0 alebo 1.

Ak dôjde k porušeniu vlastnosti samovyvažovania (faktor rovnováhy), strom AVL otočí svoje uzly, aby zachoval faktor rovnováhy. Strom AVL používa štyri hlavné rotácie – rotáciu doprava, rotáciu doľava, rotáciu zľava doprava a rotáciu sprava doľava.

Vlastnosť samovyvažovania AVL stromu zlepšuje jeho časovú zložitosť v najhoršom prípade len na O(logn), čo je výrazne efektívnejšie v porovnaní s výkonom binárneho vyhľadávacieho stromu.

3. Červeno-čierny strom

Červeno-čierny strom je ďalší samovyvažovací binárny vyhľadávací strom, ktorý používa extra bit ako svoju samovyvažovaciu vlastnosť. Bit sa zvyčajne označuje ako červený alebo čierny, odtiaľ pochádza aj názov Červeno-čierny strom.

Každý uzol v červeno-čiernom je buď červený alebo čierny, ale koreňový uzol musí byť vždy čierny. Nemôžu byť dva susediace červené uzly a všetky listové uzly musia byť čierne. Tieto pravidlá sa používajú na zachovanie samovyvažovacej vlastnosti stromu.

Súvisiace: Algoritmy, ktoré by mal poznať každý programátor

Na rozdiel od stromov binárneho vyhľadávania majú červeno-čierne stromy účinnosť približne O (logn), vďaka čomu sú oveľa efektívnejšie. AVL stromy sú však oveľa vyváženejšie vďaka definitívnej samovyvažovacej vlastnosti.

Zlepšite svoje dátové štruktúry

Znalosť pokročilých dátových štruktúr môže znamenať veľký rozdiel pri pracovných pohovoroch a môže byť faktorom, ktorý vás oddeľuje od konkurencie. Medzi ďalšie pokročilé dátové štruktúry, ktoré by ste si mali pozrieť, patria n-stromy, grafy a nesúvislé množiny.

Identifikácia ideálnej dátovej štruktúry pre daný scenár je súčasťou toho, čo robí dobrého programátora skvelým.

6 dátových štruktúr, ktoré by mal poznať každý programátor

Dátové štruktúry sú základom softvérového inžinierstva. Tu je niekoľko dôležitých dátových štruktúr, ktoré by mal poznať každý programátor.

Prečítajte si ďalej

O autorovi