Alt hvad du har brug for at vide om trædatastrukturer

Træer er så smukke. En tegning, jeg lavede da jeg var en ung dreng.

Når du først lærer at kode, er det almindeligt at lære arrays som den "vigtigste datastruktur."

Til sidst lærer du også hashborde. Hvis du forfølger en Computer Science grad, skal du tage en klasse om datastruktur. Du lærer også om linkede lister, køer og stabler. Disse datastrukturer kaldes "lineære" datastrukturer, fordi de alle har en logisk start og en logisk ende.

Når vi begynder at lære om træer og grafer, kan det blive virkelig forvirrende. Vi lagrer ikke data på en lineær måde. Begge datastrukturer gemmer data på en bestemt måde.

Dette indlæg er til at hjælpe dig med bedre at forstå trædatastrukturen og til at afklare enhver forvirring, du måtte have om det.

I denne artikel lærer vi:

  • Hvad er et træ
  • Eksempler på træer
  • Dens terminologi og hvordan det fungerer
  • Sådan implementeres træstrukturer i kode.

Lad os starte denne læringsrejse. :)

Definition

Når man starter programmeringen, er det almindeligt at forstå de lineære datastrukturer bedre end datastrukturer som træer og grafer.

Træer er velkendt som en ikke-lineær datastruktur. De gemmer ikke data på en lineær måde. De organiserer data hierarkisk.

Lad os dykke ned i eksempler i det virkelige liv!

Hvad mener jeg, når jeg siger på en hierarkisk måde?

Forestil dig et slægtstræ med forhold fra alle generationer: bedsteforældre, forældre, børn, søskende osv. Vi organiserer ofte slægtstræer hierarkisk.

Mit stamtræ

Ovenstående tegning er er mit slægtstræ. Tossico, Akikazu, Hitomi og Takemi er mine bedsteforældre.

Toshiaki og Juliana er mine forældre.

TK, Yuji, Bruno og Kaio er mine forældres børn (mig og mine brødre).

En organisations struktur er et andet eksempel på et hierarki.

En virksomheds struktur er et eksempel på et hierarki

I HTML fungerer Document Object Model (DOM) som et træ.

Dokumentobjektmodel (DOM)

HTML-mærket indeholder andre tags. Vi har et hovedmærke og et kropsmærke. Disse tags indeholder specifikke elementer. Hovedmærket har meta- og titelmærker. Body-mærket har elementer, der vises i brugergrænsefladen, for eksempel h1, a, li osv.

En teknisk definition

Et træ er en samling enheder kaldet knudepunkter. Knudepunkter er forbundet ved kanter. Hver knude indeholder en værdi eller data, og den har muligvis ikke en underordnet knude.

Træens første knude kaldes roden. Hvis denne rodnode er forbundet med en anden knude, er roden derefter en overordnet knude, og den tilsluttede knude er et barn.

Alle træknudepunkter er forbundet med links, der kaldes kanter. Det er en vigtig del af træer, fordi det styrer forholdet mellem knudepunkter.

Blade er de sidste knudepunkter på et træ. De er knudepunkter uden børn. Som rigtige træer har vi rod, grene og endelig bladene.

Andre vigtige begreber at forstå er højde og dybde.

Højden på et træ er længden af ​​den længste sti til et blad.

Dybden af ​​en knude er længden af ​​stien til dens rod.

Terminologisammendrag

  • Roden er træets øverste knude
  • Edge er forbindelsen mellem to noder
  • Barn er en knude, der har en overordnet knude
  • Forældre er en knude, der har en kant til en barneknudepunkt
  • Blad er en knude, der ikke har et barneknudepunkt i træet
  • Højde er længden af ​​den længste sti til et blad
  • Dybde er længden af ​​stien til dens rod

Binære træer

Nu diskuterer vi en bestemt type træ. Vi kalder det thebinary tree.

"I datalogi er et binært træ en trædatasstruktur, hvor hver knude har højst to børn, der benævnes det venstre barn og det højre barn." - Wikipedia

Så lad os se på et eksempel på et binært træ.

Lad os kode et binært træ

Den første ting, vi skal huske på, når vi implementerer et binært træ, er, at det er en samling af noder. Hver knude har tre attributter: værdi, venstre_barn og højre_barn.

Hvordan implementerer vi et simpelt binært træ, der initialiseres med disse tre egenskaber?

Lad os se.

Her er det. Vores binære træklasse.

