Alles wat u moet weten over boomstructuren

Wanneer u voor het eerst leert coderen, is het gebruikelijk om arrays te leren als de “belangrijkste gegevensstructuur.”

Ook leert u uiteindelijk over hash tables. Als je een graad in de informatica behaalt, moet je een les over datastructuur volgen. Je leert dan ook over linked listsqueues, en stacks. Deze gegevensstructuren worden “lineaire” gegevensstructuren genoemd, omdat ze allemaal een logisch begin en een logisch eind hebben.

Wanneer we beginnen te leren over trees en graphs, kan het erg verwarrend worden. We slaan gegevens niet op een lineaire manier op. Beide datastructuren slaan gegevens op een specifieke manier op.

Dit artikel is bedoeld om u te helpen de boomstructuur beter te begrijpen en eventuele verwarring die u erover heeft op te helderen.

In dit artikel leren we:

• Wat is een boom
• Voorbeelden van bomen
• De terminologie ervan en hoe het werkt
• Hoe boomstructuren in code te implementeren.

Laten we beginnen met deze leerreis 🙂

Definitie

Wanneer je begint met programmeren, is het gebruikelijk om de lineaire datastructuren beter te begrijpen dan datastructuren zoals bomen en grafieken.

Bomen staan bekend als een niet-lineaire datastructuur. Ze slaan gegevens niet op een lineaire manier op.

Laten we eens in de praktijkvoorbeelden duiken!

Wat bedoel ik met hiërarchisch?

Stel je een stamboom voor met relaties van alle generaties: grootouders, ouders, kinderen, broers en zussen, enz. Gewoonlijk ordenen we stambomen hiërarchisch.

De bovenstaande tekening is mijn stamboom. Tossico, Akikazu, Hitomi, en Takemi zijn mijn grootouders.

Toshiaki en Juliana zijn mijn ouders.

TK, Yuji, Bruno, en Kaio zijn de kinderen van mijn ouders (ik en mijn broers).

De structuur van een organisatie is een ander voorbeeld van een hiërarchie.

In HTML werkt het Document Object Model (DOM) als een boom.

De HTML-tag bevat andere tags. We hebben een head tag en een body tag. Deze tags bevatten specifieke elementen. De head tag heeft meta en title tags. De body tag heeft elementen die in de gebruikersinterface worden weergegeven, bijvoorbeeld h1ali, enz.

Een technische definitie

Een tree is een verzameling entiteiten die nodes worden genoemd. Knooppunten zijn met elkaar verbonden door edges. Elke node bevat een value of data, en het kan al dan niet een child node hebben.

De first node van de tree wordt de root genoemd. Als deze root node wordt verbonden door een andere node, de root is dan een parent node en de verbonden node is een child.

Alle Tree nodes zijn met elkaar verbonden door links die edges worden genoemd. Het is een belangrijk onderdeel van trees, omdat het de relatie tussen nodes beheert.

Leaves zijn de laatste nodes op een tree. Het zijn nodes zonder kinderen. Net als echte bomen hebben we de rootbranches, en tenslotte de leaves.

Andere belangrijke concepten om te begrijpen zijn height en depth.

De height van een tree is de lengte van het langste pad naar een leaf.

De depth van een node is de lengte van het pad naar zijn root.

Terminologie samenvatting

• Wortel is de bovenste node van de tree
• Rand is de schakel tussen twee nodes
• Kind is een node dat een parent node
• Ouder is een node die een edge naar een child node heeft
• Blad is een node dat geen child node heeft in de tree
• Hoogte is de lengte van het langste pad naar een leaf
• Diepte is de lengte van het pad naar zijn root

Binaire bomen

Nu zullen we een specifiek type tree bespreken. We noemen het debinary tree.

“In de informatica is een binaire boom een boom-gegevensstructuur waarin elk knooppunt maximaal twee kinderen heeft, die worden aangeduid als het linkerkind en het rechterkind.” – Wikipedia

