Bomen, rood-en-zwarte bomen

"Hallo Amigo!"

"Hallo Rishi!"

'Ik heb daar mijn oude aantekeningen gevonden en wat interessant materiaal voor je voorbereid. Ik denk dat je het wel wilt horen.'

'Laat maar horen. Je vindt altijd wel iets interessants dat later heel nuttig blijkt te zijn.'

"OK. Vandaag wil ik jullie vertellen over bomen , dus ik zal beginnen met grafieken ."

" Een grafiek is een systeem van punten en lijnen die ze met elkaar verbinden. De punten worden de hoekpunten van de grafiek genoemd en de lijnen worden de randen van de grafiek genoemd. Bijvoorbeeld:"

"Een grafiek is erg handig om te gebruiken als wiskundig model voor verschillende real-world processen en taken. Er zijn veel verschillende taken en algoritmen bedacht voor grafieken, dus ze worden vrij vaak gebruikt."

"Stel bijvoorbeeld dat hoekpunten steden zijn en randen wegen. Dan wordt zoeken naar de kortste weg tussen steden: «gegeven een grafiek, vind het kortste pad tussen twee hoekpunten». "

"Maar het pad van A naar B is niet altijd hetzelfde als het pad van B naar A. Soms heeft het dus de voorkeur om twee verschillende lijnen te hebben. Om dit te doen, worden de lijnen (randen van de grafiek) vervangen door pijlen. In met andere woorden, de grafiek kan twee pijlen hebben: een van A naar B en een andere van B naar A."

"Als de grafiek pijlen gebruikt, wordt het een gerichte grafiek genoemd ; als het alleen maar lijnen heeft, wordt het een ongerichte grafiek genoemd ."

"Elk hoekpunt kan zijn eigen aantal randen hebben. Een hoekpunt kan ook helemaal geen randen hebben. Omgekeerd kan een hoekpunt door randen verbonden zijn met elk ander hoekpunt.  Als elk paar hoekpunten in een graaf verbonden is door een rand, dan het wordt een volledige grafiek genoemd. "

"Als je randen kunt gebruiken om elk hoekpunt in een graaf te bereiken, dan wordt het een verbonden graaf genoemd . Een graaf die drie afzonderlijke hoekpunten heeft en geen randen heeft, is nog steeds een graaf, maar we noemen het een niet-verbonden graaf."

"Om een ​​verbonden graaf te vormen uit N hoekpunten, heb je minimaal N-1 randen nodig. Dit type graaf wordt een boom genoemd."

"Bovendien wordt meestal één hoekpunt gekozen als de wortel van de boom , en de rest wordt aangemerkt als takken. Boomtakken die geen eigen takken hebben, worden bladeren genoemd . Bijvoorbeeld:"

"Als elk element van de boom twee kinderen heeft, wordt het een binaire boom genoemd . Met andere woorden, er kunnen 0 of 2 takken zijn. Rechtsboven zie je een binaire boom."

" Een boom wordt een complete binaire boom genoemd als elke tak 2 kinderen heeft en alle bladeren (hoekpunten zonder kinderen) op dezelfde rij staan."

"Bijvoorbeeld:"

"Waarom zijn deze bomen nodig?"

"Oh, bomen worden op veel plaatsen gebruikt. Over het algemeen zijn binaire bomen gesorteerde gestructureerde gegevens."

"Wat is dat?"

"Ja, het is heel eenvoudig. We slaan een bepaalde waarde op in elk hoekpunt. En elk element volgt een regel: de waarde die is opgeslagen in het rechterkind moet groter zijn dan de waarde die is opgeslagen in het hoekpunt, en de waarde die is opgeslagen in het linkerkind moet kleiner zijn dan de waarde die is opgeslagen in het hoekpunt.  Deze volgorde maakt het mogelijk om snel de elementen van de boom te vinden die je nodig hebt."

"Kunt u verduidelijken wat dat betekent?"

"Boomelementen worden meestal gesorteerd door optellen. Stel dat we 7 elementen hebben: 13, 5, 4, 16, 8, 11, 10"

"Hier is hoe de elementen aan de boom worden toegevoegd."

"Als we in deze boom het getal 7 zoeken, dan gaat de zoektocht zo"

"0) Begin bij de wortel."

"1a) Is 7 gelijk aan 13? Nee"

"1b) Is 7 groter dan 13? Nee, dus gaan we naar de linker deelboom."

"2a) Is 7 gelijk aan 5? Nee."

"2b) Is 7 groter dan 5? Ja, dus gaan we naar de rechter subboom."

"3a) Is 7 gelijk aan 8? Nee"

"3b) Is 7 groter dan 8? Nee, dus gaan we naar de linker deelboom."

"4a) Er is geen linker deelboom, wat betekent dat het getal 7 niet in de boom staat."

"Ah. Met andere woorden, we hoeven alleen de hoekpunten op het pad van de wortel naar de mogelijke locatie van het gewenste getal te controleren. Ja, dat is echt snel."

"Bovendien, als de boom in evenwicht is, hoef je slechts ongeveer 20 hoekpunten te passeren om een ​​miljoen elementen te doorzoeken."

"Ik ben het ermee eens - dat zijn er niet veel."

"Wat bedoel je met evenwichtige boom?"

"Een boom die niet vervormd is, dus geen lange takken heeft. Als de elementen bijvoorbeeld al gesorteerd waren toen we de boom bouwden, dan hadden we een heel lange boom gemaakt die uit één tak bestond. "

"Hmm. Je hebt gelijk. Dus wat gaan we doen?"

"Zoals je waarschijnlijk al geraden hebt, heeft de meest efficiënte boom takken die ongeveer even lang zijn. Vervolgens wordt bij elke vergelijking het grootste deel van de resterende subboom verwijderd."

"Dus we moeten de boom herbouwen?"

"Ja. Het moet "gebalanceerd" zijn - om zo dicht mogelijk bij een volledige binaire boom te komen."

"Om dit probleem op te lossen, werden zelfbalancerende bomen uitgevonden.  Als de boom vervormd raakt na het toevoegen van een element, dan herschikt hij de elementen enigszins om alles in orde te maken.  Hier is een voorbeeld van balanceren:"

"Sommige van deze bomen staan ​​bekend als rood -zwarte bomen."

"Waarom heten ze rood-zwart?"

"Hun uitvinder tekende alle hoekpunten met twee kleuren. De ene kleur was rood en de andere was zwart. De verschillende hoekpunten gehoorzamen aan verschillende regels. Dit vormt de volledige basis voor de balanceringsprocedure."

"Bijvoorbeeld:"

"Dus wat zijn deze regels?"

"1) Een rood hoekpunt kan niet het kind zijn van een rood hoekpunt."

"2) De zwarte diepte van elk blad is hetzelfde (zwarte diepte verwijst naar het aantal zwarte hoekpunten op het pad vanaf de wortel)."

"3) De wortel van de boom is zwart."

"Ik zal niet uitleggen hoe dit werkt - je hoofd ontploft waarschijnlijk al."

"Ja. Mijn processor geeft een beetje rook af."

"Hier is een link voor je. Als je wilt, kun je hier meer over lezen."

Link naar aanvullend materiaal

"En nu, ga even pauzeren."