Når vi instantierer et objekt, overfører vi værdien (nodens data) som en parameter. Se på venstre_barnet og det højre_børn. Begge er indstillet til Ingen.

Hvorfor?

For når vi opretter vores node, har den ingen børn. Vi har bare nodedataene.

Lad os teste det:

Det er det.

Vi kan videregive strengen 'a' som værdien til vores Binary Tree-knude. Hvis vi udskriver værdien, venstre_barn og højrebørn, kan vi se værdierne.

Lad os gå til indsættelsesdelen. Hvad skal vi gøre her?

Vi implementerer en metode til at indsætte en ny knude til højre og til venstre.

Her er reglerne:

  • Hvis den nuværende knude ikke har et venstre barn, opretter vi bare en ny nodeanvisning og indstil den til den aktuelle nodes venstre_barn.
  • Hvis det har det venstre barn, opretter vi en ny knude og sætter den i det aktuelle venstre barns sted. Tildel denne venstre knude til den nye knude.

Lad os trække det ud. :)

Her er koden:

Igen, hvis den nuværende knude ikke har et venstre barn, opretter vi bare en ny knude og indstiller den til den aktuelle knudes venstre_barn. Ellers opretter vi en ny knude og sætter den på det aktuelle venstre barns sted. Tildel denne venstre knude til den nye knude.

Og vi gør den samme ting for at indsætte en ret børneknudepunkt.

Færdig. :)

Men ikke helt. Vi er stadig nødt til at teste det.

Lad os opbygge følgende trin:

For at opsummere illustrationen af ​​dette træ:

  • en knude vil være roden til vores binære træ
  • et venstre barn er b knude
  • et ret barn er c-knude
  • b højre barn er d node (b node har ikke et venstre barn)
  • c venstre barn er en knude
  • c højre barn er f node
  • både e- og f-noder har ikke børn

Så her er koden for træet:

Indsættelse er gjort.

Nu skal vi tænke over træstræning.

Vi har to muligheder her: Dybde-første søgning (DFS) og bredde-første søgning (BFS).

  • DFS “er en algoritme til at krydse eller søge trædatastruktur. Man starter ved roden og udforsker så vidt muligt langs hver gren inden backtracking. ”- Wikipedia
  • BFS “er en algoritme til at krydse eller søge trædatastruktur. Det starter ved træroden og udforsker naboens knudepunkter først, før det går til det næste niveau naboer. ”- Wikipedia

Så lad os dykke ned i hver trætraversaltype.

Dybde-første søgning (DFS)

DFS udforsker en sti hele vejen til et blad før backtracking og udforsker en anden sti. Lad os se på et eksempel med denne type gennemgang.

Resultatet for denne algoritme vil være 1-2–3–4–5–6–7.

Hvorfor?

Lad os nedbryde det.

  1. Start ved roden (1). Udskriv det.

2. Gå til det venstre barn (2). Udskriv det.

3. Gå derefter til det venstre barn (3). Udskriv det. (Denne knude har ingen børn)

4. Backtrack og gå det rigtige barn (4). Udskriv det. (Denne knude har ingen børn)

5. Backtrack til rodnoden og gå til det rigtige barn (5). Udskriv det.

6. Gå til det venstre barn (6). Udskriv det. (Denne knude har ingen børn)

7. Backtrack og gå til det rigtige barn (7). Udskriv det. (Denne knude har ingen børn)

8. Udført.

Når vi går dybt ind i blade og bagspor, kaldes dette DFS-algoritme.

Nu hvor vi er bekendt med denne gennemgående algoritme, vil vi diskutere typer af DFS: forudbestilling, ordre og postordre.

Forudbestille

Dette er nøjagtigt, hvad vi gjorde i ovenstående eksempel.

  1. Udskriv nodenes værdi.
  2. Gå til det venstre barn, og udskriv det. Dette er hvis, og kun hvis, det har et venstre barn.
  3. Gå til det rigtige barn, og udskriv det. Dette er hvis, og kun hvis, det har et rigtigt barn.

In-order

Resultatet af ordre-algoritmen til dette træeksempel er 3–2–4–1–6–5–7.

Venstre først, midterste sekund og højre sidst.

Lad os nu kode det.

  1. Gå til det venstre barn, og udskriv det. Dette er hvis, og kun hvis, det har et venstre barn.
  2. Udskriv nodens værdi
  3. Gå til det rigtige barn, og udskriv det. Dette er hvis, og kun hvis, det har et rigtigt barn.

Post-ordre

