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 är modellerade i en trädstruktur och returnerar värdet. BST är utformad på arkitekturen för en grundläggande binär sökalgoritm; det möjliggör snabbare sökningar, insättningar och borttagningar av noder. Detta gör programmet riktigt snabbt och exakt.
I den här handledningen för datastruktur lär du dig:
- Vad är ett binärt sökträd?
- Attribut för binärt sökträd
- Varför behöver vi ett binärt sökträd?
- Typer av binära träd
- Hur fungerar binärt sökträd?
- Viktiga villkor
Attribut för binärt sökträd
En BST är gjord av flera noder och består av följande attribut:
- Noder i trädet representeras i ett förhållande mellan förälder och barn
- Varje föräldernod kan ha noll underordnade noder eller högst 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ärdepar.
- Nycklarna till noder som finns i vänster underträd är mindre än nycklarna till deras föräldernod
- På samma sätt har de vänstra subträdnodernas nycklar mindre värden än deras moderns 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 föräldernoden
Varför behöver vi ett binärt sökträd?
- De två viktigaste faktorerna som gör binärt sökträd till en optimal lösning på eventuella verkliga problem är hastighet och noggrannhet.
- På grund av det faktum att den binära sökningen är i ett grenliknande format med förhållanden mellan föräldrar och barn, vet algoritmen på vilken plats i trädet elementen måste sökas. Detta minskar antalet nyckelvärdesjämförelser som programmet måste göra för att hitta det önskade elementet.
- Dessutom, om det element som ska sökas 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 alltid värden lika med eller större än föräldernoden.
- BST används ofta för att implementera komplexa sökningar, robust spellogik, automatisk komplettering av aktiviteter och grafik.
- Algoritmen stöder effektivt operationer som sökning, 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åens möjliga undantag. På samma sätt är alla noder fulla och styr längst till vänster.
- Fullt binärt träd: Alla noder har två 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.
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 underordnade noder i vänster eller höger underträd i enlighet därmed.
Beror på vilket element som ska infogas, sökas eller tas bort, efter jämförelsen kan algoritmen enkelt släppa rotens vänstra eller högra underträd.
BST erbjuder främst följande tre typer av åtgärder för din användning:
- Sök: söker i elementet från det binära trädet
- Infoga: lägger till ett element i det binära trädet
- Radera: 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 alla är Delete-operationen.
Sökoperation
Starta alltid analys av träd vid rotnoden och flytta sedan längre till antingen höger eller vänster underträd 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, följaktligen flyttar du till vänster underträd. Inget behov av att analysera rätt subtree
- Jämför nu 10 med nod 7, 10> 7, så flytta till höger subtree
- Jämför sedan 10 med nästa nod, som är 9, 10> 9, se i rätt underträdsbarn
- 10 matchar värdet i noden, 10 = 10, returnera värdet till användaren.
Sätt i drift
Detta är en mycket rakt framåt 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 till höger underträd, och om det är mindre än roten läggs det till 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 höger och vänster underträd
- 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 det högra barnet av 12, 5 <12 & 5 <7, därefter placera det som vänster barn till 7.
- Jämför nu 10, 10 är <12 & 10 är> 7 & 10 är> 9, placera 10 som rätt underträd av 9.
Radera åtgärder
Radera är det mest avancerade och komplexa bland alla andra operationer. Det finns flera ärenden som hanteras för radering i BST.
- Fall 1 - Nod med noll barn: detta är den enklaste situationen, du behöver bara ta bort noden som inte har fler barn till höger eller vänster.
- Fall 2 - Nod med ett barn: när du har raderat noden, anslut bara dess undernod med föräldernoden för det raderade värdet.
- Fall 3 Nod med två barn: detta är den svåraste situationen, och den fungerar på följande två regler
- 3a - I ordningsföregångare: du måste ta bort noden med två barn och ersätta den med det största värdet på vänster underträd i den raderade 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öger underträd i den raderade noden
- Detta är det första fallet med 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.
- Visa BST: s nya struktur utan 19
- Detta är det andra fallet med radering där du tar bort en nod som har 1 barn, vilket 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
- Visa den nya strukturen för BST utan 9
- Här raderar du noden 12 som har två barn
- Raderingen av noden kommer att ske baserat på föregångarregeln i ordning, vilket innebär att det största elementet på vänster underträd på 12 kommer att ersätta det.
- Radera nod 12 och ersätt den med 10 eftersom det är det största värdet på vänster underträd
- Visa den nya strukturen för BST efter att du har tagit bort 12
- 1 Ta bort en nod 12 som har två barn
- 2 Raderingen av noden kommer att ske baserat på In Order Successor-regeln, vilket innebär att det största elementet på det högra underträdet på 12 kommer att ersätta det
- 3 Ta bort nod 12 och ersätt den med 19 eftersom det är det största värdet på rätt underträd
- 4 Visa den nya strukturen för BST efter att du har tagit bort 12
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ällningstrafik - Korsar ett träd på förbeställning.
- Inorder Traversal - Korsar ett träd på ett ordnat sätt.
- Postorder Traversal - Korsar ett träd efter beställning.
Sammanfattning
- BST är en avancerad nivåalgoritm som utför olika operationer baserat på jämförelsen av nodvärden med rotnoden.
- Någon av punkterna i en förälder-barnhierarki representerar noden. Minst en förälder eller rotnod förblir närvarande hela tiden.
- Det finns en vänster subtree och höger subtree. Det vänstra underträdet innehåller värden som är mindre än rotnoden. Höger underträd 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 sökning, infoga och ta bort.
- Radera som det 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, autofullständig data och grafik.