[Powered by Google Translate] Hoe zou u vertegenwoordigt al uw gezinsleden in een computer?
We kunnen gewoon gebruik maken van een lijst,
maar er is een duidelijke hiërarchie hier.
>> Laten we zeggen dat we beginnen met je overgrootmoeder, Alice.
Ze heeft 2 zonen, Bob
en je grootvader, Charlie.
Charlie heeft 3 kinderen,
je oom, Dave, je tante, Eva, en je vader, Fred.
U bent enig kind Fred's.
>> Waarom zou het organiseren van uw familieleden op deze manier
beter zijn dan de eenvoudige lijst voorstelling?
Een reden is dat deze hiërarchische structuur,
heet een 'boom', bevat meer informatie dan een eenvoudige lijst.
We kennen de familiale relaties tussen iedereen
alleen door onderzoek van de boom.
Ook kan het versnellen
look-up tijd enorm, als boom gegevens worden gesorteerd.
>> We kunnen niet profiteren van dat hier, maar we zullen hier een voorbeeld van snel te zien.
Elke persoon wordt vertegenwoordigd door een knooppunt op de boom.
Knooppunten kunnen child nodes
en een bovenliggende knooppunt.
Dit zijn de technische termen,
zelfs bij gebruik van bomen voor dingen naast gezinnen.
Alice's knooppunt heeft 2 kinderen en geen ouders,
terwijl Charlie's knooppunt heeft 3 kinderen en 1 ouder.
>> Een blad knooppunt is er een die niet hoeft geen kinderen
aan de buitenkant van de boom.
De bovenste knoop van de boom, de root node,
heeft geen ouder.
>> Een binaire boom is een specifiek type boom
waarbij elke knoop hooguit 2 kinderen.
Hier is de struct een knooppunt van een binaire boom in C.
Elk knooppunt heeft een aantal gegevens in verband met het
en 2 pointers naar andere knooppunten.
>> In onze stamboom,
de bijbehorende gegevens was ieders naam.
Hier is het een int, maar het kan van alles zijn.
Het blijkt dat,
een binaire boom zou niet een goede weergave voor een gezin,
omdat mensen hebben vaak meer dan 2 kinderen.
>> Een binaire zoekboom
is een speciaal, geordende type binaire boom
die ons in staat stelt om snel te kijken naar waarden.
Je hebt misschien gemerkt
dat elke knoop onder de wortel van een boom
is de wortel van een andere boom, een zogenaamde 'substructuur.'
Hier, de wortel van de boom is 6,
en haar kind, 2, is de wortel van een tak.
>> In een binaire zoekboom
alle waarden van een knooppunt is rechter deelboom
groter zijn dan de waarde van het knooppunt. Hier: 6.
Nou, de waarden in de linker een knooppunt substructuur
zijn minder dan de waarde van het knooppunt.
Als we moeten dubbele waarden te behandelen,
we een van deze veranderen in een losse ongelijkheid
wat betekent dat identieke waarden kan vallen op de links of rechts,
zolang we consequent in het hele gebouw.
Deze boom is een binaire zoekboom
omdat het volgt deze regels.
>> Dit is hoe het eruit zou zien als we allemaal de knooppunten veranderd in C structs.
Merk op dat als een kind wordt vermist,
de aanwijzer is null.
Hoe kunnen we controleren of 7 is in de boom?
We beginnen bij de wortel.
Zeven is groter dan 6, dus als het in de boom, moet het naar rechts.
Dan is minder dan 8, dus het moet worden gelaten.
Hier hebben wij gevonden 7.
Nu gaan we controleren 5.
Vijf is minder dan 6, dus het moet aan de linkerkant.
Vijf groter is dan 2,
dus het moet goed zijn,
en is ook groter dan 4, dus moet rechts.
Er is echter geen kind hier.
De aanwijzer is null.
Dit betekent dat 5 niet in de boom.
>> We kunnen zoeken in de binaire boom met de volgende code:
Bij elke knoop, kijken we of we hebben gevonden
de waarde die we zoeken.
Als we het niet vinden, wij bepalen of het zou moeten zijn
aan de linker-of rechts en controleer of substructuur.
Deze lus blijft de boom
totdat er geen kindknoop zowel links of rechts.
>> Vergeet niet dat 5 niet in de boom.
Hoe kunnen we voegen het?
Het proces lijkt op te zoeken.
We herhalen de boom vanaf 6,
overgelaten aan 2,
recht op 4,
en weer rechts, maar 4 heeft geen kind aan deze kant.
Dit wordt de nieuwe positie 5 is,
en het zal beginnen zonder kinderen.
>> Hoe snel zijn activiteiten op een binaire zoekboom?
Anders Bigohnotation beoogt een bovengrens.
In het ergste geval,
onze boom kan gewoon een gelinkte lijst
waardoor insertie, deletie en zoeken
zou kunnen tijd evenredig met het aantal knopen in de boom.
Dit is O (n).
>> Bijvoorbeeld, de volgende is geldig binaire zoekboom.
Echter, als we proberen tot 9 te vinden,
we iedere knooppunt doorkruisen.
Het is niet beter dan een gelinkte lijst.
Idealiter zouden we willen dat elke knoop
van onze binaire zoekboom tot en met 2 kinderen te krijgen.
Zo insertie, deletie en search
zou, in het slechtste geval, O (log n) tijd.
De boom van voor zou kunnen zijn evenwichtiger,
als dit.
Nu kijken elke waarde neemt hooguit 3 stappen.
Deze boom is evenwichtig,
betekenis die een minimale diepte
opzichte van het aantal knooppunten.
>> Op zoek naar een waarde in een gebalanceerde binaire zoekboom
is vergelijkbaar met binair zoeken op een gesorteerde array.
In feite, als we niet nodig om in te voegen of te verwijderen items,
gedragen ze zich precies hetzelfde.
Echter een boomstructuur beter
voor de behandeling inserties en deleties
>> Mijn naam is Bannus Van der Kloot.
Dit is CS50.