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 returnera värdet. BST är utformad utifrån arkitekturen för en grundläggande binär sökalgoritm; därför möjliggör den snabbare sökningar, 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 för noderna som finns i det vänstra underträdet är mindre än nycklarna för deras överordnade nod.
• På samma sätt är nycklarna för noderna i det högra underträdet större än nycklarna för deras överordnade nod.

1. Det finns huvudnoden eller föräldranivå 11. Under den finns vänster och höger noder/grenar med sina egna nyckelvärden.
2. Det högra underträdet har nyckelvärden som är större än den överordnade noden.
3. Det vänstra underträdet har färre nyckelvärden än den överordnade noden.

Varför behöver vi ett binärt sökträd?

• De två viktigaste faktorerna som gör ett 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 den överordnade noden, vet noden vilken trädsida den ska söka på. Anledningen är att det vänstra underträdet alltid är mindre än den överordnade noden, och det högra underträdet har värden som alltid är lika med eller större än den överordnade noden.
• 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ädet är fulla, med ett möjligt undantag på den sista nivån. På samma sätt är alla noder fulla och pekar längst till vänster.
• Fullständigt binärt träd: Alla noder har 2 undernoder förutom lövet.
• Balanserat eller perfekt binärt träd: I trädet har alla noder två barn. Dessutom finns det samma nivå för varje undernod.

Läs mer om kursen här: 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å vilket element som ska infogas, sökas eller tas bort, kan algoritmen efter jämförelsen enkelt ta bort 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.
• Föra in: lägger till ett element i det binära trädet.
• Radera: tar 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

Börja alltid analysera trädet vid rotnoden och gå sedan vidare till antingen höger eller vänster delträd av rotnoden, beroende på om elementet som ska lokaliseras är mindre än eller större än roten.

1. Elementet som ska sökas är 10.
2. Jämför elementet med rotnoden 12, 10 < 12, så flyttar du till det vänstra delträdet. Du behöver inte analysera det högra delträdet.
3. Jämför nu 10 med nod 7, 10 > 7, så flytta till höger underträd.
4. Jämför sedan 10 med nästa nod, som är 9, 10 > 9, titta i det högra underträdet.
5. 10 matchar med värdet i noden, 10 = 10, returnerar värdet till användaren.

Pseudo Code 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.

1. Det finns en lista med 6 element som måste infogas i en BST i ordning från vänster till höger.
2. Infoga 12 som rotnod och jämför följande värden 7 och 9 för att infoga dem i höger och vänster delträd.
3. Jämför de återstående värdena 19, 5 och 10 med rotnoden 12 och placera dem därefter. 19 > 12, placera den som höger barn till 12; 5 < 12 och 5 < 7, placera den alltså som vänster barn till 7. Jämför nu 10, 10 är < 12 och 10 är > 7 och 10 är > 9, placera 10 som höger delträd till 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 vissa fall, t.ex. att ta bort en rotnod eller ta bort 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 barn: När du har tagit bort noden, anslut helt enkelt dess undernod till föräldranoden för det borttagna värdet.
• Fall 3 – Nod med två barn: Detta är den svåraste situationen, och den fungerar enligt följande två regler:
  • 3a – Föregångare i ordning: Du måste ta bort noden med två underordnade noder och ersätta den med det största värdet i det vänstra underträdet för den borttagna noden.
  • 3b – Efterföljare i ordning: Du måste ta bort noden med två underordnade noder och ersätta den med det minsta värdet i det högra underträdet för den borttagna noden.

1. Detta är det första fallet med borttagning, 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 kommer att ta bort 19.
2. Ta bort värdet 19 och ta bort länken från noden.
3. Se den nya strukturen för BST utan 19.

1. Detta är det andra fallet med borttagning, där man tar bort en nod som har ett barn. Som ni kan se i diagrammet har 9 ett barn.
2. Ta bort nod 9 och ersätt den med dess underordnade nod 10, och lägg till en länk från 7 till 10.
3. Se den nya strukturen för BST utan 9.

1. Här tar du bort nod 12 som har två barn.
2. Raderingen av noden kommer att ske baserat på föregångarregeln i ordning, vilket innebär att det största elementet i det vänstra delträdet av 12 kommer att ersätta den.
3. Ta bort nod 12 och ersätt den med 10, eftersom det är det största värdet i det vänstra underträdet.
4. Visa den nya strukturen för BST efter att ha tagit bort 12.

1. Ta bort en nod 12 som har två underordnade noder.
2. Raderingen av noden kommer att ske baserat på In-Order Successor-regeln, vilket innebär att det minsta elementet i det högra underträdet av 12 kommer att ersätta den.
3. Ta bort nod 12 och ersätt den med 19, eftersom det är det minsta värdet i det högra underträdet.
4. Visa den nya strukturen för BST efter att ha tagit bort 12.

Pseudo Code 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, delete the successor
        free(newNode)
    else
        free(y)

Viktiga villkor

• Föra in: 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: Korsar ett träd på ett förbeställt sätt.
• Inorder genomgång: Korsar ett träd i ordning.
• Postorder-genomgång: Korsar ett träd på ett efterföljande sätt.

Vanliga frågor