Implementering av ett binärt sökträd

2024 Författare: Angel Austin | [email protected]. Senast ändrad: 2023-12-17 05:42

Binärt sökträd - en strukturerad databas som innehåller noder, två länkar till andra noder, höger och vänster. Noder är ett objekt i klassen som har data, och NULL är tecknet som markerar slutet på trädet.

Det kallas ofta BST, som har en speciell egenskap: noder som är större än roten finns till höger om den, och mindre till vänster.

Allmän teori och terminologi

I ett binärt sökträd är varje nod, exklusive roten, ansluten med en riktad kant från en nod till en annan, som kallas föräldern. Var och en av dem kan kopplas till ett godtyckligt antal noder, kallade barn. Noder utan "barn" kallas löv (yttre noder). Element som inte är löv kallas interna. Noder med samma förälder är syskon. Den översta noden kallas roten. I BST, tilldela ett element till varje nod och se till att de har en speciell egenskap för dem.

Trädterminologi:

Djupet på en nod är antalet kanter som definieras från roten till den.
Höjden på en nod är antalet kanter som definieras från den till det djupaste bladet.
Höjden på trädet bestäms av höjden på roten.
Binärt sökträd är en speciell design, det ger det bästa förhållandet mellan höjd och antal noder.
Höjd h med N noder som mest O (log N).

Du kan enkelt bevisa detta genom att räkna noderna på varje nivå, med början från roten, förutsatt att den innehåller det största antalet av dem: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Att lösa detta för h ger h=O (log n).

Fördelar med trä:

Speglar de strukturella förhållandena för data.
Används för att representera hierarkier.
Säkerställ effektiv installation och sökning.
Träd är mycket flexibel data som gör att du kan flytta underträd med minimal ansträngning.

Sökmetod

I allmänhet, för att avgöra om ett värde finns i BST, starta ett binärt sökträd vid dess rot och avgör om det uppfyller kraven:

vara vid roten;
befinna sig i rotens vänstra underträd;
i det högra underträdet av roten.

Om inget basregister är uppfyllt, utförs en rekursiv sökning i motsvarande underträd. Det finns faktiskt två grundläggande alternativ:

Trädet är tomt - returnera falskt.
Värdet finns i rotnoden - returnera sant.

Det bör noteras att ett binärt sökträd med ett utvecklat schema alltid börjar söka längs vägen från roten till bladet. I värsta fall går det hela vägen till lövet. Därför är den sämsta tiden proportionell mot längden på den längsta vägen från roten till bladet, vilket är trädets höjd. I allmänhet är det då du behöver veta hur lång tid det tar att slå upp som en funktion av antalet värden som lagras i trädet.

Med andra ord finns det ett samband mellan antalet noder i en BST och höjden på ett träd, beroende på dess "form". I värsta fall har noder bara ett barn, och ett balanserat binärt sökträd är i huvudsak en länkad lista. Till exempel:

Detta träd har 5 noder och höjd=5. För att hitta värden i intervallet 16-19 och 21-29 krävs följande väg från roten till bladet (noden som innehåller värdet 20), dvs., kommer det att ta tid proportionellt mot antalet noder. I bästa fall har de alla två barn, och löven ligger på samma djup.

Det här binära sökträdet har 7 noder och höjd=3. I allmänhet kommer ett träd som detta (helt träd) att ha en höjd på ungefär log 2 (N), där N är antalet noder i trädet. Värdet på log 2 (N) är antalet gånger (2) som N kan delas innan noll uppnås.

Sammanfattning: den värsta tiden som behövs för att söka i BST är O (trädhöjd). Det värsta "linjära" trädet är O(N), där N är antalet noder i trädet. I bästa fall är ett "komplett" träd O(log N).

BST binär infogning

Undrar var den ska varaden nya noden ligger i BST, du måste förstå logiken, den måste placeras där användaren hittar den. Dessutom måste du komma ihåg reglerna:

Dubbletter är inte tillåtna, försök att infoga ett dubblettvärde kommer att leda till ett undantag.
Den offentliga infogningsmetoden använder en hjälprekursiv "hjälparmetod" för att faktiskt infoga.
En nod som innehåller ett nytt värde infogas alltid som ett blad i BST.
Den publika infogningsmetoden returnerar void, men hjälpmetoden returnerar en BST-nod. Den gör detta för att hantera fallet där noden som skickas till den är null.

I allmänhet indikerar hjälpmetoden att om det ursprungliga binära sökträdet är tomt, är resultatet ett träd med en nod. Annars kommer resultatet att vara en pekare till samma nod som skickades som ett argument.

Radering i binär algoritm

Som du kan förvänta dig, innebär att ta bort ett element att hitta en nod som innehåller värdet som ska tas bort. Det finns flera saker i den här koden:

BST använder en hjälpande, överbelastad raderingsmetod. Om elementet du letar efter inte finns i trädet kommer hjälpmetoden så småningom att anropas med n==null. Detta anses inte vara ett fel, trädet ändras helt enkelt inte i det här fallet. Raderingshjälpmetoden returnerar ett värde - en pekare till det uppdaterade trädet.
När ett blad tas bort, ställer borttagningen från det binära sökträdet motsvarande underordnade pekare för dess förälder till null, eller roten till null om den som tas bort ärnoden är en rot och har inga barn.
Observera att raderingsanropet måste vara något av följande: root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight(), nyckel)). I alla tre fallen är det alltså korrekt att raderingsmetoden helt enkelt returnerar null.
När sökningen efter noden som innehåller värdet som ska raderas lyckas finns det tre alternativ: noden som ska raderas är ett blad (har inga barn), noden som ska raderas har ett barn, den har två barn.
När noden som tas bort har ett barn kan du helt enkelt ersätta det med ett underordnat och returnera en pekare till barnet.
Om noden som ska raderas har noll eller 1 underordnade, kommer borttagningsmetoden att "följa sökvägen" från roten till den noden. Så den sämsta tiden är proportionell mot trädets höjd, för både sökning och insättning.

Om noden som ska tas bort har två barn, tas följande steg:

Hitta noden som ska raderas, följ sökvägen från roten till den.
Hitta det minsta värdet på v i det högra underträdet, fortsätt längs vägen till bladet.
Ta bort värdet på v rekursivt, följ samma väg som i steg 2.
I värsta fall utförs alltså vägen från roten till bladet två gånger.

Order av travers

Traversal är en process som besöker alla noder i ett träd. Eftersom ett binärt C-sökträd är en icke-linjär datastruktur, finns det ingen unik genomgång. Till exempel, ibland flera traversalgorithmergrupperade i följande två typer:

korsningsdjup;
första pass.

Det finns bara en typ av breddkorsning - förbi nivån. Den här genomgången besöker noder nivå ner och vänster, topp och höger.

Det finns tre olika typer av djupkorsningar:

Godkänd förbeställning - besök först föräldern och sedan vänster och höger barn.
Passing InOrder - besöker det vänstra barnet, sedan föräldern och det högra barnet.
Förbi postordern - besöker det vänstra barnet, sedan det högra barnet och sedan föräldern.

Exempel på fyra genomgångar av ett binärt sökträd:

Förbeställning - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Figuren visar i vilken ordning noderna besöks. Siffran 1 är den första noden i en viss genomgång, och 7 är den sista noden.

Dessa allmänna genomgångar kan representeras som en enda algoritm, förutsatt att varje nod besöks tre gånger. Euler-turen är en promenad runt ett binärt träd där varje kant behandlas som en vägg som användaren inte kan korsa. I denna promenad kommer varje nod att besökas antingen till vänster, under eller till höger. Euler-turen, som besöker noderna till vänster, gör att prepositionen förbigås. När noderna nedan besöks, korsas de i ordning. Och när noderna till höger besöks – fåsteg-för-steg bypass.

Navigering och felsökning

För att göra det lättare att navigera i trädet, skapa funktioner som först kontrollerar om de är vänster eller höger barn. För att ändra positionen för en nod måste det finnas enkel åtkomst till pekaren vid den överordnade noden. Att korrekt implementera ett träd är mycket svårt, så du måste känna till och tillämpa felsökningsprocesser. Ett binärt sökträd med en implementering har ofta pekare som faktiskt inte anger färdriktningen.

För att reda ut allt detta används en funktion som kontrollerar om trädet kan vara korrekt, och hjälper till att hitta många fel. Till exempel kontrollerar den om föräldernoden är en undernod. Med assert(is_wellformed(root)) kan många fel fångas i förtid. Genom att använda ett par givna brytpunkter inom den här funktionen kan du också avgöra exakt vilken pekare som är fel.

Function Konsolenausgabe

Denna funktion spolar hela trädet till konsolen och är därför mycket användbar. Ordningen i vilken trädets utdatamål exekveras är:

För att göra detta måste du först bestämma vilken information som kommer att matas ut genom noden.
Och du behöver också veta hur brett och högt trädet är för att ta hänsyn till hur mycket utrymme du ska lämna.
Följande funktioner beräknar denna information för trädet och varje underträd. Eftersom du bara kan skriva till konsolen rad för rad, måste du också skriva ut trädet rad för rad.
Nu behöver vi ett annat sätt att dra oss urhela trädet, inte bara rad för rad.
Med hjälp av dumpfunktionen kan du läsa trädet och förbättra utdataalgoritmen avsevärt vad gäller hastighet.

Den här funktionen kommer dock att vara svår att använda på stora träd.

Copy constructor and destructor

Eftersom ett träd inte är en trivial datastruktur, är det bättre att implementera en kopieringskonstruktör, en destruktor och en tilldelningsoperator. Destruktorn är lätt att implementera rekursivt. För mycket stora träd klarar den "högspill". I det här fallet formuleras den iterativt. Tanken är att ta bort bladet som representerar det minsta värdet av alla löv, så det är på vänster sida av trädet. Att skära av de första löven skapar nya, och trädet krymper tills det slutligen upphör att existera.

