Binärt sökträd (BST) med exempel
Vad är ett binärt sökträd?
Det binära sökträdet är en avancerad algoritm som används för att analysera noden, dess vänstra och högra grenar, som modelleras i en trädstruktur och returnerar värdet. BST är utformad på arkitekturen för en grundläggande binär sökalgoritm; därför möjliggör den snabbare uppslagningar, infogningar och borttagningar av noder. Detta gör programmet riktigt snabbt och exakt.
Attribut för binärt sökträd
En BST består av flera noder och består av följande attribut:
- Noder i trädet representeras i en förälder-barn-relation
- Varje föräldernod kan ha noll undernoder eller maximalt två undernoder eller underträd på vänster och höger sida.
- Varje underträd, även känt som ett binärt sökträd, har undergrenar till höger och vänster om sig själva.
- Alla noder är länkade med nyckel-värde-par.
- Nycklarna till noderna som finns i det vänstra underträdet är mindre än nycklarna till deras överordnade nod
- På samma sätt har de vänstra subträdnodernas nycklar lägre värden än deras modernods nycklar.
- Det finns huvudnoden eller överordnad nivå 11. Under den finns vänster och höger noder/grenar med sina egna nyckelvärden
- Det högra underträdet har nyckelvärden som är större än föräldernoden
- Det vänstra underträdet har värden än den överordnade noden
Varför behöver vi ett binärt sökträd?
- De två huvudfaktorerna som gör binärt sökträd till en optimal lösning på alla verkliga problem är hastighet och noggrannhet.
- På grund av att den binära sökningen är i ett grenliknande format med föräldra-barn-relationer, vet algoritmen på vilken plats i trädet elementen behöver sökas. Detta minskar antalet nyckel-värde-jämförelser som programmet måste göra för att hitta det önskade elementet.
- Dessutom, om elementet som ska sökas är större eller mindre än föräldernoden, vet noden vilken trädsida den ska söka efter. Anledningen är att det vänstra underträdet alltid är mindre än föräldernoden, och det högra underträdet har värden som alltid är lika med eller större än föräldernoden.
- BST används ofta för att implementera komplexa sökningar, robust spellogik, automatiska kompletteringsaktiviteter och grafik.
- Algoritmen stöder effektivt operationer som att söka, infoga och ta bort.
Typer av binära träd
Tre sorters binära träd är:
- Komplett binärt träd: Alla nivåer i träden är fulla av sista nivåns möjliga undantag. På samma sätt är alla noder fulla och riktar sig längst till vänster.
- Fullständigt binärt träd: Alla noder har 2 barnnoder utom bladet.
- Balanserat eller perfekt binärt träd: I trädet har alla noder två barn. Dessutom finns det samma nivå för varje subnod.
Läs mer om Binärt träd i datastruktur om du är intresserad.
Hur fungerar binärt sökträd?
Trädet har alltid en rotnod och ytterligare barnnoder, antingen till vänster eller höger. Algoritmen utför alla operationer genom att jämföra värden med roten och dess ytterligare barnnoder i det vänstra eller högra underträdet.
Beroende på elementet som ska infogas, söka eller raderas, efter jämförelsen kan algoritmen enkelt släppa det vänstra eller högra underträdet i rotnoden.
BST erbjuder i första hand följande tre typer av operationer för din användning:
- Sök: söker efter elementet från det binära trädet
- Infoga: lägger till ett element i det binära trädet
- Ta bort: ta bort elementet från ett binärt träd
Varje operation har sin egen struktur och metod för exekvering/analys, men den mest komplexa av allt är Ta bort-operationen.
Sök Operation
Initiera alltid analysträdet vid rotnoden och flytta sedan vidare till antingen det högra eller vänstra underträdet i rotnoden beroende på att elementet som ska lokaliseras är antingen mindre eller större än roten.
- Elementet som ska sökas är 10
- Jämför elementet med rotnoden 12, 10 < 12, därav går du till vänster underträd. Inget behov av att analysera det högra underträdet
- Jämför nu 10 med nod 7, 10 > 7, så flytta till höger underträd
- Jämför sedan 10 med nästa nod, som är 9, 10 > 9, titta i det högra underträdet
- 10 matchar med värdet i noden, 10 = 10, returnerar värdet till användaren.
Pseudokod för sökning i BST
search(element, root) if !root return -1 if root.value == element return 1 if root.value < element search(element, root.right) else search(element, root.left)
Insert Operation
Detta är en mycket enkel operation. Först infogas rotnoden, sedan jämförs nästa värde med rotnoden. Om värdet är större än roten läggs det till i det högra underträdet, och om det är mindre än roten läggs det till i det vänstra underträdet.
- Det finns en lista med 6 element som måste infogas i en BST i ordning från vänster till höger
- Infoga 12 som rotnod och jämför nästa värden 7 och 9 för att infoga därefter i det högra och vänstra underträdet
- Jämför de återstående värdena 19, 5 och 10 med rotnoden 12 och placera dem därefter. 19 > 12 placera det som höger barn av 12, 5 < 12 & 5 < 7, därav placera det som vänster barn av 7. Jämför nu 10, 10 är < 12 & 10 är > 7 & 10 är > 9, plats 10 som höger underträd av 9.
Pseudokod för att infoga en nod i BST
insert (element, root) Node x = root Node y = NULL while x: y = x if x.value < element.value x = x.right else x = x.left if y.value < element y.right = element else y.left = element
Radera Operationer
För att ta bort en nod från en BST finns det några fall, dvs radering av en rot eller borttagning av en lövnod. Efter att ha tagit bort en rot måste vi också tänka på rotnoden.
Säg att vi vill ta bort en bladnod, vi kan bara ta bort den, men om vi vill ta bort en rot måste vi ersätta rotens värde med en annan nod. Låt oss ta följande exempel:
- Fall 1- Nod med noll barn: detta är den enklaste situationen, du behöver bara ta bort noden som inte har några ytterligare barn till höger eller vänster.
- Fall 2 – Nod med ett underordnat: när du har tagit bort noden kopplar du helt enkelt dess underordnade nod till föräldernoden för det raderade värdet.
- Fall 3 Nod med två barn: detta är den svåraste situationen och den fungerar enligt följande två regler
- 3a – I Order Predecessor: du måste ta bort noden med två barn och ersätta den med det största värdet på det vänstra underträdet av den borttagna noden
- 3b – I ordningsföljd: du måste ta bort noden med två underordnade och ersätta den med det största värdet på högerunderträdet av den borttagna noden
- Detta är det första fallet av radering där du tar bort en nod som inte har några barn. Som du kan se i diagrammet har 19, 10 och 5 inga barn. Men vi tar bort 19.
- Ta bort värdet 19 och ta bort länken från noden.
- Se den nya strukturen för BST utan 19
- Detta är det andra fallet av radering där du tar bort en nod som har 1 barn, som du kan se i diagrammet att 9 har ett barn.
- Ta bort noden 9 och ersätt den med dess underordnade 10 och lägg till en länk från 7 till 10
- Se den nya strukturen för BST utan 9
- Här kommer du att ta bort noden 12 som har två barn
- Raderingen av noden kommer att ske baserat på föregångaren i ordning, vilket innebär att det största elementet i det vänstra underträdet av 12 kommer att ersätta det.
- Ta bort noden 12 och ersätt den med 10 eftersom det är det största värdet på det vänstra underträdet
- Visa den nya strukturen för BST efter borttagning av 12
- 1 Ta bort en nod 12 som har två barn
- 2 Raderingen av noden kommer att ske baserat på regeln In Order Successor, vilket innebär att det största elementet på höger underträd av 12 kommer att ersätta det
- 3 Ta bort noden 12 och ersätt den med 19 eftersom det är det största värdet på det högra underträdet
- 4 Visa den nya strukturen för BST efter borttagning av 12
Pseudokod för att ta bort en nod
delete (value, root): Node x = root Node y = NULL # searching the node while x: y = x if x.value < value x = x.right else if x.value > value x = x.left else if value == x break # if the node is not null, then replace it with successor if y.left or y.right: newNode = GetInOrderSuccessor(y) root.value = newNode.value # After copying the value of successor to the root #we're deleting the successor free(newNode) else free(y)
Viktiga villkor
- Infoga: Infogar ett element i ett träd/skapar ett träd.
- Sök: Söker efter ett element i ett träd.
- Förbeställningsgenomgång: Går igenom ett träd på ett förbeställningssätt.
- Inorder Traversal: Går igenom ett träd på ett inordnat sätt.
- Postorderpassering: Går igenom ett träd på ett postordersätt.
Sammanfattning
- BST är en avancerad nivåalgoritm som utför olika operationer baserat på jämförelsen av nodvärden med rotnoden.
- Vilken som helst av punkterna i en förälder-underordnad hierarki representerar noden. Minst en förälder eller rotnod finns kvar hela tiden.
- Det finns ett vänster underträd och ett höger underträd. Det vänstra underträdet innehåller värden som är mindre än rotnoden. Det högra underträdet innehåller dock ett värde som är större än rotnoden.
- Varje nod kan ha antingen noll, ett eller två barn.
- Ett binärt sökträd underlättar primära operationer som att söka, infoga och ta bort.
- Ta bort är den mest komplexa har flera fall, till exempel en nod utan barn, nod med ett barn och nod med två barn.
- Algoritmen används i verkliga lösningar som spel, autokompletteringsdata och grafik.