Binary search trees understøtter tre hovedoperationer: indsættelse af elementer, sletning af elementer og opslag (kontrol af, om en nøgle er til stede).

SearchingEdit

søgning i et binært søgetræ efter en bestemt nøgle kan programmeres rekursivt eller iterativt.

Vi begynder med at undersøge rodnoden. Hvis træet er null, findes nøglen, vi søger efter, ikke i træet. Ellers, hvis nøglen er lig med roden, er søgningen vellykket, og vi returnerer noden. Hvis nøglen er mindre end roden, søger vi den venstre undertræ., Tilsvarende, hvis nøglen er større end roden, søger vi den rigtige undertræ. Denne proces gentages, indtil nøglen er fundet, eller den resterende undertræ er null. Hvis den søgte nøgle ikke findes, efter at en null-undertræ er nået, er nøglen ikke til stede i træet. Dette udtrykkes let som en rekursiv algoritme (implementeret i Python):

den samme algoritme kan implementeres iterativt:

disse to eksempler understøtter ikke duplikater, det vil sige, de er afhængige af, at ordreforholdet er en samlet ordre.

man kan bemærke, at den rekursive algoritme er Hale rekursiv., I et sprog, der understøtter haleoptimering, kompileres de rekursive og iterative eksempler til tilsvarende programmer.da denne algoritme i værste fald skal søge fra træets rod til det blad, der er længst væk fra roden, tager søgeoperationen tid proportional med træets højde (se træterminologi). I gennemsnit binære søgning træer med noder nøgler har o(log |noder|) højde. I værste fald kan binære søgetræer dog have O(|noder|) højde, når det ubalancerede træ ligner en linket liste (degenereret træ).,

søgning med dubletter allo .ededit

Hvis ordreforholdet kun er en total forudbestilling, er en rimelig udvidelse af funktionaliteten følgende: også i tilfælde af ligestillingssøgning ned til bladene. Derved giver mulighed for at angive (eller hard-wireire) en retning, hvor at indsætte en dublet, enten til højre eller venstre for alle dubletter i træet hidtil. Hvis retningen er kabelforbundet, Understøtter begge valg, højre og venstre, en stak med Indsæt duplikat som push-betjening og slet som pop-operationen.,: 155

en binær træsort udstyret med en sådan søgefunktion bliver stabil.

InsertionEdit

indsættelse begynder som en søgning ville begynde; hvis nøglen ikke er lig med roden, søger vi venstre eller højre undertræer som før. Til sidst når vi en ekstern knude og tilføjer det nye nøgleværdipar (her kodet som en rekord ‘ne .node’) som dets højre eller venstre barn, afhængigt af nodens nøgle., Med andre ord undersøger vi roden og rekursivt indsætter den nye knude til venstre undertræ, hvis dens nøgle er mindre end roden, eller den højre undertræ, hvis dens nøgle er større end eller lig med roden.

sådan kan en typisk indsættelse af binært søgetræ udføres i et binært træ i C++:

Alternativt kan en ikke-rekursiv version implementeres som denne., Ved hjælp af en pointer-til-pointer for at holde styr på, hvor vi kom fra, lader koden undgå eksplicit kontrol af og håndtering af sagen, hvor den skal indsætte en knude ved træroden:

ovenstående destruktive procedurevariant ændrer træet på plads. Det bruger kun konstant bunke plads (og den iterative version bruger konstant stak plads samt), men den tidligere version af træet er tabt., Alternativt kan der, som i de følgende Python eksempel, vi kan rekonstruere alle forfædre indsat knude; enhver henvisning til den oprindelige træet rod forbliver gyldige, hvilket gør træet en vedvarende datastruktur:

Den del, der er genopbygget bruger O(log n) plads i den gennemsnitlige sag, og O(n) i værste fald.

i begge versioner kræver denne operation tid proportional med træets højde i værste tilfælde, hvilket er O(log n) Tid i gennemsnit for alle træer, men O(n) tid i værste tilfælde.,

en anden måde at forklare indsættelse på er, at for at indsætte en ny knude i træet sammenlignes dens nøgle først med roden. Hvis dens nøgle er mindre end rodens, sammenlignes den derefter med nøglen til rodens venstre barn. Hvis nøglen er større, sammenlignes den med rodets rigtige barn. Denne proces fortsætter, indtil den nye knude sammenlignes med en bladknude, og derefter tilføjes den som denne knude højre eller venstre barn, afhængigt af dens nøgle: hvis nøglen er mindre end bladets nøgle, indsættes den som bladets venstre barn, ellers som bladets højre barn.,

Der er andre måder at indsætte knuder i et binært træ på, men det er den eneste måde at indsætte knuder på bladene og samtidig bevare BST-strukturen.

DeletionEdit

Når du fjerner en node fra et binært søgetræ, er det obligatorisk at opretholde nodernes rækkefølge. Der er mange muligheder for at gøre dette. Men den følgende metode, som er blevet foreslået af T. Hibbard i 1962 garanterer, at højden af emnet undertræer er ændret ved højst ét., Der er tre mulige tilfælde at overveje:

• sletning af en node uden børn: fjern blot noden fra træet.
• sletning af en node med et barn: fjern noden og udskift den med sit barn.
• sletning af en node D med to børn: vælg enten D ‘ S i orden forgænger eller i orden efterfølger E (se figur). I stedet for at slette D, Overskriv dens nøgle og værdi med E ‘er. Hvis E ikke har et barn, skal du fjerne E fra sin tidligere forælder G. Hvis E har et barn F, er det et rigtigt barn, så det skal erstatte E hos e’ s forælder.,