Dus laten we eens kijken naar een voorbeeld van een binary tree.

Laten we een binaire boom coderen

Het eerste wat we in gedachten moeten houden als we een binary tree implementeren, is dat het een verzameling nodes is. Elke node heeft drie attributen: valueleft_child, en right_child.

Hoe implementeren we een eenvoudige binary tree die met deze drie eigenschappen initialiseert?

Laten we eens kijken.

class BinaryTree: def __init__(self, value): self.value = value self.left_child = None self.right_child = None

Hier is het. Onze binary tree klasse.

Wanneer we een object instantiëren, geven we de value (de gegevens van de node) door als parameter. Kijk naar de left_child en de right_child. Beide zijn ingesteld op None.

Waarom?

Omdat wanneer we onze node maken, deze geen kinderen heeft. We hebben alleen de node data.

Laten we het testen:

tree = BinaryTree('a')print(tree.value) # aprint(tree.left_child) # Noneprint(tree.right_child) # None

Dat is het.

We kunnen de stringa‘ als de value aan onze Binary Tree node doorgeven. Als we de valueleft_child, en right_child afdrukken, kunnen we de waarden zien.

Laten we nu naar het invoeg gedeelte gaan. Wat moeten we hier doen?

We zullen een methode implementeren om een nieuwe node in te voegen in de right en in de left.

Hier zijn de regels:

• Als de huidige node geen left child heeft, maken we gewoon een nieuwe node en stellen die in op de left_child van de huidige node.
• Als het wel de left child heeft, maken we een nieuwe node aan en zetten die op de plaats van de huidige left child. Wijs deze left child node toe aan de left child van de nieuwe node.

Laten we het uittekenen. 🙂

Hier is de code:

Wederom, als de huidige node geen left child heeft, maken we gewoon een nieuwe node en stellen deze in op de left_child van de huidige node. Of anders maken we een nieuwe node aan en zetten die op de plaats van de huidige left child. Wijs deze left child node toe aan de left child van de nieuwe node.

En we doen hetzelfde om een right child node in te voegen.

Doen we. 🙂

Maar niet helemaal. We moeten het nog testen.

Laten we de volgendetree bouwen:

Om de illustratie van deze boom samen te vatten:

• anode zal de root van onze binary Tree zijn.
• aleft child is bnode
• aright child is cnode
• bright child is dnodebnode heeft geen left child)
• cleft child is enode
• cright child is fnode
• beide e en fnodes hebben geen kinderen

Dus hier is de code voor de tree:

Invoegen is gedaan.

Nu moeten we nadenken over tree traversal.

We hebben hier twee opties: Depth-First Search (DFS) en Breadth-First Search (BFS).

• DFS “is een algoritme voor het doorkruisen of doorzoeken van een boomstructuur van gegevens. Men begint bij de wortel en verkent zo ver mogelijk langs elke tak alvorens terug te keren.” – Wikipedia
• BFS “is een algoritme voor het doorkruisen of doorzoeken van een boomstructuur. Het begint bij de boomwortel en verkent eerst de naburige knooppunten, alvorens naar de buren van het volgende niveau te gaan.” – Wikipedia

Dus laten we eens duiken in elk tree traversal type.

Depth-First Search (DFS)

DFS verkent een pad helemaal tot aan een blad alvorens terug te keren en een ander pad te verkennen. Laten we eens kijken naar een voorbeeld met dit type traversal.

Het resultaat voor dit algoritme zal 1-2-3-4-5-6-7 zijn.

Waarom?

Laten we het uitsplitsen.

1. Start bij de root (1). Druk het af.

2. Ga naar de left child (2). Druk het af.

3. Ga dan naar de left child (3). Druk het af. (Deze node heeft geen kinderen)

4. Backtrack en ga naar de right child (4). Druk het af. (Deze node heeft geen kinderen)

5. Backtrack naar de rootnode en ga naar de right child (5). Druk het af.

