3 avancerede datastrukturer, som enhver programmør bør kende

Du vil opdage, at det er ret almindeligt at bruge datastrukturer som programmør, så det er afgørende for din succes at være dygtig til grundlæggende datastrukturer som binære træer, stakke og køer.

Men hvis du vil forbedre dine færdigheder og skille dig ud fra mængden, vil du også gerne blive fortrolig med avancerede datastrukturer.

Avancerede datastrukturer er en væsentlig komponent i datavidenskab, og de hjælper med at rydde op i ineffektiv styring og giver lagring til store datasæt. Softwareingeniører og dataforskere gør konstant brug af avancerede datastrukturer til at designe algoritmer og software.

Læs videre, mens vi diskuterer de avancerede datastrukturer, som enhver udvikler bør kende til.

1. Fibonacci-bunke

Hvis du allerede har brugt lidt tid på at lære datastrukturer, skal du være bekendt med binære heaps. Fibonacci-dynger er ret ens, og det følger min-bunke eller max-bunke ejendomme. Du kan tænke på en Fibonacci-bunke som en samling af træer, hvor minimum- eller maksimumværdiknuden altid er ved roden.

Heapen opfylder også Fibonacci-egenskaben, således at en node n vil have i det mindste F(n+2) noder. Inden for en Fibonacci-dynge er rødderne af hver node knyttet sammen, normalt gennem en cirkulær dobbeltforbundet liste. Dette gør det muligt at slette en node og sammenkæde to lister på kun O(1) tid.

Relaterede: En begyndervejledning til at forstå køer og prioriterede køer

Fibonacci-dynger er meget mere fleksible end binære og binomiale dynger, hvilket gør dem nyttige i en lang række applikationer. De bruges almindeligvis som prioritetskøer i Dijkstras algoritme for at forbedre algoritmens køretid betydeligt.

2. AVL træ

AVL (Adelson-Velsky og Landis) træer er selvbalancerende binære søgetræer. Standard binære søgetræer kan blive skæve og have en worst-case tidskompleksitet på O(n), hvilket gør dem ineffektive til applikationer i den virkelige verden. Selvbalancerende træer ændrer automatisk deres struktur, når balanceegenskaben krænkes.

I et AVL-træ indeholder hver node en ekstra attribut, der indeholder dens balanceringsfaktor. Balancefaktoren er den værdi, der opnås ved at trække højden af ​​det venstre undertræ fra det højre undertræ ved den node. Den selvbalancerende egenskab for AVL-træet kræver, at balancefaktoren altid er -1, 0 eller 1.

Hvis den selvbalancerende egenskab (balancefaktor) overtrædes, roterer AVL-træet sine noder for at bevare balancefaktoren. Et AVL-træ bruger fire hovedrotationer - højrerotation, venstredrejning, venstre-højre rotation og højre-venstre rotation.

Den selvbalancerende egenskab for et AVL-træ forbedrer dets worst-case tidskompleksitet til kun O(logn), hvilket er væsentligt mere effektivt sammenlignet med ydeevnen af ​​et binært søgetræ.

3. Rød-sort træ

Et rød-sort træ er et andet selvbalancerende binært søgetræ, der bruger en ekstra bit som sin selvbalancerende egenskab. Bittet omtales normalt som rødt eller sort, deraf navnet Rød-sort træ.

Hver knude i en rød-sort er enten rød eller sort, men rodknuden skal altid være sort. Der må ikke være to tilstødende røde noder, og alle bladknuder skal være sorte. Disse regler bruges til at bevare træets selvbalancerende egenskab.

Relaterede: Algoritmer, som enhver programmør bør kende

I modsætning til binære søgetræer har rød-sorte træer omtrentlig O(logn) effektivitet, hvilket gør dem langt mere effektive. AVL-træer er dog meget mere afbalancerede på grund af en definitiv selvbalancerende egenskab.

Forbedre dine datastrukturer

At kende avancerede datastrukturer kan gøre en stor forskel i jobsamtaler og kan være den faktor, der adskiller dig fra konkurrenterne. Andre avancerede datastrukturer, som du bør undersøge, inkluderer n-træer, grafer og disjoint sæt.

At identificere en ideel datastruktur for et givet scenarie er en del af det, der gør en god programmør fantastisk.

6 datastrukturer, som enhver programmør bør kende

Datastrukturer er en fast bestanddel i softwareudvikling. Her er nogle vigtige datastrukturer, som enhver programmør bør kende.

Læs Næste

Om forfatteren