binaire zoekboom ondersteunt drie hoofdbewerkingen: invoegen van elementen, verwijderen van elementen en opzoeken (controleren of er een sleutel aanwezig is).

SearchingEdit

het zoeken in een binaire zoekboom naar een specifieke sleutel kan recursief of iteratief worden geprogrammeerd.

we beginnen met het onderzoeken van de root node. Als de boom null is, bestaat de sleutel die we zoeken niet in de boom. Anders, als de sleutel gelijk is aan die van de root, is de zoekopdracht succesvol en geven we het knooppunt terug. Als de sleutel kleiner is dan die van de root, zoeken we naar de linker subboom., Op dezelfde manier, als de sleutel groter is dan die van de wortel, zoeken we de juiste subboom. Dit proces wordt herhaald totdat de sleutel is gevonden of de resterende subboom is null. Als de gezochte sleutel niet wordt gevonden nadat een null-subboom is bereikt, dan is de sleutel niet aanwezig in de boomstructuur. Dit wordt gemakkelijk uitgedrukt als een recursief algoritme (geà mplementeerd in Python):

hetzelfde algoritme kan iteratief worden geà mplementeerd:

deze twee voorbeelden ondersteunen geen duplicaten, dat wil zeggen, ze vertrouwen erop dat de orderrelatie een totale orde is.

men kan opmerken dat het recursieve algoritme tail recursief is., In een taal die tail call optimalisatie ondersteunt, zullen de recursieve en iteratieve voorbeelden compileren naar gelijkwaardige programma ‘ s.

omdat in het ergste geval dit algoritme moet zoeken van de wortel van de boom tot het blad het verst van de wortel, de zoekopdracht duurt evenredig aan de hoogte van de boom (zie boom terminologie). Gemiddeld hebben binaire zoekbomen met Knooppuntentoetsen o (log |Knooppuntentoetsen|) hoogte. Echter, in het ergste geval kunnen binaire zoekbomen o(|Nodes|) hoogte hebben, wanneer de onevenwichtige boom lijkt op een gekoppelde lijst (gedegenereerde boom).,

zoeken met duplicaten allowedEdit

als de orderrelatie slechts een totale pre-volgorde is, is een redelijke uitbreiding van de functionaliteit de volgende: ook in geval van gelijkheid zoeken tot aan de bladeren. Hierdoor kan (of hard-wire) een richting worden opgegeven, waar een duplicaat moet worden ingevoegd, hetzij rechts of links van alle duplicaten in de boom tot nu toe. Als de richting is vast bedraad, beide keuzes, rechts en links, ondersteunen een stack met insert duplicate als push operatie en delete als de pop operatie.,: 155

een binaire boomsoort die met een dergelijke zoekfunctie is uitgerust, wordt stabiel.

InsertionEdit

Insertion begint als een zoekopdracht zou beginnen; als de sleutel niet gelijk is aan die van de root, zoeken we de linker of rechter subbomen zoals hiervoor. Uiteindelijk zullen we een extern knooppunt bereiken en het nieuwe sleutel-waarde paar (hier gecodeerd als een record ‘newNode’) toevoegen als zijn rechter-of linker kind, afhankelijk van de sleutel van het knooppunt., Met andere woorden, we onderzoeken de root en voegen recursief de nieuwe knoop toe aan de linker subtree als de sleutel kleiner is dan die van de root, of de rechter subtree als de sleutel groter is dan of gelijk is aan de root.

Hier is hoe een typische binaire zoekboominvoeging kan worden uitgevoerd in een binaire boom in c++:

alternatief kan een niet-recursieve versie op deze manier worden geïmplementeerd., Door een pointer-to-pointer te gebruiken om bij te houden waar we vandaan komen, vermijdt de code expliciete controle op en afhandeling van de zaak waar het een knooppunt in de boomwortel moet invoegen:

de bovenstaande destructieve procedurele variant wijzigt de boomstructuur. Het gebruikt alleen constante heap ruimte (en de iteratieve versie maakt gebruik van constante stack ruimte ook), maar de eerdere versie van de boom is verloren., Als alternatief, zoals in het volgende Python voorbeeld, kunnen we alle voorouders van het ingevoegde knooppunt reconstrueren; elke verwijzing naar de oorspronkelijke boomwortel blijft geldig, waardoor de boom een blijvende gegevensstructuur wordt:

het deel dat wordt herbouwd gebruikt O(log n) ruimte in het gemiddelde geval en O(n) in het slechtste geval.

in beide versies vereist deze bewerking tijd evenredig aan de hoogte van de boom in het slechtste geval, dat is O(log n) tijd in het gemiddelde geval van alle bomen, maar O(n) tijd in het slechtste geval.,

een andere manier om insertie uit te leggen is dat om een nieuw knooppunt in de boom in te voegen, de sleutel eerst wordt vergeleken met die van de root. Als de sleutel kleiner is dan die van de root, wordt deze vergeleken met de sleutel van het linker kind van de root. Als de sleutel groter is, wordt het vergeleken met het juiste kind van de wortel. Dit proces gaat door, totdat de nieuwe knoop wordt vergeleken met een bladknoop, en dan wordt toegevoegd als het rechter of linker kind van deze knoop, afhankelijk van de sleutel: als de sleutel kleiner is dan de sleutel van het blad, dan wordt het ingevoegd als het linker kind van het blad, anders als het rechter kind van het blad.,

er zijn andere manieren om knopen in een binaire boom in te voegen, maar dit is de enige manier om knopen in de bladeren in te voegen en tegelijkertijd de BST-structuur te behouden.

DeletionEdit

bij het verwijderen van een knooppunt uit een binaire zoekboom is het verplicht om de volgorde van de knooppunten te behouden. Er zijn vele mogelijkheden om dit te doen. De volgende methode, die door T. Hibbard in 1962 werd voorgesteld, garandeert echter dat de hoogte van de subtaken ten hoogste één keer wordt gewijzigd., Er zijn drie mogelijke gevallen om rekening mee te houden:

• Een knooppunt zonder kinderen verwijderen: verwijder eenvoudig de knooppunt uit de boomstructuur.
• een knooppunt met één dochter verwijderen: verwijder het knooppunt en vervang het door zijn dochter.
• Een knooppunt d verwijderen met twee kinderen: kies D ‘ s in-order voorganger of in-order opvolger E (zie figuur). In plaats van D te verwijderen, overschrijft u de sleutel en waarde met E ‘s. als E geen kind heeft, verwijdert u E van de vorige ouder G. Als E Een kind F heeft, is het een juist kind, zodat het E vervangt bij E’ S ouder.,

in alle gevallen, als D de root is, maak dan de vervangende node root opnieuw.

knopen met twee kinderen zijn moeilijker te verwijderen., De opvolger van een knooppunt is het meest linkse kind van de rechter subtree, en de voorganger van een knooppunt is het meest rechtse kind van de linker subtree. In beide gevallen zal dit knooppunt slechts één of helemaal geen kind hebben. Verwijder het volgens een van de twee eenvoudiger gevallen hierboven.

het consequent gebruiken van de in-order opvolger of de in-order voorganger voor elke instantie van de twee-kind zaak kan leiden tot een onevenwichtige boom, dus sommige implementaties selecteren de ene of de andere op verschillende tijdstippen.,

Runtime analyse: hoewel deze bewerking niet altijd de boom naar beneden naar een blad doorkruist, is dit altijd een mogelijkheid; dus in het ergste geval vereist het tijd evenredig aan de hoogte van de boom. Het vereist niet meer, zelfs als het knooppunt twee kinderen heeft, omdat het nog steeds een enkel pad volgt en geen knooppunt tweemaal bezoekt.,

TraversalEdit

zodra de binaire zoekboom is aangemaakt, kunnen de elementen ervan op volgorde worden opgehaald door recursief de linker subboom van het rootknooppunt te doorlopen, het knooppunt zelf te benaderen, en vervolgens recursief de rechter subboom van het knooppunt te doorlopen, dit patroon voort te zetten met elk knooppunt in de boom als het recursief wordt benaderd. Zoals bij alle binaire bomen, kan men een pre-order traversal of een post-order traversal uitvoeren, maar geen van beide zijn waarschijnlijk nuttig voor binaire zoek bomen., Een in-order traversal van een binaire zoekboom zal altijd resulteren in een gesorteerde lijst van knooppuntitems (getallen, tekenreeksen of andere vergelijkbare items).

de code voor in-order traversal in Python wordt hieronder gegeven. Het zal callback (sommige functie die de programmeur wil aanroepen op de waarde van het knooppunt, zoals afdrukken naar het scherm) voor elke knooppunt in de boom noemen.