6. Ga naar de left child (6). Druk het af. (Deze node heeft geen kinderen)

7. Backtrack en ga naar de right child (7). Druk het af. (Deze node heeft geen kinderen)

8. Klaar.

Wanneer we diep naar het blad gaan en backtracken, heet dit het DFS algoritme.

Nu we bekend zijn met dit traversal-algoritme, zullen we soorten DFS bespreken: pre-orderin-order, en post-order.

Pre-order

Dit is precies wat we in het bovenstaande voorbeeld hebben gedaan.

1. Print de waarde van de node.
2. Ga naar de left child en print deze. Dit is als, en alleen als, het heeft een left child.
3. Ga naar de right child en druk het af. Dit is als, en alleen als, het een right child heeft.

In-volgorde

Het resultaat van het in-volgorde algoritme voor dit tree voorbeeld is 3-2-4-1-6-5-7.

De linker eerst, de middelste tweede, en de rechter laatste.

Nu gaan we het coderen.

def in_order(self): if self.left_child: self.left_child.in_order() print(self.value) if self.right_child: self.right_child.in_order()

1. Ga naar de left child en druk het af. Dit is als, en alleen als, het een left child heeft.
2. Print de waarde van de node
3. Ga naar de right child en print het. Dit is als, en alleen als, het een right child heeft.

Post-order

Het resultaat van het post order algoritme voor dit tree voorbeeld is 3-4-2-6-7-5-1.

De linker eerst, de rechter tweede, en de middelste als laatste.

Laten we dit eens coderen.

1. Ga naar de left child en print het uit. Dit is als, en alleen als, het heeft een left child.
2. Ga naar de right child en print het. Dit is als, en alleen als, het een right child heeft.
3. Print de waarde van de node

Breadth-First Search (BFS)

BFS algoritme doorkruist de tree niveau voor niveau en diepte voor diepte.

Hier volgt een voorbeeld dat helpt om dit algoritme beter uit te leggen:

Dus we doorkruisen niveau per niveau. In dit voorbeeld is het resultaat 1-2-5-3-4-6-7.

• Level/diepte 0: alleen node met waarde 1
• Level/diepte 1: nodes met waarden 2 en 5
• Level/Diepte 2: nodes met waarden 3, 4, 6, en 7

Nu gaan we het coderen.

Om een BFS-algoritme te implementeren, gebruiken we als hulp de queue-datastructuur.

Hoe werkt het?

Hier volgt de uitleg.

1. Eerst voeg je de rootnode in de queue met de put methode.
2. Iterate terwijl de queue niet leeg is.
3. Geef de eerste node in de queue, en print vervolgens de waarde ervan.
4. Voeg zowel left als rightchildren toe in de queue (als de huidige nodechildren heeft).
5. Gewerkt. We zullen de waarde van elke node, niveau voor niveau afdrukken, met onze queuehelper.

Binaire zoekboom

“Een binaire zoekboom wordt soms geordende of gesorteerde binaire boom genoemd, en het houdt zijn waarden in gesorteerde volgorde, zodat lookup en andere operaties gebruik kunnen maken van het principe van binair zoeken” – Wikipedia

Een belangrijke eigenschap van een Binary Search Tree is dat de waarde van een Binary Search Treenode groter is dan de waarde van de nakomelingen van zijn left child, maar kleiner dan de waarde van de nakomelingen van zijn right child.“

Hier volgt een uitsplitsing van de bovenstaande illustratie:

• A is omgekeerd. De subtree 7-5-8-6 moet aan de rechterkant, en de subtree 2-1-3 moet aan de linkerkant.
• B is de enige juiste optie. Het voldoet aan de Binary Search Tree eigenschap.
• C heeft één probleem: de node met de waarde 4. Het moet aan de linkerkant van de root staan omdat het kleiner is dan 5.

Let’s code a Binary Search Tree!

Nu is het tijd om te coderen!

