Binaire zoekboom - een gestructureerde database met knooppunten, twee links naar andere knooppunten, rechts en links. Knooppunten zijn een object van de klasse die gegevens heeft, en NULL is het teken dat het einde van de boom aangeeft.
Het wordt vaak BST genoemd, wat een speciale eigenschap heeft: knopen die groter zijn dan de wortel bevinden zich rechts ervan en kleinere links.
Algemene theorie en terminologie
In een binaire zoekboom is elk knooppunt, met uitzondering van de wortel, verbonden door een gerichte rand van het ene knooppunt naar het andere, die de ouder wordt genoemd. Elk van hen kan worden verbonden met een willekeurig aantal knooppunten, kinderen genoemd. Knopen zonder "kinderen" worden bladeren (buitenknopen) genoemd. Elementen die geen bladeren zijn, worden intern genoemd. Knooppunten met dezelfde ouder zijn broers en zussen. Het bovenste knooppunt wordt de wortel genoemd. Wijs in BST een element toe aan elk knooppunt en zorg ervoor dat er een speciale eigenschap voor is ingesteld.
Boomterminologie:
- De diepte van een knoop is het aantal randen dat is gedefinieerd vanaf de wortel tot eraan.
- Hoogte van een knoop is het aantal randen dat er vanaf is gedefinieerd tot aan het diepste blad.
- De hoogte van de boom wordt bepaald door de hoogte van de wortel.
- Binaire zoekboom is een speciaal ontwerp, het biedt de beste verhouding tussen hoogte en aantal knooppunten.
- Hoogte h met maximaal N knopen O (log N).
Je kunt dit eenvoudig bewijzen door de knopen op elk niveau te tellen, beginnend bij de wortel, ervan uitgaande dat deze het grootste aantal bevat: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Dit oplossen voor h geeft h=O (log n).
Voordelen van hout:
- Weerspiegel de structurele relaties van de gegevens.
- Wordt gebruikt om hiërarchieën weer te geven.
- Zorg voor een efficiënte installatie en zoekactie.
- Bomen zijn zeer flexibele gegevens, waardoor u subbomen met minimale inspanning kunt verplaatsen.
Zoekmethode
In het algemeen, om te bepalen of een waarde in de BST staat, start u een binaire zoekboom bij de wortel en bepa alt u of deze aan de vereisten voldoet:
- wees bij de wortel;
- be in de linker subboom van root;
- in de rechter subboom van root.
Als aan geen basisregister is voldaan, wordt een recursieve zoekopdracht uitgevoerd in de overeenkomstige subboom. Er zijn eigenlijk twee basisopties:
- De boom is leeg - retourneer false.
- De waarde bevindt zich in het hoofdknooppunt - return true.
Opgemerkt moet worden dat een binaire zoekboom met een ontwikkeld schema altijd begint te zoeken langs het pad van de wortel naar het blad. In het ergste geval gaat het helemaal tot aan het blad. Daarom is de slechtste tijd evenredig met de lengte van het langste pad van de wortel naar het blad, de hoogte van de boom. Over het algemeen is dit het moment waarop u moet weten hoe lang het duurt om op te zoeken als functie van het aantal waarden dat in de boom is opgeslagen.
Met andere woorden, er is een relatie tussen het aantal knopen in een BST en de hoogte van een boom, afhankelijk van zijn "vorm". In het ergste geval hebben knooppunten slechts één kind en is een gebalanceerde binaire zoekboom in wezen een gekoppelde lijst. Bijvoorbeeld:
50
/
10
15
30
/
20
Deze boom heeft 5 knooppunten en hoogte=5. Het vinden van waarden in het bereik 16-19 en 21-29 vereist het volgende pad van de wortel naar het blad (het knooppunt met de waarde 20), d.w.z., het zal tijd kosten die evenredig is aan het aantal knooppunten. In het beste geval hebben ze allemaal 2 kinderen en bevinden de bladeren zich op dezelfde diepte.
Deze binaire zoekboom heeft 7 knopen en hoogte=3. Over het algemeen zal een boom als deze (volledige boom) een hoogte hebben van ongeveer log 2 (N), waarbij N het aantal knopen in de boom is. De waarde van log 2 (N) is het aantal keren (2) dat N kan worden gedeeld voordat nul is bereikt.
Samenvattend: de slechtste tijd die nodig is om in BST te zoeken is O (boomhoogte). De "lineaire" boom in het slechtste geval is O(N), waarbij N het aantal knopen in de boom is. In het beste geval is een "complete" boom O(log N).
BST binaire insert
Vraagt u zich af waar zou moeten zijnhet nieuwe knooppunt bevindt zich in de BST, u moet de logica begrijpen, het moet worden geplaatst waar de gebruiker het vindt. Bovendien moet u de regels onthouden:
- Duplicaten zijn niet toegestaan, een poging om een dubbele waarde in te voegen leidt tot een uitzondering.
- De openbare invoegmethode gebruikt een recursieve helper-"helper"-methode om daadwerkelijk in te voegen.
- Een knoop met een nieuwe waarde wordt altijd ingevoegd als een blad in BST.
- De public insert-methode retourneert void, maar de helper-methode retourneert een BSTnode. Het doet dit om het geval af te handelen waarin het knooppunt dat eraan wordt doorgegeven, null is.
Over het algemeen geeft de helpermethode aan dat als de oorspronkelijke binaire zoekboom leeg is, het resultaat een boom met één knoop is. Anders is het resultaat een verwijzing naar hetzelfde knooppunt dat als argument is doorgegeven.
Verwijderen in binair algoritme
Zoals je zou verwachten, omvat het verwijderen van een element het vinden van een knoop die de waarde bevat die moet worden verwijderd. Er zijn verschillende dingen in deze code:
- BST gebruikt een helper, overbelaste verwijdermethode. Als het element dat u zoekt niet in de boom voorkomt, wordt de helpermethode uiteindelijk aangeroepen met n==null. Dit wordt niet als een fout beschouwd, de boom verandert in dit geval gewoon niet. De verwijderhulpmethode retourneert een waarde - een verwijzing naar de bijgewerkte boomstructuur.
- Wanneer een blad wordt verwijderd, stelt het verwijderen uit de binaire zoekboom de corresponderende onderliggende aanwijzer van zijn ouder in op null, of de root op null als degene die wordt verwijderd ishet knooppunt is een root en heeft geen kinderen.
- Merk op dat de delete-aanroep een van de volgende moet zijn: root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight(), sleutel)). Dus in alle drie de gevallen is het juist dat de delete-methode gewoon null retourneert.
- Als het zoeken naar het knooppunt met de te verwijderen waarde slaagt, zijn er drie opties: het te verwijderen knooppunt is een blad (heeft geen kinderen), het te verwijderen knooppunt heeft één kind, het heeft er twee kinderen.
- Als het verwijderde knooppunt één kind heeft, kunt u het eenvoudig vervangen door een kind, waardoor een aanwijzer naar het kind wordt teruggestuurd.
- Als het te verwijderen knooppunt nul of 1 kinderen heeft, dan zal de verwijdermethode "het pad volgen" van de hoofdmap naar dat knooppunt. Dus de slechtste tijd is evenredig met de hoogte van de boom, voor zowel zoeken als invoegen.
Als het te verwijderen knooppunt twee kinderen heeft, worden de volgende stappen genomen:
- Zoek het knooppunt dat moet worden verwijderd door het pad van de wortel ernaartoe te volgen.
- Zoek de kleinste waarde van v in de rechter subboom, verder langs het pad naar het blad.
- Verwijder recursief de waarde van v, volg hetzelfde pad als in stap 2.
- Dus in het ergste geval wordt het pad van de wortel naar het blad twee keer uitgevoerd.
Volgorde van traverses
Traversal is een proces dat alle knooppunten in een boom bezoekt. Omdat een C binaire zoekboom een niet-lineaire datastructuur is, is er geen unieke traversal. Bijvoorbeeld, soms meerdere traversal-algoritmengegroepeerd in de volgende twee typen:
- oversteekdiepte;
- eerste pas.
Er is maar één soort breedtekruising - het niveau omzeilen. Deze traversal bezoekt knooppunten naar beneden en naar links, boven en naar rechts.
Er zijn drie verschillende soorten diepteovergangen:
- Vooruitbestelling doorgeven - bezoek eerst de ouder en dan het linker en rechter kind.
- Passing InOrder - het linkerkind bezoeken, dan de ouder en het rechterkind.
- Voorbij de PostOrder - een bezoek aan het linkerkind, dan het rechterkind, dan de ouder.
Voorbeeld van vier doorgangen van een binaire zoekboom:
- Voorbestelling - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
De afbeelding toont de volgorde waarin knooppunten worden bezocht. Het nummer 1 is het eerste knooppunt in een bepaalde traversal en 7 is het laatste knooppunt.
Deze algemene verplaatsingen kunnen worden weergegeven als een enkel algoritme, ervan uitgaande dat elk knooppunt drie keer wordt bezocht. De Euler-tour is een wandeling rond een binaire boom waarbij elke rand wordt behandeld als een muur die de gebruiker niet kan oversteken. In deze wandeling wordt elk knooppunt aan de linkerkant, of aan de onderkant of aan de rechterkant bezocht. De Euler-tour, die de knooppunten aan de linkerkant bezoekt, zorgt ervoor dat het voorzetsel wordt omzeild. Wanneer de onderstaande knooppunten worden bezocht, worden ze op volgorde doorlopen. En wanneer de knooppunten aan de rechterkant worden bezocht - getstap-voor-stap bypass.
Navigatie en foutopsporing
Om het gemakkelijker te maken om door de boom te navigeren, maakt u functies die eerst controleren of ze het linker- of rechterkind zijn. Om de positie van een knooppunt te wijzigen, moet er gemakkelijke toegang zijn tot de aanwijzer op het bovenliggende knooppunt. Het correct implementeren van een boomstructuur is erg moeilijk, dus u moet debugging-processen kennen en toepassen. Een binaire zoekboom met een implementatie heeft vaak pointers die niet echt de reisrichting aangeven.
Om dit allemaal uit te zoeken, wordt een functie gebruikt die controleert of de boom correct kan zijn, en helpt om veel fouten te vinden. Het controleert bijvoorbeeld of het bovenliggende knooppunt een onderliggend knooppunt is. Met assert(is_wellformed(root)) kunnen veel fouten voortijdig worden ontdekt. Met behulp van een aantal gegeven breekpunten binnen deze functie, kunt u ook precies bepalen welke aanwijzer fout is.
Functie Konsolenausgabe
Deze functie spoelt de hele boom naar de console en is daarom erg handig. De volgorde waarin het doel van de boomuitvoer wordt uitgevoerd is:
- Om dit te doen, moet u eerst bepalen welke informatie via het knooppunt wordt uitgevoerd.
- En je moet ook weten hoe breed en hoog de boom is om rekening te houden met hoeveel ruimte je moet laten.
- De volgende functies berekenen deze informatie voor de boom en elke subboom. Aangezien u alleen regel voor regel naar de console kunt schrijven, moet u ook de boom regel voor regel afdrukken.
- Nu hebben we een andere manier nodig om ons terug te trekkende hele boom, niet alleen regel voor regel.
- Met behulp van de dump-functie kun je de boomstructuur lezen en het uitvoeralgoritme aanzienlijk verbeteren, wat betreft snelheid.
Deze functie zal echter moeilijk te gebruiken zijn bij grote bomen.
Copy constructor en destructor
Omdat een boom geen triviale gegevensstructuur is, is het beter om een kopieerconstructor, een destructor en een toewijzingsoperator te implementeren. De destructor is eenvoudig recursief te implementeren. Voor zeer grote bomen kan het "heap overflow" aan. In dit geval is het iteratief geformuleerd. Het idee is om het blad te verwijderen dat de kleinste waarde van alle bladeren vertegenwoordigt, dus aan de linkerkant van de boom. Door de eerste bladeren af te snijden ontstaan er nieuwe en de boom krimpt totdat hij uiteindelijk ophoudt te bestaan.
De kopieerconstructor kan ook recursief worden geïmplementeerd, maar wees voorzichtig als er een uitzondering wordt gegenereerd. Anders wordt de boom snel verwarrend en foutgevoelig. Daarom heeft de iteratieve versie de voorkeur. Het idee is om door de oude boom en de nieuwe boom te gaan, zoals je zou doen in de destructor, en alle knooppunten in de oude boom te klonen, maar niet de nieuwe.
Met deze methode is de implementatie van de binaire zoekboom altijd in een goede staat en kan deze zelfs in een onvolledige staat door de destructor worden verwijderd. Als er een uitzondering optreedt, hoeft u alleen maar de destructor te instrueren om de halfafgewerkte boom te verwijderen. opdracht operatorkan eenvoudig worden geïmplementeerd met behulp van Copy & Swap.
Een binaire zoekboom maken
Optimale binaire zoekbomen zijn ongelooflijk efficiënt als ze goed worden beheerd. Enkele regels voor binaire zoekbomen:
- Een bovenliggende node heeft maximaal 2 onderliggende nodes.
- Het linker onderliggende knooppunt is altijd kleiner dan het bovenliggende knooppunt.
- Een geldige onderliggende node is altijd groter dan of gelijk aan de bovenliggende node.
De array die zal worden gebruikt om de binaire zoekboom te bouwen:
- Een array van gehele getallen met zeven waarden in ongesorteerde volgorde.
- De eerste waarde in de array is 10, dus de eerste stap bij het bouwen van de boom is het maken van een 10 wortelknooppunt, zoals hier getoond.
- Met een set hoofdknooppunten zijn alle andere waarden onderliggende waarden van dit knooppunt. Verwijzend naar de regels, is de eerste stap die moet worden genomen om 7 aan de boom toe te voegen, deze te vergelijken met het hoofdknooppunt.
- Als de waarde 7 kleiner is dan 10, wordt het de linker onderliggende node.
- Als de waarde 7 groter is dan of gelijk is aan 10, zal deze naar rechts verschuiven. Aangezien bekend is dat 7 kleiner is dan 10, wordt het aangeduid als het linker onderliggende knooppunt.
- Recursief vergelijkingen uitvoeren voor elk element.
- Volg hetzelfde patroon en voer dezelfde vergelijking uit met de 14e waarde in de array.
- De waarde 14 vergelijken met de wortelknoop 10, wetende dat 14 het juiste kind is.
- Door de array lopen,kom naar 20.
- Begin met het vergelijken van de array met 10, welke groter is. Dus ga naar rechts en vergelijk het met 14, hij is ouder dan 14 en heeft geen kinderen aan de rechterkant.
- Nu is er een waarde van 1. Volg hetzelfde patroon als de andere waarden, vergelijk 1 met 10, beweeg naar links en vergelijk met 7 en tenslotte met het 1 linker kind van de 7e knoop.
- Als de waarde 5 is, vergelijk het dan met 10. Aangezien 5 kleiner is dan 10, ga naar links en vergelijk het met 7.
- Weten dat 5 minder dan 7 is, ga verder in de boom en vergelijk 5 met 1 waarde.
- Als 1 geen kinderen heeft en 5 groter is dan 1, dan is 5 een geldige onderliggende waarde van 1 knoop.
- Voer ten slotte de waarde 8 in de boom in.
- Als 8 kleiner is dan 10, verplaats het naar links en vergelijk het met 7, 8 is groter dan 7, dus verplaats het naar rechts en voltooi de boom, waardoor 8 een echt kind van 7 wordt.
De eenvoudige elegantie van optimale binaire zoekbomen verkrijgen en evalueren. Net als veel andere programmeeronderwerpen, komt de kracht van binaire zoekbomen voort uit hun vermogen om gegevens op te lossen in kleine, gerelateerde componenten. Vanaf nu kun je overzichtelijk met de volledige dataset aan de slag.
Potentiële problemen met binair zoeken
Binaire zoekbomen zijn geweldig, maar er zijn een paar kanttekeningen om in gedachten te houden. Ze zijn meestal alleen effectief als ze in balans zijn. Een evenwichtige boom is een boom waarin:het verschil tussen de hoogten van de subbomen van elke knoop in de boom is maximaal één. Laten we een voorbeeld bekijken dat de regels kan helpen verduidelijken. Laten we ons voorstellen dat de array begint als sorteerbaar.
Als u een binair zoekboomalgoritme op deze boom probeert uit te voeren, zal het precies zo werken alsof het door de array heen loopt totdat de gewenste waarde is gevonden. De kracht van binair zoeken ligt in de mogelijkheid om snel ongewenste waarden uit te filteren. Wanneer een boom niet in balans is, biedt hij niet dezelfde voordelen als een evenwichtige boom.
Het is erg belangrijk om de gegevens te onderzoeken waarmee de gebruiker werkt bij het maken van een binaire zoekboom. U kunt routines zoals array-randomisatie integreren voordat u een binaire zoekboom voor gehele getallen implementeert om het uit te balanceren.
Binaire zoekberekeningsvoorbeelden
We moeten bepalen wat voor soort boom het resultaat zal zijn als 25 wordt ingevoegd in de volgende binaire zoekboom:
10
/
/
5 15
/ /
/ /
2 12 20
Bij het invoegen van x in een boom T die nog geen x bevat, wordt de sleutel x altijd in een nieuw blad geplaatst. In verband hiermee ziet de nieuwe boom er als volgt uit:
10
/
/
5 15
/ /
/ /
2 12 20
25
Wat voor soort boom zou je krijgen als je 7 invoegde in de volgende binaire zoekboom?
10
/
/
5 15
/ /
/ /
2 12 20
Antwoord:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
Een binaire zoekboom kan worden gebruikt om elk object op te slaan. Het voordeel van het gebruik van een binaire zoekboom in plaats van een gekoppelde lijst is dat als de boom redelijk gebalanceerd is en meer als een "volledige" boom dan een "lineaire" boom, invoeg-, zoek- en alle verwijderingsbewerkingen kunnen worden geïmplementeerd om te worden uitgevoerd in O(log N) tijd.