Resultatet af postordre-algoritmen for dette træeksempel er 3–4–2–6–7–5–1.

Venstre først, højre sekund og midterste sidst.

Lad os kode dette.

  1. Gå til det venstre barn, og udskriv det. Dette er hvis, og kun hvis, det har et venstre barn.
  2. Gå til det rigtige barn, og udskriv det. Dette er hvis, og kun hvis, det har et rigtigt barn.
  3. Udskriv nodens værdi

Breadth-First Search (BFS)

BFS-algoritme gennemgår træet niveau efter niveau og dybde efter dybde.

Her er et eksempel, der hjælper med at forklare denne algoritme bedre:

Så vi krydser niveau for niveau. I dette eksempel er resultatet 1–2–5–3–4–6–7.

  • Niveau / dybde 0: kun knude med værdi 1
  • Niveau / dybde 1: knudepunkter med værdier 2 og 5
  • Niveau / dybde 2: knudepunkter med værdierne 3, 4, 6 og 7

Lad os nu kode det.

For at implementere en BFS-algoritme bruger vi kødatastrukturen til at hjælpe.

Hvordan virker det?

Her er forklaringen.

  1. Tilføj først rodnoden i køen med put-metoden.
  2. Itererer, mens køen ikke er tom.
  3. Hent den første knude i køen, og udskriv derefter dens værdi.
  4. Tilføj både venstre og højre børn i køen (hvis den nuværende knude har børn).
  5. Færdig. Vi udskriver værdien af ​​hver knude niveau for niveau med vores køhelper.

Binært søgetræ

"Et binært søgetræ kaldes undertiden ordnet eller sorteret binære træer, og det holder dets værdier i sorteret rækkefølge, så opslag og andre operationer kan bruge princippet om binær søgning" - Wikipedia

En vigtig egenskab ved et binært søgetræ er, at værdien af ​​et binært søgetræ er en værdi, der er større end værdien af ​​afkommet til dets venstre barn, men mindre end værdien af ​​afkomet til dets højre barn. ”

Her er en oversigt over ovenstående illustration:

  • A er omvendt. Undertråden 7–5–8–6 skal være på højre side, og undertråden 2–1–3 skal være til venstre.
  • B er den eneste korrekte mulighed. Det tilfredsstiller ejendommen Binary Search Tree.
  • C har et problem: knuden med værdien 4. Den skal være på venstre side af roden, fordi den er mindre end 5.

Lad os kode et binært søgetræ!

Nu er det tid til at kode!

Hvad ser vi her? Vi vil indsætte nye noder, søge efter en værdi, slette noder og træets balance.

Lad os begynde.

Indsættelse: tilføjelse af nye noder til vores træ

Forestil dig, at vi har et tomt træ, og vi vil tilføje nye noder med følgende værdier i denne rækkefølge: 50, 76, 21, 4, 32, 100, 64, 52.

Den første ting, vi har brug for at vide, er, om 50 er roden til vores træ.

Vi kan nu begynde at indsætte node efter knude.

  • 76 er større end 50, så indsæt 76 på højre side.
  • 21 er mindre end 50, så indsæt 21 på venstre side.
  • 4 er mindre end 50. Knude med værdi 50 har et venstre barn 21. Da 4 er mindre end 21, skal du indsætte det på venstre side af denne knude.
  • 32 er mindre end 50. Knude med værdi 50 har et venstre barn 21. Da 32 er større end 21, indsættes 32 på højre side af denne knude.
  • 100 er større end 50. Knude med værdi 50 har et ret barn 76. Da 100 er større end 76, indsættes 100 på højre side af denne knude.
  • 64 er større end 50. Knude med værdi 50 har et højre barn 76. Da 64 er mindre end 76, indsættes 64 på venstre side af denne knude.
  • 52 er større end 50. Knude med værdi 50 har et højre barn 76. Da 52 er mindre end 76, har knude med værdi 76 et venstre barn 64. 52 er mindre end 64, så indsæt 54 på venstre side af denne knude.

Bemærker du et mønster her?

Lad os nedbryde det.

  1. Er den nye knudeværdi større eller mindre end den nuværende knude?
  2. Hvis værdien af ​​den nye knude er større end den nuværende knude, skal du gå til højre undertrin. Hvis den nuværende knude ikke har et rigtigt barn, skal du indsætte det der, ellers backtrack til trin # 1.
  3. Hvis værdien af ​​den nye knude er mindre end den aktuelle knude, skal du gå til venstre undertrin. Hvis den nuværende knude ikke har et venstre barn, skal du indsætte det der, ellers backtrack til trin # 1.
  4. Vi behandlede ikke specielle sager her. Når værdien af ​​en ny knude er lig med den aktuelle værdi af knuden, skal du bruge regelnummer 3. Overvej at indsætte lige værdier til venstre side af undertråden.