i alle tilfælde, når D tilfældigvis er roden, skal du foretage udskiftningsnoden rod igen.

noder med to børn er sværere at slette., En knudepunkts efterfølger i orden er dens højre undertræs venstre mest barn, og en knudepunkts i orden forgænger er den venstre undertræs højre mest barn. I begge tilfælde vil denne knude kun have et eller intet barn overhovedet. Slet det i henhold til et af de to enklere tilfælde ovenfor.

konsekvent brug af efterfølgeren i orden eller forgængeren i orden for hver forekomst af to-barn-sagen kan føre til et ubalanceret træ, så nogle implementeringer vælger den ene eller den anden på forskellige tidspunkter.,Runtime analysis: selvom denne operation ikke altid krydser træet ned til et blad, er dette altid en mulighed; i værste fald kræver det tid proportional med træets højde. Det kræver ikke mere, selv når knuden har to børn, da den stadig følger en enkelt sti og ikke besøger nogen knude to gange.,

TraversalEdit

Når binary search tree er blevet oprettet, er dens elementer kan hentes i rækkefølge ved rekursivt gennemkører det venstre undertræ af root node, adgang til knuden selv, så rekursivt gennemkører højre undertræ af den node, fortsætter dette mønster med hver node i træet, som det er rekursivt adgang til det. Som med alle binære træer, man kan foretage en pre-order traversal eller en post-order traversal, men hverken vil sandsynligvis være nyttige for binære søgning træer., En in-order traversal af en binær søgning træ vil altid resultere i en sorteret liste over node elementer (tal, strenge eller andre sammenlignelige elementer).

koden for in-order traversal i Python er angivet nedenfor. Det vil kalde tilbagekald (nogle funktion programmøren ønsker at kalde på noden værdi, såsom udskrivning til skærmen) for hver node i træet.Traversal kræver O(n) tid, da det skal besøge hver node. Denne algoritme er også O( N), så den er asymptotisk optimal.

Traversal kan også implementeres iterativt. Til visse anvendelser, f. eks., større lige søgning, tilnærmelsesvis søgning, en operation for enkelt trin (iterativ) traversal kan være meget nyttig. Dette er naturligvis implementeret uden tilbagekald konstruktion og tager O (1) i gennemsnit og O(log n) i værste fald.

Verifikationrediger

Nogle gange har vi allerede et binært træ, og vi skal afgøre, om det er en BST. Dette problem har en simpel rekursiv løsning.,

BST—ejendommen—hver knude på højre undertræ skal være større end den aktuelle knude, og hver knude på venstre undertræ skal være mindre end den aktuelle knude-er nøglen til at finde ud af, om et træ er en BST eller ej. Den grådige algoritme-simpelthen krydse træet, ved hver knude kontrollere, om noden indeholder en værdi større end værdien på venstre barn og mindre end værdien på højre barn—virker ikke for alle tilfælde., Overvej følgende træ:

 20 / \ 10 30 / \ 5 40

I træet ovenfor, hver node opfylder den betingelse, at den knude indeholder en værdi, der er større end dens venstre barn og mindre end sin rigtige barn hold, og alligevel er det ikke en BST: værdien 5 er på højre undertræ af den node, der indeholder 20, en krænkelse af BST ejendom.

i stedet for at tage en beslutning, der udelukkende er baseret på værdierne for en knude og dens børn, har vi også brug for information, der strømmer ned fra forælderen., I tilfælde af træet ovenfor, hvis vi kunne huske om noden, der indeholder værdien 20, ville vi se, at noden med værdi 5 overtræder BST-ejendomskontrakten.,

Så den tilstand, vi skal ind på hver enkelt node er:

• hvis noden er det venstre barn af sine forældre, så må det være mindre end (eller lig med) den forælder, og det skal passere ned i værdi fra moderselskabet til højre undertræ til at sikre, at ingen af knuderne i, at undertræ er større end den forælder
• hvis noden er det rigtige barn af sine forældre, så må det være større end den forælder, og det skal passere ned i værdi fra moderselskabet til venstre undertræ til at sikre, at ingen af knuderne i, at undertræ er mindre end den overordnede.,

En rekursiv løsning i C++ kan forklare dette yderligere:

node->key+1 og node->key-1 er gjort til kun at tillade forskellige elementer i BST.

Hvis vi ønsker, at de samme elementer også skal være til stede, kan vi kun bruge node->key begge steder.

Det første opkald for at denne funktion kan være noget lignende dette:

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

grundlæggende har vi at skabe en gyldig interval (fra ) og holde det faldende ned for hver node, som vi går rekursivt ned.,

som påpeget i afsnit #Traversal returnerer en ordre-traversal af et binært søgetræ de sorterede noder. Således behøver vi kun at beholde den sidst besøgte knude, mens vi krydser træet og kontrollere, om nøglen er mindre (eller mindre/lige, hvis duplikater skal tillades i træet) sammenlignet med den aktuelle nøgle.

Parallel algorithmsEdit

Der er også parallelle algoritmer for binær søgning træer, herunder indsætte/slette flere elementer, konstruktion fra array, filter med visse predicator, tromle til et array, sammenlægning/substracting/skærende to træer, osv., Disse algoritmer kan implementeres ved hjælp af join-baseret træ algoritmer, som også kan holde træet afbalanceret ved hjælp af flere balancing ordninger (herunder AVL-træ, rød-sort træ, vægt-balanceret træ og treap) .