Hvordan man ikke bliver stampet af træer

Vend det træ på hovedet!

Så snart lyspæren i datastrukturen slukker i dit hoved, er det virkelig svært at ikke se datastrukturer, på hvilken måde du ser ud! Eller ... måske er det bare mig.

For et par uger siden opdagede jeg glæden ved sammenkoblede lister og de mange forskellige abstrakte datatyper, som vi kan opbygge ved at bruge dem! Når jeg indså, at disse enkle datastrukturer faktisk var under overfladen af ​​så mange ting, som jeg brugte i mit arbejde og liv hver eneste dag, blev jeg slags blæst væk. Men som det viser sig, var det bare toppen af ​​isbjerget af datastrukturer! Fordi det selvfølgelig er. Det er trods alt computervidenskab, hvor problemer kan løses på så mange forskellige måder! Og det samme gælder data, der kan organiseres på forskellige måder.

Indtil videre har vi mest behandlet kun en type datastruktur. Men i dag vil vi blive lidt skøre og ryste vores data ude af drift! Det skyldes, at vi omsider vil dykke ned i ikke-lineære datastrukturer, der starter med min personlige favorit: træer!

Dyr en hvilken som helst gren du ønsker!

Du kan huske, at der er mange forskellige måder at kategorisere datastrukturer på. En af de mere brede kategorier for, hvordan vi kan gemme vores data, er, om vores data er lineære eller ikke - det vil sige, om der er en rækkefølge og en rækkefølge til, hvordan vores data konstrueres og krydses. I lineære datastrukturer - såsom arrays eller sammenkoblede lister - ordnes dataene, og den rækkefølge betyder noget; den måde, du krydser en lineær datastruktur på, er direkte relateret til dens rækkefølge, fordi elementerne i en lineær datastruktur kun kan krydses sekventielt.

Lineære datastrukturer i naturen

Men som vi ved nu, er der også ikke-lineære datastrukturer! Jo mere jeg har læst og lært om disse, jo mere seje ser de ud. Men de kan også være lidt vanskelige og uhåndterlige, hvorfor det kan være meget nyttigt at have et godt greb om lineære datastrukturer først, bare så vi kan forstå den grundlæggende forskel mellem dem fra start.

I ikke-lineære datastrukturer følger dataene ikke rigtig en rækkefølge - i det mindste ikke en åbenlyst numerisk ordning, som med arrays eller sammenkædede lister. Og fordi dataene ikke nødvendigvis skal arrangeres i en bestemt rækkefølge, er det let (og faktisk temmelig almindeligt) at krydse en ikke-lineær datastruktur på en ikke-sekventiel måde.

En af de vigtige typer ikke-lineære datastrukturer er et træ. Og hvis vi ønsker at forstå træer, og hvordan vi kan tale om dem, er vi nødt til at være i stand til at identificere dele af et træ! Selvom de ser meget forskellige ud fra de strukturer, vi har behandlet indtil videre, består de virkelig af de samme ting.

Træer - ligesom linkede lister - består af noder og links.

Alle træer, uanset om de er egetræer, ahorn eller ginkoer, begynder alle at spire med et solidt sæt rødder. I trædatastrukturer skal du også altid have en rod, selvom du ikke har noget andet. Faktisk, hvis vi bare havde en rod, ville vi have en enkelt knude. Men her bliver det interessant: en rodnode kan have links til flere andre noder. Og lige her er den grundlæggende forskel mellem de lineære strukturer, vi har set så langt, og de træer, vi lærer om nu. Én knude kan oprette forbindelse til mange andre, hvilket betyder, at træer kan vokse i forskellige former og måder.

Identificering af dele af en trædatastruktur

Her er nogle gode vilkår at vide, når det kommer til at tale om træer:

  • Rot: træets øverste knude, der aldrig har nogen forbindelser eller kanter, der forbinder til det
  • Link / kant: den henvisning, som en overordnet knude indeholder, der fortæller den, hvad dens underordnede knude er
  • Underordnet: enhver knude, der har en overordnet knude, der linker til den
  • Overordnet: enhver knude, der har en henvisning eller et link til en anden knude
  • Søskende: enhver gruppe af noder, der er børn af den samme knude
  • Internt: enhver knude, der har en barneknudepunkt (stort set alle overordnede knudepunkter)
  • Blad: enhver knude, der ikke har et barneknudepunkt i træet