Lad os nu kode det.

Det virker meget enkelt.

Den kraftige del af denne algoritme er rekursionsdelen, der er på linje 9 og linje 13. Begge linjer med kode kalder metoden insert_node, og bruger den til henholdsvis sine venstre og højre børn. Linje 11 og 15 er dem, der gør indsættelsen for hvert barn.

Lad os søge efter nodeværdien ... Eller ikke ...

Den algoritme, som vi skal bygge nu, handler om at udføre søgninger. For en given værdi (heltalnummer) siger vi, om vores Binary Search Tree har eller ikke har denne værdi.

Et vigtigt element at bemærke er, hvordan vi definerede træindføringsalgoritmen. Først har vi vores rodnode. Alle de venstre undertrænoder har mindre værdier end rodnoden. Og alle de rigtige undernetrinoder har værdier større end rodnoden.

Lad os se på et eksempel.

Forestil dig, at vi har dette træ.

Nu vil vi vide, om vi har en knude baseret på værdi 52.

Lad os nedbryde det.

  1. Vi starter med rodnoden som vores nuværende knude. Er den givne værdi mindre end den aktuelle knudeværdi? Hvis ja, vil vi søge efter det i venstre undertegne.
  2. Er den givne værdi større end den aktuelle knudeværdi? Hvis ja, vil vi søge efter det i det rigtige undertrin.
  3. Hvis reglerne nr. 1 og # 2 begge er falske, kan vi sammenligne den aktuelle knudeværdi og den givne værdi, hvis de er ens. Hvis sammenligningen vender tilbage, kan vi sige, ”Yeah! Vores træ har den givne værdi, ”ellers siger vi:” Nej, det har det ikke. ”

Lad os nu kode det.

Lad os nedkøbe koden:

  • Linjer 8 og 9 falder ind under regel nr. 1.
  • Linje 10 og 11 falder ind under regel nr. 2.
  • Linie 13 falder ind under regel nr. 3.

Hvordan tester vi det?

Lad os oprette vores binære søgetræ ved at initialisere rodnoden med værdien 15.

Og nu vil vi indsætte mange nye noder.

For hver indsat node tester vi, om vores find_node-metode virkelig fungerer.

Ja, det fungerer for disse givne værdier! Lad os teste en værdi, der ikke findes i vores Binary Search Tree.

Oh yeah.

Vores søgning er færdig.

Sletning: fjernelse og organisering

Sletning er en mere kompleks algoritme, fordi vi er nødt til at håndtere forskellige sager. For en given værdi skal vi fjerne noden med denne værdi. Forestil dig følgende scenarier for denne knude: den har ingen børn, har et enkelt barn eller har to børn.

  • Scenario nr. 1: En knude uden børn (bladknude).

Hvis den node, vi vil slette, ikke har nogen børn, sletter vi den bare. Algoritmen behøver ikke at omorganisere træet.

  • Scenario nr. 2: En knude med kun et barn (venstre eller højre barn).

I dette tilfælde er vores algoritme nødt til at få den overordnede knude til at pege til den underordnede knude. Hvis noden er det venstre barn, får vi det forældre til det venstre barn til at pege på barnet. Hvis noden er det rigtige barn for dets forælder, får vi forælderen til det rigtige barn til at pege på barnet.

  • Scenario nr. 3: En knude med to børn.

Når noden har 2 børn, er vi nødt til at finde noden med den mindste værdi, startende fra nodens højre barn. Vi sætter denne knude med minimumsværdi på stedet for den knude, vi vil fjerne.

