Syet binært træ

Et sammensyet binært træ  er en variant af et binært træ , der tillader hurtig gennemløb - givet en pointer til en node i et sammensyet træ, kan man nemt finde den næste (og/eller forrige) node i rækkefølge .

Baggrund

Binære træer, inklusive (men ikke begrænset til) binære søgetræer og deres varianter, kan bruges til at gemme flere elementer i en bestemt rækkefølge. For eksempel antager et binært søgetræ, at dataelementer er ordnet på en eller anden måde og bevarer denne rækkefølge, når de indsættes og fjernes. En nyttig operation på et sådant træ er traversal , det vil sige at besøge elementerne i træet i den rækkefølge, de vil blive husket i (hvilket svarer til rækkefølgen af ​​noderne i tilfælde af et binært søgetræ).

Den simple rekursive traversalalgoritme, der besøger hver knude i det binære søgetræ, er som følger. Antag , at t  er en pointer til en knude eller nul . "Besøg" t kan betyde enhver operation med denne node t eller det indhold, der er tildelt den.

Traversal algoritme( t ):

• Input: pointer t til node (eller nul )
• Hvis t = nul , returneres.
• Ellers:
  • Traverse(venstre-forfader( t ))
  • Vi besøger t
  • Traverse (højre-forfader( t ))

Problemet med denne algoritme er, at algoritmen på grund af rekursion bruger stakplads proportionalt med højden af ​​træet. Hvis træet er dårligt afbalanceret, når denne værdi O (log n ) for et træ med n elementer. I værste fald, når træet har form af en kæde , er højden af ​​træet n , så algoritmen vil kræve O ( n ) stakplads .

I 1968 spurgte Donald Knuth , om der var en ikke-rekursiv centreret traversalalgoritme, der ikke brugte stakken og efterlod træet uændret. En løsning på dette problem er træsyning, introduceret af James H. Morris i 1979 [1] [2] .

Definition

Et syet træ er defineret som følger:

"Et binært træ sammenføjes ved at tildele alle højre underordnede pointere, som normalt ville være nul-pegere, til pointere til knudepunktets næste knude ( hvis nogen), og alle venstre underordnede pegere, som normalt ville være nul-pegere, til pointere til tidligere knudepunkter i bestilling” [3] .

Det er også muligt at finde forælderen til en node fra et sammensat binært træ uden eksplicit at bruge en markør til forælderen eller stakken, selvom det er langsommere. Dette er nyttigt, når stakken er begrænset, eller når en stak af overordnede pointere ikke er tilgængelig (til at finde en overordnet pointer ved hjælp af dybde -først-søgning ).

For at se, hvordan dette er muligt, skal du overveje en node k , der har et ret underordnet r . Så skal nodens venstre pointer r enten være et underordnet eller en pointer tilbage til k . I det tilfælde, hvor r har et venstre barn, så skal det venstre barn have sit eget venstre barn, eller en pointer tilbage til k , og så videre for alle efterfølgende venstre børn. Når vi således går gennem kæden af ​​venstre visere fra r den ene efter den anden , finder vi til sidst stingmarkøren tilbage til k . Situationen er symmetrisk, når q er det venstre underordnede af p , i hvilket tilfælde vi kan spore de højre underordnede af knudepunktet q for at få en firmwarepointer til p .

Typer af syede binære træer

1. Enkelt blink: hver knude blinker med en pegepind enten til den forrige knude i rækkefølge eller til den næste knude i rækkefølge (venstre eller højre).
2. Dobbeltsyning: Hver knude er syet med en pegepind til både den forrige knude og den næste (venstre og højre).

På Python sprog :