Wat zullen we hier zien? We zullen nieuwe nodes invoegen, zoeken naar een waarde, nodes verwijderen, en de balans van de tree.

Laten we beginnen.

Invoegen: nieuwe nodes toevoegen aan onze boom

Stel je voor dat we een lege tree hebben en we willen nieuwe nodes toevoegen met de volgende waarden in deze volgorde: 50, 76, 21, 4, 32, 100, 64, 52.

Het eerste wat we moeten weten is of 50 de root van onze boom is.

We kunnen nu node gaan invoegen bij node.

• 76 is groter dan 50, dus voeg 76 in aan de rechterkant.
• 21 is kleiner dan 50, dus voeg 21 in aan de linkerkant.
• 4 is kleiner dan 50. Node met waarde 50 heeft een left child 21. Omdat 4 kleiner is dan 21, voeg je het in aan de linkerkant van deze node.
• 32 is kleiner dan 50. Node met waarde 50 heeft een left child 21. Omdat 32 groter is dan 21, voeg 32 in aan de rechterkant van deze node.
• 100 is groter dan 50. Node met waarde 50 heeft een right child 76. Omdat 100 groter is dan 76, voeg je 100 in aan de rechterkant van deze node.
• 64 is groter dan 50. Node met waarde 50 heeft een right child 76. Omdat 64 kleiner is dan 76, voeg 64 in aan de linkerkant van deze node.
• 52 is groter dan 50. Node met waarde 50 heeft een right child 76. Omdat 52 kleiner is dan 76, heeft node met waarde 76 een left child 64. 52 is kleiner dan 64, dus plaats 54 aan de linkerkant van deze node.

Ziet u hier een patroon?

Laten we het eens uitsplitsen.

1. Is de nieuwe node waarde groter of kleiner dan de huidige node?
2. Als de waarde van de nieuwe node groter is dan de huidige node, ga dan naar de rechter subtree. Als de huidige node geen right child heeft, voeg hem dan daar in, of ga anders terug naar stap #1.
3. Als de waarde van de nieuwe node kleiner is dan de huidige node, ga dan naar de linker subtree. Als de huidige node geen left child heeft, voeg hem daar dan in, of ga anders terug naar stap #1.
4. We hebben hier geen speciale gevallen behandeld. Wanneer de waarde van een nieuwe node gelijk is aan de huidige waarde van de node, gebruik dan regel nummer 3. Overweeg gelijke waarden in te voegen aan de linkerkant van de subtree.

Nu gaan we het coderen.

Het lijkt heel eenvoudig.

Het krachtige deel van dit algoritme is het recursiegedeelte, dat op regel 9 en regel 13 staat. Beide regels code roepen de insert_node methode aan, en gebruiken deze voor de left en rightchildren, respectievelijk. Lijnen 11 en 15 zijn degenen die het invoegen doen voor elke child.

Let’s search for the node value… Or not…

Het algoritme dat we nu gaan bouwen gaat over het doen van zoekopdrachten. Voor een gegeven waarde (geheel getal), zullen we zeggen of onze Binary Search Tree die waarde wel of niet heeft.

Een belangrijk punt om op te merken is hoe we het boom invoeg algoritme hebben gedefinieerd. Eerst hebben we onze rootnode. Alle linker subtreenodes zullen kleinere waarden hebben dan de rootnode. En alle juiste subtreenodes zullen waarden hebben die groter zijn dan de rootnode.

Laten we eens naar een voorbeeld kijken.

Stel u voor dat we deze tree hebben.

Nu willen we weten of we een knooppunt hebben op basis van waarde 52.

Laten we het eens uitsplitsen.

1. We beginnen met de rootnode als onze huidige node. Is de gegeven waarde kleiner dan de huidige node waarde? Zo ja, dan zoeken we naar de linker subtree.
2. Is de opgegeven waarde groter dan de huidige node waarde? Zo ja, dan zoeken we het op de rechter subtree.
3. Als regel #1 en #2 beide onwaar zijn, kunnen we de huidige node waarde en de gegeven waarde vergelijken of ze gelijk zijn. Als de vergelijking true oplevert, dan kunnen we zeggen, “Ja! Onze tree heeft de gegeven waarde,” anders zeggen we, “Neeee, dat heeft het niet.”