Det er tid til at kode.

  1. Først: Bemærk parameterværdien og overordnet. Vi ønsker at finde ud af, at nodethet har denne værdi, og nodens overordnede er vigtig for fjernelse af noden.
  2. Andet: Bemærk den returnerende værdi. Vores algoritme returnerer en boolesk værdi. Den vender sandt, hvis den finder noden og fjerner den. Ellers vil det vende tilbage falsk.
  3. Fra linje 2 til linje 9: Vi begynder at søge efter den knude, der har den værdi, som vi leder efter. Hvis værdien er mindre end den nuværende nodevalue, går vi til venstre undertråd, rekursivt (hvis, og kun hvis, den nuværende knude har et venstre barn). Hvis værdien er større, skal du gå til det rigtige undertrin, rekursivt.
  4. Linie 10: Vi begynder at tænke på fjerne algoritmen.
  5. Fra linje 11 til linje 13: Vi dækker knuden uden børn, og det er det venstre barn fra dets forælder. Vi fjerner noden ved at indstille forældrens venstre barn til Ingen.
  6. Linjer 14 og 15: Vi dækker knuden uden børn, og det er det rigtige barn fra dets forælder. Vi fjerner noden ved at indstille forældrenes rigtige barn til Ingen.
  7. Ryd node-metode: Jeg viser clear_node-koden nedenfor. Det indstiller noder til venstre barn, højre barn og dets værdi til Ingen.
  8. Fra linje 16 til linje 18: Vi dækker noden med kun et barn (venstre barn), og det er det venstre barn fra dets forælder. Vi indstiller forældrens venstre barn til nodens venstre barn (det eneste barn, det har).
  9. Fra linje 19 til linje 21: Vi dækker noden med kun et barn (venstre barn), og det er det rigtige barn fra dets forælder. Vi indstiller forældrens højre barn til nodens venstre barn (det eneste barn, det har).
  10. Fra linje 22 til linje 24: Vi dækker noden med kun et barn (højre barn), og det er det venstre barn fra dets forælder. Vi indstiller forældrens venstre barn til nodens højre barn (det eneste barn, det har).
  11. Fra linje 25 til linje 27: Vi dækker noden med kun et barn (højre barn), og det er det rigtige barn fra dets forælder. Vi indstiller forældrens rigtige barn til nodens rigtige barn (det eneste barn, det har).
  12. Fra linje 28 til linje 30: Vi dækker noden med både venstre og højre børnebørn. Vi får noden med den mindste værdi (koden vises nedenfor) og indstiller den til værdien af ​​den aktuelle knude. Afslut det ved at fjerne den mindste knude.
  13. Linie 32: Hvis vi finder den node, vi leder efter, er den nødt til at returnere sandt. Fra linje 11 til linje 31 behandler vi denne sag. Så bare returner sandt, og det er det.
  • Sådan bruges clear_node-metoden: indstil værdien Ingen til alle tre attributter - (værdi, venstre_barn og højrebørn)
  • Sådan bruger du metoden find_minimum_value: gå ned til venstre. Hvis vi ikke kan finde noder mere, fandt vi den mindste.

Lad os teste det.

Vi bruger dette træ til at teste vores remove_node algoritme.

Lad os fjerne noden med værdien 8. Det er en knude uden barn.

Lad os nu fjerne noden med værdien 17. Det er en knude med kun et barn.

Endelig fjerner vi en knude med to børn. Dette er roden til vores træ.

Testene er nu udført. :)

Det er alt for nu!

Vi lærte meget her.

Tillykke med at afslutte dette tætte indhold. Det er virkelig svært at forstå det koncept, som vi ikke kender. Men du gjorde det. :)

Dette er endnu et skridt fremad i min rejse til læring og mestring af algoritmer og datastrukturer. Du kan se dokumentationen for min komplette rejse her på min Renaissance Developer-publikation.

Ha det sjovt, hold læring og kodning.

Jeg håber du kunne lide dette indhold. Støtt mit arbejde med Ko-Fi

Min Twitter & Github. ☺

Yderligere ressourcer

  • Introduktion til trædatastruktur af mycodeschool
  • Træ af Wikipedia
  • Hvordan man ikke bliver stampet af træer af den talentfulde Vaidehi Joshi
  • Introduktion til træer, forelæsning af professor Jonathan Cohen
  • Introduktion til træer, forelæsning af professor David Schmidt
  • Introduktion til træer, forelæsning af professor Victor Adamchik
  • Træer med Gayle Laakmann McDowell
  • Binært træimplementering og test af TK
  • Coursera-kursus: Datastrukturer fra University of California, San Diego
  • Coursera-kursus: datastrukturer og ydeevne fra University of California, San Diego
  • Binary Search Tree-koncepter og implementering af Paul-programmering
  • Implementering og test af binært søgetræ af TK
  • Tree Traversal af Wikipedia
  • Binært søgetræ Fjern nodealgoritme af GeeksforGeeks
  • Binært søgetræ Fjern nodealgoritme af Algolist
  • At lære Python fra nul til helt