Binary search trees stöder tre huvudsakliga operationer: införande av element, radering av element och lookup (kontrollera om en nyckel är närvarande).

SearchingEdit

sökning i ett binärt sökträd efter en viss nyckel kan programmeras rekursivt eller iterativt.

vi börjar med att undersöka rotnoden. Om trädet är null, finns inte nyckeln vi söker efter i trädet. Annars, om nyckeln är lika med roten, är sökningen framgångsrik och vi returnerar noden. Om nyckeln är mindre än roten söker vi den vänstra undertreen., På samma sätt, om nyckeln är större än roten, söker vi rätt underträd. Denna process upprepas tills nyckeln hittas eller den återstående undertreen är null. Om den sökta nyckeln inte hittas efter att en null-underträd har nåtts, är nyckeln inte närvarande i trädet. Detta uttrycks lätt som en rekursiv algoritm (implementerad i Python):

samma algoritm kan implementeras iterativt:

dessa två exempel stöder inte dubbletter, det vill säga de är beroende av att orderförhållandet är en total order.

man kan notera att den rekursiva algoritmen är svansrekursiv., På ett språk som stöder tail call optimering, kommer rekursiva och iterativa exempel sammanställa motsvarande program.

eftersom den här algoritmen i värsta fall måste söka från trädets rot till bladet längst bort från roten, tar sökoperationen tid proportionell mot trädets höjd (se trädterminologi). I genomsnitt har binära sökträd med Nodnycklar o (log |Nodes|) höjd. Men i värsta fall kan binära Sök Träd ha o (|noder/) höjd, när det obalanserade trädet liknar en länkad lista (degenererat träd).,

söka med dubbletter allowedEdit

om orderrelationen endast är en total förbeställning är en rimlig förlängning av funktionaliteten följande: även vid jämlikhet sök ner till bladen. Därigenom gör det möjligt att ange (eller hård tråd) en riktning, var att infoga en dubblett, antingen till höger eller vänster om alla dubbletter i trädet hittills. Om riktningen är hård trådbunden, stöder både Val, höger och vänster, en stapel med infoga dubblett som tryckoperation och radera som pop-operationen.,: 155

en binär träd Sortera utrustad med en sådan sökfunktion blir stabil.

Infogningedit

infogning börjar som en sökning skulle börja; om nyckeln inte är lika med roten, söker vi vänster eller höger understreck som tidigare. Så småningom kommer vi att nå en extern nod och lägga till det nya nyckelvärdesparet (här kodat som en post ”newNode”) som sitt högra eller vänstra barn, beroende på nodens nyckel., Med andra ord undersöker vi roten och rekursivt sätter in den nya noden till vänster subtree om dess nyckel är mindre än roten, eller den högra subtreen om nyckeln är större än eller lika med roten.

här är hur en typisk binär sökning träd insättning kan utföras i ett binärt träd i c++:

Alternativt kan en icke-rekursiv version genomföras så här., Med hjälp av en pekare till pekare för att hålla reda på var vi kom ifrån kan koden undvika explicit kontroll och hantering av fallet där den behöver infoga en nod vid trädroten:

ovanstående destruktiva procedurvariant ändrar trädet på plats. Den använder endast konstant heap utrymme (och den iterativa versionen använder konstant stack utrymme samt), men den tidigare versionen av trädet går förlorad., Alternativt kan vi, som i följande Python-exempel, rekonstruera alla förfäder till den infogade noden; varje hänvisning till den ursprungliga trädroten förblir giltig, vilket gör trädet till en beständig datastruktur:

den del som ombyggs använder o(log n) utrymme i medelfallet och O(n) i värsta fall.

i endera versionen kräver denna operation tid som är proportionell mot trädets höjd i värsta fall, vilket är o(log n) tid i det genomsnittliga fallet över alla träd, men o(n) tid i värsta fall.,

ett annat sätt att förklara införandet är att för att infoga en ny nod i trädet, är dess nyckel först jämfört med roten. Om dess nyckel är mindre än rotens, jämförs den sedan med nyckeln till rotens vänstra barn. Om nyckeln är större jämförs den med rotens rätta barn. Denna process fortsätter tills den nya noden jämförs med en bladnod, och sedan läggs den till som den här nodens högra eller vänstra barn, beroende på dess nyckel: om nyckeln är mindre än bladets nyckel, sätts den in som bladets vänstra barn, annars som bladets högra barn.,

det finns andra sätt att infoga noder i ett binärt träd, men det här är det enda sättet att infoga noder vid bladen och samtidigt bevara BST-strukturen.

DeletionEdit

När du tar bort en nod från ett binärt sökträd är det obligatoriskt att behålla nodernas ordningsföljd. Det finns många möjligheter att göra detta. Följande metod som T. Hibbard föreslog 1962 garanterar dock att höjderna för subtrees ändras av högst en., Det finns tre möjliga fall att överväga:

• ta bort en nod utan barn: ta bara bort noden från trädet.
• ta bort en nod med ett barn: ta bort noden och ersätt den med sitt barn.
• ta bort en nod D med två barn: välj antingen d: s föregångare i ordning eller i ordning efterträdare E (se figur). I stället för att ta bort D, Skriv över dess nyckel och värde med E: S. om E inte har ett barn, ta bort E från sin tidigare förälder G. Om E har ett barn F är det ett rätt barn, så att det är att ersätta E hos e: s förälder.,

