3 täpsemat andmestruktuuri, mida iga programmeerija peaks teadma

Avastate, et andmestruktuuride kasutamine on programmeerijana üsna tavaline nähtus, seega on teie edu jaoks ülioluline põhiliste andmestruktuuride (nt binaarpuud, virnad ja järjekorrad) valdamine.

Kuid kui soovite oma oskusi täiustada ja teistest eristuda, soovite tutvuda ka täiustatud andmestruktuuridega.

Täiustatud andmestruktuurid on andmeteaduse oluline komponent ning need aitavad ebatõhusalt haldada ja pakuvad salvestusruumi suurte andmehulkade jaoks. Tarkvarainsenerid ja andmeteadlased kasutavad algoritmide ja tarkvara kavandamiseks pidevalt täiustatud andmestruktuure.

Lugege edasi, kui arutame täiustatud andmestruktuure, millest iga arendaja peaks teadma.

1. Fibonacci hunnik

Kui olete andmestruktuuride õppimiseks juba mõnda aega pühendanud, peate olema tuttav binaarkuhjadega. Fibonacci kuhjad on üsna sarnased ja sellele järgneb min-hunnik või max-hunnik omadused. Fibonacci hunnikut võib pidada puude kogumiks, kus minimaalse või maksimaalse väärtuse sõlm on alati juurtes.

Kuhja täidab ka Fibonacci omadust nii, et sõlm n saab vähemalt F(n+2) sõlmed. Fibonacci hunnikus on iga sõlme juured omavahel ühendatud, tavaliselt ringikujulise topeltlingitud loendi kaudu. See võimaldab kustutada sõlme ja ühendada kaks loendit vaid O(1) ajaga.

Seotud: Juhend algajatele järjekordade ja prioriteetsete järjekordade mõistmiseks

Fibonacci kuhjad on palju paindlikumad kui kahend- ja binoomkuhjad, mistõttu on need kasulikud paljudes rakendustes. Neid kasutatakse Dijkstra algoritmis tavaliselt prioriteetsete järjekordadena, et parandada oluliselt algoritmi tööaega.

2. AVL puu

AVL (Adelson-Velsky ja Landis) puud on isetasakaaluvad binaarsed otsingupuud. Standardsed binaarsed otsingupuud võivad olla viltu ja nende ajaline keerukus on halvimal juhul O(n), mis muudab need reaalsete rakenduste jaoks ebaefektiivseks. Isebalansseerivad puud muudavad tasakaalustusomaduse rikkumisel automaatselt oma struktuuri.

AVL-puus sisaldab iga sõlm täiendavat atribuuti, mis sisaldab selle tasakaalustamistegurit. Tasakaalutegur on väärtus, mis saadakse vasaku alampuu kõrguse lahutamisel selle sõlme paremast alampuust. AVL-i puu isetasakaalustav omadus nõuab, et tasakaalutegur oleks alati -1, 0 või 1.

Kui isetasakaalustamise omadust (tasakaalutegurit) rikutakse, pöörab AVL-puu oma sõlmed tasakaaluteguri säilitamiseks. AVL-puu kasutab nelja peamist pööramist – paremale pööramine, vasakule pööramine, vasakule-paremale pööramine ja paremale-vasakule pööramine.

AVL-i puu isetasakaalustav omadus parandab selle halvimal juhul aja keerukust vaid O(logn)-ni, mis on binaarse otsingupuu jõudlusega võrreldes oluliselt tõhusam.

3.Punane-must puu

Punane-must puu on veel üks isetasakaaluv binaarne otsingupuu, mis kasutab oma tasakaalustava omadusena täiendavat bitti. Otsa nimetatakse tavaliselt punaseks või mustaks, sellest ka nimi Red-Black tree.

Iga punase-musta sõlm on kas punane või must, kuid juursõlm peab alati olema must. Kahte kõrvuti asetsevat punast sõlme ei saa olla ja kõik lehtede sõlmed peavad olema mustad. Neid reegleid kasutatakse puu isetasakaalustumisomaduste säilitamiseks.

Seotud: Algoritmid, mida iga programmeerija peaks teadma

Erinevalt kahendotsingu puudest on puna-mustade puude efektiivsus ligikaudu O(logn), mis muudab need palju tõhusamaks. Kuid AVL-puud on palju tasakaalustatumad tänu kindlale isetasakaaluva omadusele.

Täiustage oma andmestruktuure

Täiustatud andmestruktuuride tundmine võib tööintervjuudel oluliselt mõjutada ja võib olla tegur, mis teid konkurentsist eraldab. Muud täpsemad andmestruktuurid, mida peaksite uurima, hõlmavad n-puud, graafikuid ja disjoint komplekte.

Ideaalse andmestruktuuri tuvastamine antud stsenaariumi jaoks on osa sellest, mis teeb hea programmeerija suurepäraseks.

6 andmestruktuuri, mida iga programmeerija peaks teadma

Andmestruktuurid on tarkvaratehnika põhiosa. Siin on mõned olulised andmestruktuurid, mida iga programmeerija peaks teadma.

Loe edasi

Autori kohta