Nu gaan we het coderen.

Laten we de code eens afkraken:

• Lijnen 8 en 9 vallen onder regel #1.
• Lijnen 10 en 11 vallen onder regel #2.
• Lijn 13 valt onder regel #3.

Hoe testen we het?

Laten we onze Binary Search Tree maken door de rootnode te initialiseren met de waarde 15.

bst = BinarySearchTree(15)

En nu gaan we veel nieuwe nodes invoegen.

Voor elke ingevoegde node gaan we testen of onze find_node methode echt werkt.

Ja, het werkt voor deze gegeven waarden! Laten we eens testen op een waarde die niet bestaat in onze Binary Search Tree.

print(bst.find_node(0)) # False

Oh ja.

Onze zoektocht is klaar.

Wissen: verwijderen en ordenen

Wissen is een complexer algoritme omdat we verschillende gevallen moeten afhandelen. Voor een gegeven waarde moeten we de node met deze waarde verwijderen. Stel je de volgende scenario’s voor voor deze node : het heeft geen children, heeft een enkele child, of heeft twee children.

• Scenario #1: Een node met geen childrenleafnode).

# |50| |50|# / \ / \# |30| |70| (DELETE 20) ---> |30| |70|# / \ \# |20| |40| |40|

Als de node die we willen verwijderen geen kinderen heeft, verwijderen we deze gewoon. Het algoritme hoeft de tree niet te reorganiseren.

• Scenario #2: Een node met slechts één kind (left of right kind).

# |50| |50|# / \ / \# |30| |70| (DELETE 30) ---> |20| |70|# / # |20|

In dit geval moet ons algoritme ervoor zorgen dat de ouder van de node naar de child node wijst. Als de node de left child is, dan laten we de parent van de left child wijzen naar de child. Als de node de right child van zijn parent is, dan laten we de parent van de right child naar de child wijzen.

• Scenario #3: Een node met twee kinderen.

# |50| |50|# / \ / \# |30| |70| (DELETE 30) ---> |40| |70|# / \ /# |20| |40| |20|

Wanneer de node 2 kinderen heeft, moeten we de node met de minimale waarde vinden, beginnend bij de node‘sright child. We zullen deze node met minimum waarde op de plaats zetten van de node die we willen verwijderen.

Het is tijd om te coderen.

1. Eerst: Let op de parameters value en parent. We willen de node vinden die deze value heeft, en de node’s ouder is belangrijk voor het verwijderen van de node.
2. Ten tweede: Let op de terugkerende waarde. Ons algoritme geeft een booleaanse waarde terug. Het geeft True terug als het de node vindt en verwijdert. Anders geeft het False terug.
3. Van regel 2 tot regel 9: We beginnen te zoeken naar de node die de value heeft waarnaar we op zoek zijn. Als de value kleiner is dan de current nodevalue , gaan we naar de left subtree, recursief (als, en alleen als, de current node een left child heeft). Als de value groter is, ga dan naar de right subtree, recursief.
4. Regel 10: We beginnen na te denken over het remove algoritme.
5. Van regel 11 tot regel 13: We dekken de node af met geen children , en wel de left child uit zijn parent. We verwijderen de node door de parent’s left child op None te zetten.
6. Regels 14 en 15: We dekken de node af zonder children , en het is de right child uit het parent. We verwijderen de node door de parent’s right child in te stellen op None.
7. Clear node method: Ik zal de clear_node code hieronder laten zien. Het stelt de nodes left child , right child, en zijn value in None.
8. Van regel 16 tot regel 18: We bedekken de node met slechts één childleft child), en wel de left child uit zijn parent. We stellen de parent’s left child in op de node’s left child (het enige kind dat het heeft).
9. Van regel 19 tot regel 21: We bedekken de node met slechts één childleft child), en het is de right child van zijn parent. We stellen de parent’s right child in op de node’s left child (het enige kind dat het heeft).
10. Van regel 22 tot regel 24: We bedekken de node met slechts één childright child), en het is de left child van zijn parent. We zetten de parent’s left child op de node’s right child (het enige kind dat het heeft).
11. Van regel 25 tot regel 27: We bedekken de node met slechts één childright child) , en het is de right child van zijn parent. We zetten de parent’s right child op de node’s right child (het enige kind dat het heeft).
12. Van regel 28 tot regel 30: We bedekken de node met zowel left als rightchildren. We halen de node met de kleinste value (de code staat hieronder) en zetten deze op de value van de current node . Maak het af door de kleinste node te verwijderen.
13. Regel 32: Als we de node vinden die we zoeken, moet deze True teruggeven. Van regel 11 tot regel 31, behandelen we dit geval. Dus gewoon True teruggeven en dat is het.

