Vad är ett binärt sökträd?

Ett binärt sökträd är en av de olika datastrukturerna som hjälper oss att organisera och sortera data. Det är ett effektivt sätt att lagra data i en hierarki och är mycket flexibelt.

I den här artikeln kommer vi att titta närmare på hur det fungerar – tillsammans med dess egenskaper och tillämpningar.

Vad är ett binärt sökträd?

Ett binärt sökträd är en datastruktur som består av noder – liknande länkade listor. Det kan finnas två typer av noder: en förälder och ett barn. Rotnoden är startpunkten för strukturen som förgrenar sig till två barnnoder, som kallas den vänstra noden och den högra noden.

Varje nod kan endast refereras av sin förälder, och vi kan korsa trädets noder beroende på riktningen. Det binära sökträdet har tre huvudegenskaper:

1. Den vänstra noden är mindre än sin förälder.
2. Den högra noden är större än sin förälder.
3. De vänstra och högra underträden måste vara binära sökträd.

Ett perfekt binärt sökträd uppnås när alla nivåer är fyllda och varje nod har en vänster och höger barnnod.

Relaterad: Data Science Libraries för Python som alla dataforskare bör använda

Grundläggande funktioner för ett binärt sökträd

Nu har du fått en bättre uppfattning om vad ett binärt sökträd är, vi kan titta på dess grundläggande funktioner nedan.

1. Sökoperation

Sökning tillåter oss att lokalisera ett visst värde som finns i trädet. Vi kan använda två typer av sökningar: bredd-först-sökning (BFS) och djup-först-sökning (DFS). Bredd-först-sökning är en sökalgoritm som börjar vid rotnoden och går horisontellt, från sida till sida, tills målet hittas. Varje nod besöks en gång under denna sökning.

Djup-första-sökning, å andra sidan, korsar trädet vertikalt – med början från rotnoden och arbetar nerför en enda gren. Om målet hittas avslutas operationen. Men om inte, det och söker de andra noderna.

2. Insättningsoperation

Infogningsoperationen använder sökoperationen för att bestämma platsen där den nya noden ska infogas. Processen startar från rotnoden och sökningen börjar tills destinationen nås. Det finns tre fall att överväga med infogning.

• Fall 1: När ingen nod finns. Noden som ska infogas blir rotnoden.

• Fall 2: Det finns inga barn. I det här fallet kommer noden att jämföras med rotnoden. Om det är större blir det rätt barn; annars kommer det att bli det vänstra barnet.

• Fall 3: När roten och dess barn är närvarande. Den nya noden kommer att jämföras med varje nod på sin väg för att bestämma vilken nod den besöker härnäst. Om noden är större än rotnoden, kommer den att korsa ner det högra underträdet eller till vänster. På samma sätt görs jämförelser på varje nivå för att avgöra om den kommer att gå åt höger eller vänster tills den når sin destination.

3. Ta bort operation

Ta bort operationen används för att ta bort en viss nod i trädet. Borttagning anses vara knepigt eftersom trädet måste omorganiseras efter att en nod tagits bort. Det finns tre huvudfall att överväga:

• Fall 1: Ta bort en lövnod. En lövnod är en nod utan några barn. Detta är det enklaste att ta bort eftersom det inte påverkar någon annan nod; vi korsar helt enkelt trädet tills vi når det och tar bort det.

• Fall 2: Ta bort en nod med ett barn. Att ta bort en förälder med en nod kommer att resultera i att barnet tar sin position, och alla efterföljande noder kommer att flytta upp en nivå. Det kommer inte att ske någon förändring i underträdens struktur.

• Fall 3: Ta bort en nod med två barn. När vi ska ta bort en nod med två barn måste vi först hitta en efterföljande nod som kan ta sin position. Två noder kan ersätta den borttagna noden, den inordnade efterföljaren eller föregångaren. Den inordnade efterföljaren är det högra underträdets underordnade längst till vänster, och den inordnade föregångaren är det vänstra underträdets underordnade längst till höger. Vi kopierar innehållet i efterträdaren/föregångaren till noden och tar bort efterföljaren/föregångaren i ordning.

Relaterad: Hur man bygger datastrukturer med JavaScript ES6-klasser

Hur man korsar ett binärt sökträd

Traversering är den process genom vilken vi navigerar i ett binärt sökträd. Det görs för att hitta ett specifikt föremål eller för att skriva ut en kontur av trädet. Vi utgår alltid från rotnoden och måste följa kanterna för att komma till de andra noderna. Varje nod bör betraktas som ett underträd, och processen upprepas tills alla noder har besökts.

• Genomgång i order: Att gå i ordning kommer att producera en karta i stigande ordning. Med denna metod börjar vi från det vänstra underträdet och fortsätter till roten och det högra underträdet.

• Genomgång för förbeställning: I denna metod besöks rotnoden först, följt av det vänstra underträdet och det högra underträdet.

• Traversering efter beställning: Denna genomgång innebär att man besöker rotnoden sist. Vi börjar från det vänstra underträdet, sedan det högra underträdet och sedan rotnoden.

Verkliga applikationer

Så, hur använder vi binära sökträdalgoritmer? Som man kan ana är de extremt effektiva på att söka och sortera. Den största styrkan hos binära träd är deras organiserade struktur. Det gör att sökningar kan göras med anmärkningsvärda hastigheter genom att halvera mängden data vi behöver analysera med hälften per pass.

Binära sökträd tillåter oss att effektivt underhålla en dynamiskt föränderlig datauppsättning i en organiserad form. För program som ofta har infogat och tagit bort data är de mycket användbara. Videospelsmotorer använder en algoritm baserad på träd som kallas binär rymdpartition för att hjälpa till att göra objekt ordnade. Microsoft Excel och de flesta kalkylprogram använder binära träd som sin grundläggande datastruktur.

Du kanske blir förvånad över att veta att morsekod använder ett binärt sökträd för att koda data. En annan framträdande anledning till att binära sökträd är så användbara är deras många varianter. Deras flexibilitet har lett till att många varianter skapats för att lösa alla möjliga problem. När de används på rätt sätt är binära sökträd en stor tillgång.

Binära sökträd: Den perfekta startpunkten

Ett av de viktigaste sätten att mäta en ingenjörs expertis är genom deras kunskap och tillämpning av datastrukturer. Datastrukturer är användbara och kan hjälpa till att skapa ett mer effektivt system. Binära sökträd är en bra introduktion till datastrukturer för alla utvecklare som börjar.

15 JavaScript-array-metoder du bör behärska idag

Vill du förstå JavaScript-matriser men kan inte ta tag i dem? Se våra JavaScript-arrayexempel för vägledning.

Läs Nästa

Om författaren