Hvis disse udtryk overhovedet føles overvældende, finder jeg det nyttigt at tænke på trædatastrukturer som et slægtstræ eller endda en virksomhedsstige. Dataene er altid hierarkiske. Du har nogen (en rodnode) øverst, der delegerer til nogle andre noder (overordnede noder), som kan eller kan have en anden, der rapporterer til dem (underordnede noder). Eller så har du en enorm familie med forældreknudder, børneknuder, som alle fører op til en forfædres rodnode.

Lige så længe du kan huske, at dataene er hierarkiske, skal jargon forhåbentlig være lidt mindre bekymrende at tænke på.

Tal din (træ) sandhed

Uanset hvordan et træ ser ud, hvor mange grene eller blade det har, eller hvor stort det vokser, er der nogle universelle "træ sandheder", der holder sig selv for at være selvindlysende.

Jeg finder ud af, at disse er meget lettere at forstå, når vi visualiserer dem, så vi vil læne os på nogle eksempler her. Lad os se på dette træ, vi har nedenfor. Det har 10 noder i alt, inklusive rodnoden.

Træ-sandheder: et træ vil altid have et mindre link end det samlede antal knudepunkter

Den interessante sandhed om dette træ er, at det har 10 noder, men 9 links eller kanter. Der er et forhold her, der gælder uanset antallet af noder, og der er en let tommelfingerregel, vi kan huske:

Hvis et træ har n-noder, vil det altid have et mindre antal kanter (n-1).

Og hvis vi ser på træet, begynder det at blive klart, hvorfor det er. En rodnode er en knude, der aldrig kan have nogen forældre. Derfor kan det aldrig have noget, der refererer til det. Hvis hver knude skal have en anden knude, der refererer til den via et link / kant (undtagen rodnoden), kan vi altid være sikre på, at vores træ har n-1-links, når n er det samlede antal knudepunkter i træet. Hvor cool (og kraftfuld!) Er det ikke, at vi kan kende disse oplysninger så let uden at skulle krydse træet ?!

Men vent - her er en anden sandhed, der muligvis er endnu køligere: træer indeholder faktisk træer inden i dem!

Træ-sandheder: træer er rekursive datastrukturer

Træer er rekursive datastrukturer, fordi et træ normalt består af mindre træer - ofte benævnt undertræer - inde i det. Barnet til den ene knude i et træ kunne meget vel være forælderen til et andet træ (hvilket gør det til rodnoden i en undertræ). Dette kan være virkelig interessant, når det kommer til at skrive algoritmer til at krydse eller søge gennem et træ, da indlejring af træer undertiden kan føre os til at skrive rekursive søgealgoritmer.

Men vi kommer ikke ind i træskifte endnu. I stedet vil vi se på noget, der er vigtigere at forstå først: de forskellige måder, vi kan klassificere vores træer på, som vil komme godt med på vejen.

Hvor højt går dit træ?

Da træer kan komme i så mange forskellige former og størrelser, er det super vigtigt at være i stand til at identificere og forstå, hvilken type træ du har at gøre med, og hvordan disse data ser ud. Med henblik herpå er der to egenskaber, der er de vigtigste at tale om, når det kommer til hvilken type træ du har at gøre med, og hvor dine data bor i det træ.

For det meste er de to egenskaber, som vi vil være mest optaget af, enten dybden af ​​en knude eller højden af ​​en knude.

En enkel måde at tænke på dybden af ​​en knude er ved at besvare spørgsmålet: hvor langt væk er noden fra træets rod?

Men hvordan ved vi, hvad langt er i dette tilfælde? Nå, selvom vi ikke lige har fået ind i alle kompleksiteterne ved trævandring, er der kun én måde at krydse eller søge gennem et træ ved at lave en sti og følge kanterne / linkene fra rodnoden nede. Så vi kunne bestemme, hvor langt en knude er fra rodnoden ved at tælle antallet af links, det tager for at nå denne knude fra rodnoden.