Kopieringskonstruktorn kan också implementeras rekursivt, men var försiktig om ett undantag kastas. Annars blir trädet snabbt förvirrande och felbenäget. Det är därför den iterativa versionen är att föredra. Tanken är att gå igenom det gamla trädet och det nya trädet, som du skulle göra i förstöraren, klona alla noder som finns i det gamla trädet men inte de nya.

Med den här metoden är implementeringen av det binära sökträdet alltid i ett hälsosamt tillstånd och kan tas bort av förstöraren även i ett ofullständigt tillstånd. Om ett undantag inträffar är allt du behöver göra att instruera destruktören att ta bort det halvfärdiga trädet. uppdragsoperatörkan enkelt implementeras med Copy & Swap.

Skapa ett binärt sökträd

Optimala binära sökträd är otroligt effektiva om de hanteras på rätt sätt. Några regler för binära sökträd:

En föräldernod har högst 2 underordnade noder.
Den vänstra underordnade noden är alltid mindre än den överordnade noden.
En giltig underordnad nod är alltid större än eller lika med den överordnade noden.

Arrayen som kommer att användas för att bygga det binära sökträdet:

En basheltalsmatris med sju värden i osorterad ordning.
Det första värdet i arrayen är 10, så det första steget i att bygga trädet är att skapa en 10 rotnod, som visas här.
Med en uppsättning rotnoder kommer alla andra värden att vara barn till denna nod. Med hänvisning till reglerna är det första steget som måste tas för att lägga till 7 i trädet att jämföra det med rotnoden.
Om värdet 7 är mindre än 10, blir det den vänstra underordnade noden.
Om värdet 7 är större än eller lika med 10, flyttas det åt höger. Eftersom 7 är känt för att vara mindre än 10, anges den som den vänstra underordnade noden.
Utför jämförelser rekursivt för varje element.
Följ samma mönster och gör samma jämförelse med det 14:e värdet i arrayen.
Jämför värdet 14 med rotnoden 10, med vetskapen om att 14 är rätt underordnad.
Gå genom arrayen,kom till 20.
Börja med att jämföra arrayen med 10, vilket som är störst. Så flytta till höger och jämför det med 14, han är över 14 och har inga barn till höger.
Nu finns det ett värde på 1. Följ samma mönster som de andra värdena, jämför 1 med 10, flytta till vänster och jämför med 7 och slutligen med det 1 vänstra barnet i den 7:e noden.
Om värdet är 5, jämför det med 10. Eftersom 5 är mindre än 10, gå till vänster och jämför det med 7.
När du vet att 5 är mindre än 7, fortsätt ner i trädet och jämför 5 med 1 värde.
Om 1 inte har några barn och 5 är större än 1, är 5 ett giltigt barn till 1 nod.
Sätt slutligen in värdet 8 i trädet.
När 8 är mindre än 10, flytta det till vänster och jämför det med 7, 8 är större än 7, så flytta det till höger och slutföra trädet, vilket gör 8 till ett riktigt barn på 7.

Få och utvärderar den enkla elegansen hos optimala binära sökträd. Liksom många ämnen inom programmering kommer kraften i binära sökträd från deras förmåga att lösa data till små, relaterade komponenter. Från och med nu kan du arbeta med hela datasetet på ett organiserat sätt.

Potential binära sökproblem

Binära sökträd är bra, men det finns några varningar att tänka på. De är vanligtvis bara effektiva om de är balanserade. Ett balanserat träd är ett träd därskillnaden mellan höjderna på underträden för någon nod i trädet är högst en. Låt oss titta på ett exempel som kan hjälpa till att förtydliga reglerna. Låt oss föreställa oss att arrayen börjar som sorterbar.

Om du försöker köra en binär sökträdalgoritm på det här trädet, kommer den att fungera exakt som om den bara itererade genom arrayen tills det önskade värdet hittas. Kraften med binär sökning ligger i möjligheten att snabbt filtrera bort oönskade värden. När ett träd inte är balanserat ger det inte samma fördelar som ett balanserat träd.

Det är mycket viktigt att undersöka data som användaren arbetar med när man skapar ett binärt sökträd. Du kan integrera rutiner som slumpmässig array innan du implementerar ett binärt sökträd för heltal för att balansera det.

Beräkningsexempel för binära sökningar

Vi måste bestämma vilken typ av träd som kommer att resultera om 25 infogas i följande binära sökträd:

5 15

/ /

2 12 20

När du infogar x i ett träd T som ännu inte innehåller x, placeras nyckeln x alltid i ett nytt blad. I samband med detta kommer det nya trädet att se ut så här:

5 15

/ /

2 12 20

Vilken typ av träd skulle du få om du infogade 7 i följande binära sökträd?

5 15

/ /

2 12 20

Svar:

5 15

/ / /

2 7 12 20

Ett binärt sökträd kan användas för att lagra vilket objekt som helst. Fördelen med att använda ett binärt sökträd istället för en länkad lista är att om trädet är någorlunda balanserat och mer likt ett "fullt" träd än ett "linjärt", kan infogning, sökning och alla raderingsoperationer implementeras för att köras i O(log N) tid.