Traversal vereist o (n) tijd, omdat het elk knooppunt moet bezoeken. Dit algoritme is ook O (n), dus het is asymptotisch optimaal.

Traversal kan ook iteratief worden geïmplementeerd. Voor bepaalde toepassingen, bijv., groter gelijk zoeken, approximatief zoeken, een operatie voor enkele stap (iteratieve) traversal kan zeer nuttig zijn. Dit is natuurlijk geïmplementeerd zonder de callback constructie en neemt gemiddeld o(1) en o(log n) in het slechtste geval.

VerificationEdit

soms hebben we al een binaire boom, en we moeten bepalen of het een BST is. Dit probleem heeft een eenvoudige recursieve oplossing.,

de eigenschap BST-elk knooppunt in de rechter subboom moet groter zijn dan het huidige knooppunt en elk knooppunt in de linker subboom moet kleiner zijn dan het huidige knooppunt—is de sleutel om uit te zoeken of een boom een BST is of niet. Het hebzuchtige algoritme-gewoon de boom doorlopen, op elk knooppunt controleren of het knooppunt bevat een waarde groter dan de waarde bij het linker kind en kleiner dan de waarde op het rechter kind—werkt niet voor alle gevallen., Overweeg de volgende boom:

 20 / \ 10 30 / \ 5 40

in de boom hierboven voldoet elk knooppunt aan de voorwaarde dat het knooppunt een waarde bevat die groter is dan zijn linker dochter en kleiner dan zijn rechter dochterhold, en toch is het geen BST: de waarde 5 staat op de rechter subboom van het knooppunt dat 20 bevat, een schending van de BST-eigenschap.

in plaats van een beslissing te nemen die uitsluitend gebaseerd is op de waarden van een knoop en zijn kinderen, hebben we ook informatie nodig die van de ouder naar beneden stroomt., In het geval van de boom hierboven, als we ons konden herinneren over het knooppunt met de waarde 20, zouden we zien dat het knooppunt met waarde 5 het eigendomscontract van BST schendt.,

Dus de voorwaarde moeten we controleren op elk knooppunt is:

• als de node op de linker kind van zijn ouder, dan moet kleiner zijn dan (of gelijk aan) de ouder en het moet gaan vaststelling van de waarde van de ouder aan de rechter deelboom om ervoor te zorgen dat geen van de knooppunten in die deelboom groter is dan de bovenliggende
• als de node op het juiste kind van zijn ouder, dan moet groter zijn dan de ouder en het moet gaan vaststelling van de waarde van zijn ouder te zijn linker deelboom te gebruiken om ervoor te zorgen dat geen van de knooppunten in die substructuur is minder dan de ouder.,

een recursieve oplossing in C++ kan dit verder verklaren:

node->key+1 en node->key-1 worden gedaan om alleen afzonderlijke elementen in BST toe te staan.

als we willen dat dezelfde elementen ook aanwezig zijn, dan kunnen we alleen node->key op beide plaatsen gebruiken.

de eerste aanroep van deze functie kan ongeveer als volgt zijn:

if (isBST(root, INT_MIN, INT_MAX)) { puts("This is a BST.");} else { puts("This is NOT a BST!");}

in wezen blijven we een geldig bereik maken (beginnend vanaf ) en blijven het krimpen voor elke node terwijl we recursief naar beneden gaan.,

zoals aangegeven in sectie # Traversal, geeft een in-volgorde traversal van een binaire zoekboom de gesorteerde knooppunten terug. We hoeven dus alleen het laatst bezochte knooppunt te behouden tijdens het doorlopen van de boomstructuur en te controleren of de sleutel kleiner is (of kleiner/Gelijk, als duplicaten in de boom moeten worden toegestaan) in vergelijking met de huidige sleutel.

Parallel algoritmsedit

Er zijn ook parallelle algoritmen voor binaire zoekbomen, waaronder het invoegen / verwijderen van meerdere elementen, constructie Uit array, filter met bepaalde voorspeller, plat tot een array, samenvoegen/substracteren/snijden van twee bomen, enz., Deze algoritmen kunnen worden geà mplementeerd met behulp van join – gebaseerde tree algoritmen, die ook de boom in evenwicht kunnen houden met behulp van verschillende balanceringsschema ‘ s (waaronder AVL tree, red-black tree, weight-balanced tree en treap) .