I det her viste eksempel er dybden af ​​den lyserøde knude 2, fordi der er nøjagtigt 2 links, der forbinder rodnoden med den lyserøde knude. Dybden af ​​den lilla knude er imidlertid 3, fordi den tager 3 links til at krydse ned fra rodnoden til den lilla knude.

Dybden og højden af ​​en knude på en trædatastruktur

Nu hvor vi ved, hvordan dybden fungerer, er den anden egenskab lidt lettere. Højden på en knude kan forenkles ved at stille spørgsmålet: hvor langt er denne knude fra dens længst væk blad? (Husk: vi vender træer på hovedet i den vilde verden af ​​computere, hvilket er grunden til, at højden bestemmes på denne måde!)

Så vi kan finde en knudepunktshøjde ved at finde det længste barneblad og tælle stien til links, det tager for at nå den. I eksemplet er højden på den orange knude 3, fordi dets fjerneste barneblade (der er faktisk tre af dem!) Er tre led væk fra den orange knude. Bonuspoint, hvis du finder ud af, hvor dybden af ​​den orange knude er!

Det kølige ved især højdeegenskaben er, at rodnodens højde automatisk er højden på hele træet. Grundlæggende betyder det, at når vi først finder den bladknude, der er længst væk fra roden, ved vi nu den længste mulige sti i træet, som fortæller os, hvor høj den faktisk er!

Årsagen til, at dybde og højde er så vigtig, er fordi de fortæller os meget om, hvordan et træ ser ud, lige fra flagermus. Og tingene med træer (som jeg er sikker på nu ved vi alle sammen) er, at de alle kan se anderledes ud. Et hurtigt eksempel på dette er afbalancerede træer kontra ubalancerede træer.

Balancerede træer kontra ubalancerede træer

Et træ anses for at være afbalanceret, hvis to søskens undertræer ikke adskiller sig i højden med mere end et niveau. Men hvis to søskens undertræer adskiller sig markant i højden (og har mere end et niveau af forskellingsdybde), er træet ubalanceret.

Afbalancerede træer dukker op, når vi taler om træoperationer og især gennemgang. Ideen bag dette er, at hvis vi kan krydse et træ og skære ned på halvdelen af ​​antallet af operationer, har vi en bedre datastruktur. I et ubalanceret træ er dette bestemt ikke tilfældet, fordi et undertræ kan være markant større end søskens undertræ. Mange af de operationelle effektivitetsproblemer, som afbalancerede træer løser, kaldes faktisk binære træer - men meget mere om det næste uge!

Afgrødning af træerødder

For virkelig at værdsætte et træs kraft må vi se på dem i sammenhæng med deres anvendelse. Med andre ord: de er sandsynligvis ikke så seje, før du ser dem i naturen!

Et enkelt eksempel ligger inden for objektorienterede sprog: hovedobjektet er rodnoden, mens klasser, der arver det, er børn af hovedklassen. Dette giver mere mening, når du tænker over det; det faktum, at det ofte kaldes et "klassehierarki", egner sig pænt til den hierarkiske trædatastruktur.

Den mest indlysende (som måske ikke har været indlysende indtil nu!) Er filstrukturen i et projekt - eller endda filsystemet på din computer! Hvis vi tænker over det, er alle de vigtige stykker allerede der: en rodkatalog, med underordnede noder, der kan være deres egne underkataloger, eller blade af træet, der slutter med bare en simpel fil. Det hele er egentlig kun en hierarkisk trædatastruktur!

Og at tænke, vi havde alle solet os i skyggen af ​​træet så længe og havde ingen idé om det.

Ressourcer

Hvis du er en træknus eller en træentusiast, eller bare vil lære lidt mere, så tjek disse nyttige links!

  1. Datakonstruktioner: Introduktion til træer, mycodeschool
  2. Datakonstruktioner: Træer, HackerRank
  3. Træer, professor Jonathan Cohen
  4. Trædatasstrukturer, professor David Schmidt
  5. Balancing Trees, professor R. Clayton