3 avanserte datastrukturer enhver programmerer bør kjenne til

Du vil oppdage at bruk av datastrukturer er en ganske vanlig forekomst som programmerer, så det å være dyktig med grunnleggende datastrukturer som binære trær, stabler og køer er avgjørende for din suksess.

Men hvis du ønsker å forbedre ferdighetene dine og skille deg ut fra mengden, vil du også ønske å bli kjent med avanserte datastrukturer.

Avanserte datastrukturer er en viktig komponent i datavitenskap, og de hjelper til med å rydde opp i ineffektiv administrasjon og gir lagring for store sett med data. Programvareingeniører og dataforskere bruker stadig avanserte datastrukturer for å designe algoritmer og programvare.

Les videre mens vi diskuterer de avanserte datastrukturene enhver utviklere bør vite om.

1. Fibonacci-haug

Hvis du allerede har brukt litt tid på å lære datastrukturer, må du være kjent med binære hauger. Fibonacci-hauger er ganske like, og det følger min-haug eller maks-haug egenskaper. Du kan tenke på en Fibonacci-haug som en samling trær der minimums- eller maksimumsverdinoden alltid er ved roten.

Heapen oppfyller også Fibonacci-egenskapen slik at en node n vil ha minst F(n+2) noder. Innenfor en Fibonacci-haug er røttene til hver node koblet sammen, vanligvis gjennom en sirkulær dobbeltlenket liste. Dette gjør det mulig å slette en node og sette sammen to lister på kun O(1) tid.

I slekt: En nybegynnerveiledning for å forstå køer og prioriterte køer

Fibonacci-hauger er mye mer fleksible enn binære og binomiale hauger, noe som gjør dem nyttige i en lang rekke bruksområder. De brukes ofte som prioriterte køer i Dijkstras algoritme for å forbedre algoritmens kjøretid betraktelig.

2. AVL-tre

AVL (Adelson-Velsky og Landis) trær er selvbalanserende binære søketrær. Standard binære søketrær kan bli skjeve og ha en tidskompleksitet i verste fall på O(n), noe som gjør dem ineffektive for virkelige applikasjoner. Selvbalanserende trær endrer automatisk strukturen når balanseegenskapen brytes.

I et AVL-tre inneholder hver node et ekstra attributt som inneholder balanseringsfaktoren. Balansefaktoren er verdien som oppnås ved å trekke fra høyden til venstre deltre fra høyre deltre ved den noden. Den selvbalanserende egenskapen til AVL-treet krever at balansefaktoren alltid er -1, 0 eller 1.

Hvis den selvbalanserende egenskapen (balansefaktor) brytes, roterer AVL-treet sine noder for å bevare balansefaktoren. Et AVL-tre bruker fire hovedrotasjoner – høyrerotering, venstrerotering, venstre-høyrerotering og høyre-venstrerotering.

Den selvbalanserende egenskapen til et AVL-tre forbedrer dets verste tidskompleksitet til bare O(logg), som er betydelig mer effektivt sammenlignet med ytelsen til et binært søketre.

3. Rød-svart tre

Et rød-svart tre er et annet selvbalanserende binært søketre som bruker en ekstra bit som sin selvbalanserende egenskap. Biten blir vanligvis referert til som rød eller svart, derav navnet Rød-Sort tre.

Hver node i en rød-svart er enten rød eller svart, men rotnoden må alltid være svart. Det kan ikke være to tilstøtende røde noder, og alle bladnoder må være svarte. Disse reglene brukes for å bevare den selvbalanserende egenskapen til treet.

I slekt: Algoritmer som enhver programmerer bør kjenne til

I motsetning til binære søketrær har rød-svarte trær omtrentlig O(logn) effektivitet, noe som gjør dem langt mer effektive. AVL-trær er imidlertid mye mer balanserte på grunn av en definitiv selvbalanserende egenskap.

Forbedre datastrukturene dine

Å kjenne avanserte datastrukturer kan utgjøre en stor forskjell i jobbintervjuer og kan være faktoren som skiller deg fra konkurrentene. Andre avanserte datastrukturer du bør se nærmere på inkluderer n-trær, grafer og usammenhengende sett.

Å identifisere en ideell datastruktur for et gitt scenario er en del av det som gjør en god programmerer stor.

6 datastrukturer enhver programmerer bør kjenne til

Datastrukturer er en stift i programvareutvikling. Her er noen viktige datastrukturer enhver programmerer bør kjenne til.

Les Neste

Om forfatteren