Binaire boom met schroefdraad - Threaded binary tree
In de informatica is een threaded binaire boom een binaire boomvariant die het doorkruisen in een bepaalde volgorde mogelijk maakt (vaak dezelfde volgorde die al voor de boom is gedefinieerd).
Een hele binaire zoekboom kan gemakkelijk worden doorlopen in de volgorde van de hoofdsleutel, maar als u slechts een verwijzing naar een knoop krijgt, kan het vinden van de volgende knoop traag of onmogelijk zijn. Bladknooppunten hebben bijvoorbeeld per definitie geen afstammelingen, dus geen enkel ander knooppunt kan worden bereikt met alleen een verwijzing naar een bladknooppunt -- die natuurlijk het gewenste "volgende" knooppunt bevat. Een threaded tree voegt extra informatie toe aan sommige of alle nodes, zodat de "volgende" node snel gevonden kan worden. Het kan ook worden doorkruist zonder recursie en de extra opslag (evenredig met de diepte van de boom) die nodig is.
Inrijgen
"Een binaire boom wordt geregen door alle rechter onderliggende aanwijzers die normaal nul zouden zijn, naar de in-order opvolger van het knooppunt te laten wijzen ( als deze bestaat), en alle linker onderliggende aanwijzers die normaal nul zouden zijn, wijzen naar de in-order voorganger van de knoop."
Dit veronderstelt dat de verplaatsingsvolgorde hetzelfde is als de volgorde waarin de boom wordt verplaatst. Aanwijzers kunnen echter in plaats daarvan (of daarnaast) worden toegevoegd aan boomknooppunten in plaats van te vervangen. De aldus gedefinieerde gekoppelde lijsten worden ook gewoonlijk "threads" genoemd en kunnen worden gebruikt om doorgang in elke gewenste volgorde mogelijk te maken. Een boom waarvan de knooppunten informatie over mensen vertegenwoordigen, kan bijvoorbeeld op naam worden gesorteerd, maar heeft extra threads die snelle doorloop mogelijk maken in volgorde van geboortedatum, gewicht of een ander bekend kenmerk.
Motivatie
Bomen, inclusief (maar niet beperkt tot) binaire zoekbomen , kunnen worden gebruikt om items in een bepaalde volgorde op te slaan, zoals de waarde van een eigenschap die in elk knooppunt is opgeslagen, vaak een sleutel genoemd . Een handige bewerking op zo'n boom is traversal : alle items in volgorde van de sleutel bezoeken.
Een eenvoudig recursief traversaal algoritme dat elk knooppunt van een binaire zoekboom bezoekt , is het volgende. Neem aan dat t een pointer is naar een knoop, of nil . "Bezoek" t kan betekenen dat een actie wordt uitgevoerd op het knooppunt t of de inhoud ervan.
Algoritme traverse ( t ):
- Input: een pointer t naar een knoop (of nul )
- Als t = nul , retourneer.
- Anders:
- traverse(links-kind( t ))
- Bezoek t
- traverse(rechts-kind( t ))
Een probleem met dit algoritme is dat het vanwege zijn recursie stackruimte gebruikt die evenredig is met de hoogte van een boom. Als de boom redelijk in balans is, komt dit neer op O (log n ) ruimte voor een boom met n elementen. In het ergste geval, wanneer de boom de vorm aanneemt van een ketting , is de hoogte van de boom n, dus het algoritme neemt O ( n ) ruimte in beslag . Een tweede probleem is dat alle traversals bij de wortel moeten beginnen wanneer knooppunten alleen verwijzingen naar hun kinderen hebben. Het is gebruikelijk om een aanwijzer naar een bepaald knooppunt te hebben, maar dat is niet voldoende om terug te gaan naar de rest van de boom tenzij er extra informatie wordt toegevoegd, zoals draadaanwijzers.
Bij deze benadering is het misschien niet mogelijk om te zeggen of de linker- en/of rechterwijzers in een bepaald knooppunt daadwerkelijk naar kinderen verwijzen, of een gevolg zijn van threading. Als het onderscheid nodig is, is het toevoegen van een enkele bit aan elk knooppunt voldoende om het op te nemen.
In een leerboek uit 1968 vroeg Donald Knuth of er een niet-recursief algoritme voor in-order traversal bestaat, dat geen stapel gebruikt en de boom ongewijzigd laat. Een van de oplossingen voor dit probleem is het inrijgen van bomen, gepresenteerd door Joseph M. Morris in 1979. In de vervolgeditie van 1969 schreef Knuth de weergave van bomen met schroefdraad toe aan Perlis en Thornton (1960).
Relatie met bovenliggende aanwijzingen
Een andere manier om vergelijkbare doelen te bereiken, is door in elk knooppunt een aanwijzer op te nemen naar het bovenliggende knooppunt van dat knooppunt. Gegeven dat, kan het "volgende" knooppunt altijd worden bereikt. "juiste" pointers zijn nog steeds nul wanneer er geen juiste kinderen zijn. Om het "volgende" knooppunt te vinden van een knooppunt waarvan de rechteraanwijzer nul is, loopt u door de "bovenliggende" aanwijzers totdat u een knooppunt bereikt waarvan de rechteraanwijzer niet nul is en niet het kind is waar u zojuist vandaan kwam. Dat knooppunt is het "volgende" knooppunt, en daarna komen zijn nakomelingen aan de rechterkant.
Het is ook mogelijk om de ouder van een knooppunt te ontdekken uit een binaire structuur met schroefdraad, zonder expliciet gebruik van bovenliggende aanwijzers of een stapel, hoewel dit langzamer is. Om dit te zien, overweeg een knoop k met rechterkind r . Dan moet de linkerwijzer van r een kind zijn of een draad terug naar k . In het geval dat r een linkerkind heeft, moet dat linkerkind op zijn beurt ofwel een eigen linkerkind hebben of een draad terug naar k , enzovoort voor alle opeenvolgende linkerkinderen. Dus door de keten van linkse wijzers van r te volgen , zullen we uiteindelijk een draad vinden die terug wijst naar k . De situatie is symmetrisch vergelijkbaar wanneer q het linkerkind van p is — we kunnen de rechterkinderen van q volgen naar een draad die vooruit wijst naar p .
Types
- Single Threaded: elk knooppunt is gekoppeld aan ofwel de in-order voorganger of opvolger (links of rechts).
- Double threaded: elk knooppunt wordt zowel naar de in-order voorganger als naar de opvolger (links en rechts) gedraaid .
In Python :
def parent(node):
if node is node.tree.root:
return None
else:
x = node
y = node
while True:
if is_thread(y):
p = y.right
if p is None or p.left is not node:
p = x
while not is_thread(p.left):
p = p.left
p = p.left
return p
elif is_thread(x):
p = x.left
if p is None or p.right is not node:
p = y
while not is_thread(p.right):
p = p.right
p = p.right
return p
x = x.left
y = y.right
De reeks van in-order-traversal
Threads verwijzen naar de voorgangers en opvolgers van het knooppunt volgens een inorder-traversal.
In-order doorkruisen van de draadboom is A,B,C,D,E,F,G,H,I, de voorloper van Eis D, de opvolger van Eis F.
Voorbeeld
Laten we de Threaded Binary-boom maken van een normale binaire boom:
De in-order- traversal voor de bovenstaande boom is - DBAE C. Dus de respectieve Threaded Binary-boom zal zijn -
Null-links
In een m-way threaded binaire boom met n knooppunten, zijn er n*m - (n-1) lege links.
iteratieve traversal
Er is een algoritme om een binaire boom met schroefdraad te doorlopen zonder recursie te gebruiken. Elke dergelijke methode moet in plaats daarvan iteratie gebruiken; dat wil zeggen, alle stappen moeten in een lus worden gedaan om alle knooppunten in de boom te bezoeken.
In-order traversal bezoekt per definitie eerst de linker sub-boom van elk knooppunt (als het bestaat en als het nog niet is bezocht); dan bezoekt het het knooppunt zelf en tenslotte de rechter sub-boom van het knooppunt (als deze bestaat). Als de juiste substructuur niet bestaat, maar er wel een threaded link is, maken we van de threaded node het huidige knooppunt. Een voorbeeld is hieronder weergegeven.
Algoritme
- Als het huidige knooppunt een linkerkind heeft dat niet in de bezochte lijst staat, ga dan naar stap 2, anders stap 3.
- Zet dat linkerkind in de lijst met bezochte knooppunten en maak er het huidige knooppunt van. Ga naar stap 6.
- Bezoek het knooppunt. Als de knoop een rechterkind heeft, ga dan naar stap 4, ga anders naar stap 5.
- Maak van het juiste kind het huidige knooppunt. Ga naar stap 6.
- Als er een draadknooppunt is, maak dit dan het huidige knooppunt.
- Als alle knooppunten zijn afgedrukt, beëindigt u, anders gaat u naar stap 1.
| Stap | Li | ||
|---|---|---|---|
| 1 | 'A' heeft een linkerkind B, dat niet is bezocht. Dus plaatsen we B in onze lijst met bezochte knooppunten en B wordt ons huidige knooppunt. | B | |
| 2 | 'B' heeft een linkerkind, 'D', dat niet in onze lijst met bezochte knooppunten staat. Dus plaatsen we 'D' in die lijst en maken er ons huidige knooppunt van. | BD | |
| 3 | 'D' heeft geen kind meer, dus bezoeken we 'D'. Dan kijken we naar het juiste kind. 'D' heeft geen recht kind en dus controleren we op zijn thread-link. Het heeft een draad tot knooppunt 'B'. Dus maken we van 'B' het huidige knooppunt. | BD | NS |
| 4 | 'B' heeft een linkerkind, maar het staat al in de lijst met bezochte knooppunten. Ga dus naar 'B'. Controleer nu of het een recht kind heeft. Het doet niet. Maak dus van het knooppunt met schroefdraad (dwz 'A') het huidige knooppunt. | BD | DB |
| 5 | 'A' heeft een linkerkind, 'B', maar het is al bezocht. Dus, bezoek 'A'. Nu heeft 'A' een recht kind, 'C' en wordt niet bezocht. Dus voeg het toe aan de lijst en maak er het huidige knooppunt van. | BDC | DBA |
| 6 | 'C' heeft een linkerkind 'E' dat niet wordt bezocht. Voeg het toe aan de lijst en maak er het huidige knooppunt van. | BDCE | DBA |
| 7 | en tenslotte..... | DBAEC |
