En begynderguide til binære træer

Hvis du har taget et datastrukturkursus i din datalogi, eller er en autodidakt programmerer, er der stor sandsynlighed for, at du er stødt på udtrykket "Binære træer". Selvom de måske lyder lidt overvældende og komplekse, er konceptet med et binært træ ganske enkelt.

Læs videre, mens vi dissekerer binære træer, og hvorfor de er et nødvendigt kernekoncept for programmører.

Hvad er binære træer?

Binære træer er blandt en af ​​de første datastrukturer, som eleverne undervises i et datastrukturkursus. Et binært træ består af mange noder, og hver node i det binære træ indeholder to pointer, der angiver venstre og højre underordnede dataknudepunkter.

Den første knude i et binært træ kaldes "roden". Noder i det sidste niveau i et træ kaldes blade.

Hver node indeholder et dataelement og to nodepegere. Et tomt binært træ repræsenteres af en nullmarkør. Som du måske allerede har regnet ud, kan binære træer kun få to børn (deraf navnet).

Typer af binære træstrukturer

Der er flere forskellige binære træstrukturer afhængigt af den måde, knudepunkterne er placeret på. Et binært træ kaldes et fuldt binært træ, når hver knude i træet har enten nul eller to børn. I et perfekt binært træ har alle knuder to børn, og bladene er alle i samme dybde.

Relaterede: Bedste måder at lære at kode gratis på

Et komplet binært træ har noder udfyldt på hvert niveau, med undtagelse af det sidste niveau. I komplette binære træer er noder koncentreret på venstre side af roden. En anden fælles struktur er et afbalanceret binært træ; i denne struktur må højderne til højre og venstre undertræer højst variere med en. Det kræves også, at venstre og højre undertræer også skal være afbalanceret.

Det er vigtigt at bemærke, at højden af ​​det afbalancerede binære træ er O (logn), hvor n er antallet af noder i træet.

I nogle tilfælde, hvis hver node kun har et venstre eller højre barn, kan det binære træ blive et skævt binært træ. Det vil derefter opføre sig som en sammenkædet liste, sådanne træer kaldes også et degenereret træ.

Hvad er binære søgetræer?

Et binært søgetræ (BST) er i det væsentlige et ordnet binært træ med en særlig egenskab kendt som egenskaben "binært søgetræ". BST -egenskaben betyder, at noder med en nøgleværdi, der er mindre end roden, er placeret i venstre undertræ, og noder med en nøgleværdi, der er større end roden, er en del af det rigtige undertræ.

BST -egenskaben skal være sand for hver efterfølgende forældreknude i træet.

Binære søgetræer tilbyder hurtig indsættelse og opslag. Indsættelse, sletning og søgeoperationer har en værst tænkelig tidskompleksitet på O (n), der ligner en sammenkædet liste.

Fordele ved binære træer

Binære træer tilbyder mange fordele, hvorfor de fortsat er en meget nyttig datastruktur. De kan bruges til at vise de strukturelle relationer og hierarkier i et datasæt. Mere vigtigt er, at binære træer tillader effektiv søgning, sletning og indsættelse.

Det er også meget let at implementere og vedligeholde et binært træ. Et binært træ tilbyder programmerere fordelene ved et bestilt array og en sammenkædet liste; søgning i et binært træ er lige så hurtigt som i et sorteret array, og indsættelse eller sletning er lige så effektiv som i sammenkædede lister.

Binære træer er vigtige datastrukturer

Binære træer er en meget vigtig datastruktur, og det er afgørende, at programmører er trygge ved at anvende dem i deres programmer. Ofte stiller interviewere simple binære træproblemer såsom traversals, maksimal dybde, spejling osv.

Vi anbefaler stærkt at forstå det binære træ -koncept og kende typiske interviewproblemer.

TreeViz: En enkel måde at visualisere datastrukturer på

Læs Næste

Om forfatteren