i alla fall, när D råkar vara roten, gör ersättningsnodroten igen.

noder med två barn är svårare att ta bort., En nods in-order-efterträdare är dess högra undertrees vänstra barn, och en nods in-order-föregångare är den vänstra undertrees högra barn. I båda fallen har denna nod bara ett eller inget barn alls. Ta bort det enligt ett av de två enklare fallen ovan.

genom att konsekvent använda in-order-efterträdaren eller in-order-föregångaren för varje instans av tvåbarnsfallet kan det leda till ett obalanserat träd, så vissa implementeringar väljer det ena eller det andra vid olika tidpunkter.,

Runtime analysis: även om denna operation inte alltid passerar trädet ner till ett blad, är detta alltid en möjlighet; således i värsta fall kräver tid proportionell mot trädets höjd. Det kräver inte jämnare när noden har två barn, eftersom det fortfarande följer en enda väg och inte besöker någon nod två gånger.,

TraversalEdit

När det binära sökträdet har skapats kan dess element hämtas i ordning genom att rekursivt korsa rotnodens vänstra underträd, komma åt själva noden och sedan rekursivt korsa nodens högra underträd och fortsätta detta mönster med varje nod i trädet eftersom det rekursivt nås. Som med alla binära träd, kan man genomföra en pre-order traversal eller en post-order traversal, men inte heller är sannolikt att vara användbar för binära Sök Träd., En beställning av ett binärt sökträd kommer alltid att resultera i en sorterad lista över nodobjekt (tal, strängar eller andra jämförbara objekt).

koden för in-order traversal i Python ges nedan. Det kommer att återuppringning (någon funktion programmeraren vill ringa på nodens värde, till exempel utskrift till skärmen) för varje nod i trädet.

Traversal kräver O(n) tid, eftersom den måste besöka varje nod. Denna algoritm är också O (n), så det är asymptotiskt optimalt.

Traversal kan också genomföras iterativt. För vissa tillämpningar, t. ex., större lika sökning, approximativ sökning, en operation för ett steg (iterativ) traversal kan vara mycket användbar. Detta implementeras naturligtvis utan återuppringningskonstruktionen och tar i genomsnitt O(1) och O(log n) i värsta fall.

Verifieringedit

Ibland har vi redan ett binärt träd, och vi måste avgöra om det är en BST. Detta problem har en enkel rekursiv lösning.,

BST-egenskapen – varje nod på höger underträd måste vara större än den aktuella noden och varje nod på vänster underträd måste vara mindre än den aktuella noden—är nyckeln till att ta reda på om ett träd är en BST eller inte. Den giriga algoritmen-helt enkelt korsa trädet, vid varje nod kontrollera om noden innehåller ett värde som är större än värdet på vänster barn och mindre än värdet på rätt barn—fungerar inte för alla fall., Tänk på följande träd:

 20 / \ 10 30 / \ 5 40

i trädet ovan uppfyller varje nod villkoret att noden innehåller ett värde som är större än dess vänstra barn och mindre än dess högra barnhåll, och ändå är det inte en BST: värdet 5 ligger på den högra undertreen i noden som innehåller 20, en kränkning av BST-egenskapen.

i stället för att fatta ett beslut baserat enbart på värdena för en nod och dess barn behöver vi också information som strömmar ner från föräldern också., När det gäller trädet ovan, om vi kunde komma ihåg om noden som innehåller värdet 20, skulle vi se att noden med värde 5 bryter mot BST-egendomskontraktet.,

så villkoret vi måste kontrollera vid varje nod är:

• om noden är det vänstra barnet i sin förälder, måste det vara mindre än (eller lika med) föräldern och det måste passera ner värdet från sin förälder till sin högra underträd för att se till att ingen av noderna i den undertreen är större än föräldern
• om noden är det högra barnet i sin förälder, måste det vara större än föräldern och det måste passera ner värdet från sin förälder till sin vänstra undertree för att se till att ingen av noderna i det underträdet är mindre än föräldern.,

en rekursiv lösning i C++ kan förklara detta ytterligare:

node->key+1 ochnode->key-1 görs för att tillåta endast distinkta element i BST.

om vi vill att samma element också ska vara närvarande kan vi bara använda node->key på båda ställena.

det första samtalet till den här funktionen kan vara ungefär så här:

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

i huvudsak fortsätter vi att skapa ett giltigt intervall (från och med ) och fortsätter att krympa ner det för varje nod när vi går ner rekursivt.,

som påpekats i avsnitt #Traversal returnerar en in-order traversal av ett binärt sökträd noderna sorterade. Således behöver vi bara hålla den senast besökta noden medan vi går över trädet och kontrollera om dess nyckel är mindre (eller mindre/lika, om dubbletter ska tillåtas i trädet) jämfört med den aktuella nyckeln.

Parallellalgoritmsedit

det finns också parallella algoritmer för binära sök träd, inklusive Infoga / Ta bort flera element, konstruktion från array, filter med viss predicator, platta till en array, sammanslagning/substracting / korsande två träd, etc., Dessa algoritmer kan implementeras med hjälp av join – baserade träd algoritmer, som också kan hålla trädet balanseras med hjälp av flera balanseringssystem (inklusive AVL träd, röd-svart träd, viktbalanserad träd och treap) .