• Om de methode clear_node te gebruiken: stel de None waarde in op alle drie attributen – (valueleft_child, en right_child)

def clear_node(self): self.value = None self.left_child = None self.right_child = None

• Om de find_minimum_value methode te gebruiken: ga helemaal naar beneden naar links. Als we geen nodes meer vinden, hebben we de kleinste gevonden.

def find_minimum_value(self): if self.left_child: return self.left_child.find_minimum_value() else: return self.value

Nu gaan we het testen.

We zullen deze tree gebruiken om ons remove_node algoritme te testen.

# |15|# / \# |10| |20|# / \ / \# |8| |12| |17| |25|# \# |19|

Laten we de node met de value 8 verwijderen. Het is een node zonder kind.

print(bst.remove_node(8, None)) # Truebst.pre_order_traversal()# |15|# / \# |10| |20|# \ / \# |12| |17| |25|# \# |19|

Nu laten we de node met de value 17 verwijderen. Het is een node met slechts één kind.

print(bst.remove_node(17, None)) # Truebst.pre_order_traversal()# |15|# / \# |10| |20|# \ / \# |12| |19| |25|

Ten slotte gaan we een node met twee kinderen verwijderen. Dit is de root van onze tree.

print(bst.remove_node(15, None)) # Truebst.pre_order_traversal()# |19|# / \# |10| |20|# \ \# |12| |25|

De tests zijn nu gedaan.

Dat is alles voor nu!

We hebben hier veel geleerd.

Congrats voor het afmaken van deze dichte inhoud. Het is echt moeilijk om een concept te begrijpen dat we niet kennen. Maar het is je gelukt 🙂

Dit is weer een stap voorwaarts op mijn reis om algoritmen en gegevensstructuren te leren kennen en beheersen. Je kunt de documentatie van mijn complete reis hier zien op mijn Renaissance Developer publicatie.

Heel veel plezier, blijf leren en coderen.

Mijn Twitter & Github. ☺

Aanvullende bronnen

• Inleiding tot boomstructuur door mycodeschool
• Tree door Wikipedia
• How To Not Be Stumped By Trees door de getalenteerde Vaidehi Joshi
• Intro to Trees, Lezing door Professor Jonathan Cohen
• Intro to Trees, Lezing door professor David Schmidt
• Intro to Trees, Lezing door professor Victor Adamchik
• Trees met Gayle Laakmann McDowell
• Binary Tree Implementation and Tests door TK
• Coursera Course: Data Structures door University of California, San Diego
• Coursera Course: Data Structures and Performance door University of California, San Diego
• Binary Search Tree concepten en Implementatie door Paul Programming
• Binary Search Tree Implementatie en Tests door TK
• Tree Traversal door Wikipedia
• Binary Search Tree Remove Node Algorithm door GeeksforGeeks
• Binary Search Tree Remove Node Algorithm door Algolist
• Learning Python From Zero to Hero