Binêre soekboom - 'n gestruktureerde databasis wat nodusse, twee skakels na ander nodusse, regs en links bevat. Nodes is 'n voorwerp van die klas wat data het, en NULL is die teken wat die einde van die boom aandui.
Daar word dikwels na verwys as BST, wat 'n spesiale eienskap het: nodusse groter as die wortel is regs daarvan geleë, en kleineres aan die linkerkant.
Algemene teorie en terminologie
In 'n binêre soekboom word elke nodus, die wortel uitgesluit, deur 'n gerigte rand van een nodus na 'n ander verbind, wat die ouer genoem word. Elkeen van hulle kan gekoppel word aan 'n arbitrêre aantal nodusse, genoem kinders. Nodusse sonder "kinders" word blare (buitenste nodusse) genoem. Elemente wat nie blare is nie, word intern genoem. Nodusse met dieselfde ouer is broers en susters. Die boonste nodus word die wortel genoem. In BST, ken 'n element aan elke nodus toe en maak seker dat hulle 'n spesiale eienskap vir hulle het.
Boomterminologie:
- Die diepte van 'n nodus is die aantal rande wat vanaf die wortel tot dit gedefinieer is.
- Hoogte van 'n nodus is die aantal rande wat van dit tot die diepste blaar gedefinieer word.
- Die hoogte van die boom word bepaal deur die hoogte van die wortel.
- Binêre soekboom is 'n spesiale ontwerp, dit bied die beste verhouding van hoogte en aantal nodusse.
- Hoogte h met N nodusse hoogstens O (log N).
Jy kan dit maklik bewys deur die nodusse op elke vlak te tel, vanaf die wortel, met die veronderstelling dat dit die grootste aantal daarvan bevat: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Om dit vir h op te los gee h=O (log n).
Voordele van hout:
- Weespieël die strukturele verwantskappe van die data.
- Gebruik om hiërargieë voor te stel.
- Verseker doeltreffende installasie en soektog.
- Bome is baie buigsame data, wat jou toelaat om subbome met minimale moeite te skuif.
Soekmetode
Oor die algemeen, om te bepaal of 'n waarde in die BST is, begin 'n binêre soekboom by sy wortel en bepaal of dit aan die vereistes voldoen:
- wees aan die wortel;
- wees in die linker subboom van wortel;
- in die regter subboom van wortel.
As geen basisregister bevredig is nie, word 'n rekursiewe soektog in die ooreenstemmende subboom uitgevoer. Daar is eintlik twee basiese opsies:
- Die boom is leeg - gee vals terug.
- Die waarde is in die wortelnodus - gee terug waar.
Daar moet kennis geneem word dat 'n binêre soekboom met 'n ontwikkelde skema altyd langs die pad vanaf die wortel na die blaar begin soek. In die ergste geval gaan dit tot by die blaar. Daarom is die slegste tyd eweredig aan die lengte van die langste pad van die wortel na die blaar, wat die hoogte van die boom is. Oor die algemeen is dit wanneer jy moet weet hoe lank dit neem om op te soek as 'n funksie van die aantal waardes wat in die boom gestoor is.
Met ander woorde, daar is 'n verband tussen die aantal nodusse in 'n BST en die hoogte van 'n boom, afhangende van sy "vorm". In die ergste geval het nodusse net een kind, en 'n gebalanseerde binêre soekboom is in wese 'n gekoppelde lys. Byvoorbeeld:
50
/
10
15
30
/
20
Hierdie boom het 5 nodusse en hoogte=5. Om waardes in die reeks 16-19 en 21-29 te vind, sal die volgende pad van die wortel na die blaar vereis (die nodus wat die waarde 20 bevat), m.a.w., sal dit tyd neem eweredig aan die aantal nodusse. Op sy beste het hulle almal 2 kinders, en die blare is op dieselfde diepte geleë.
Hierdie binêre soekboom het 7 nodusse en hoogte=3. Oor die algemeen sal 'n boom soos hierdie (vol boom) 'n hoogte van ongeveer log 2 (N) hê, waar N die aantal nodusse in die boom is.. Die waarde van log 2 (N) is die aantal kere (2) wat N gedeel kan word voordat nul bereik word.
Opsomming: die slegste tyd wat nodig is om in BST te soek, is O (boomhoogte). Die ergste geval "lineêre" boom is O(N), waar N die aantal nodusse in die boom is. Op sy beste is 'n "volledige" boom O(log N).
BST-binêre insetsel
Wonder waar moet weesdie nuwe nodus is in die BST geleë, jy moet die logika verstaan, dit moet geplaas word waar die gebruiker dit vind. Daarbenewens moet jy die reëls onthou:
- Duplikate word nie toegelaat nie, 'n poging om 'n duplikaatwaarde in te voeg sal 'n uitsondering veroorsaak.
- Die publieke invoegingsmetode gebruik 'n helper-rekursiewe "helper"-metode om werklik in te voeg.
- 'n Nodus wat 'n nuwe waarde bevat, word altyd as 'n blaar in BST ingevoeg.
- Die publieke invoegingsmetode gee leeg, maar die helpermetode gee 'n BSTnode terug. Dit doen dit om die geval te hanteer waar die nodus wat daarheen gestuur is, nul is.
Oor die algemeen dui die helper-metode aan dat as die oorspronklike binêre soekboom leeg is, die resultaat 'n boom met een nodus is. Andersins sal die resultaat 'n wyser wees na dieselfde nodus wat as 'n argument deurgegee is.
Delete in binêre algoritme
Soos jy kan verwag, behels die uitvee van 'n element om 'n nodus te vind wat die waarde bevat wat verwyder moet word. Daar is verskeie dinge in hierdie kode:
- BST gebruik 'n helper, oorlaaide verwyderingsmetode. As die element waarna jy soek nie in die boom is nie, sal die helper metode uiteindelik geroep word met n==null. Dit word nie as 'n fout beskou nie, die boom verander eenvoudig nie in hierdie geval nie. Die skrap helper metode gee 'n waarde terug - 'n wyser na die opgedateerde boom.
- Wanneer 'n blaar verwyder word, stel die verwydering van die binêre soekboom die ooreenstemmende onderliggende wyser van sy ouer op nul, of die wortel op nul as die een wat verwyder worddie nodus is 'n wortel en het geen kinders nie.
- Let daarop dat die uitvee-oproep een van die volgende moet wees: root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight(), sleutel)). Dus, in al drie gevalle is dit korrek dat die delete metode bloot nul teruggee.
- Wanneer die soektog na die nodus wat die waarde bevat wat uitgevee moet word, slaag, is daar drie opsies: die nodus wat uitgevee moet word is 'n blaar (het geen kinders nie), die nodus wat uitgevee moet word het een kind, dit het twee kinders.
- Wanneer die nodus wat verwyder word een kind het, kan jy dit eenvoudig met 'n kind vervang en 'n wyser na die kind terugstuur.
- As die nodus wat uitgevee moet word, nul of 1 kinders het, sal die verwyderingsmetode "die pad volg" vanaf die wortel na daardie nodus. Die slegste tyd is dus eweredig aan die hoogte van die boom, vir beide soek en invoeging.
As die nodus wat verwyder moet word twee kinders het, word die volgende stappe geneem:
- Vind die nodus wat uitgevee moet word, volg die pad vanaf die wortel na dit.
- Vind die kleinste waarde van v in die regter subboom, gaan voort met die pad na die blaar.
- Verwyder die waarde van v rekursief, volg dieselfde pad as in stap 2.
- Dus, in die ergste geval, word die pad vanaf die wortel na die blaar twee keer uitgevoer.
Orde van dwarstrekke
Traversal is 'n proses wat alle nodusse in 'n boom besoek. Omdat 'n C-binêre soekboom 'n nie-lineêre datastruktuur is, is daar geen unieke deurkruising nie. Byvoorbeeld, soms verskeie deurkruisalgoritmesgegroepeer in die volgende twee tipes:
- kruisdiepte;
- eerste pas.
Daar is net een soort breedtekruising – om die vlak te omseil. Hierdie deurkruising besoek nodusse vlak af en links, bo en regs.
Daar is drie verskillende tipes dieptekruisings:
- Slaag voorafbestelling - besoek eers die ouer en dan die linker- en regterkind.
- Passing InOrder - besoek die linkerkind, dan die ouer en die regter kind.
- Verby die posbestelling - besoek die linkerkind, dan die regter kind, dan die ouer.
Voorbeeld vir vier deurkruisings van 'n binêre soekboom:
- Voorafbestelling - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- Posorder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- Vlakorde - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Die figuur toon die volgorde waarin nodusse besoek word. Die nommer 1 is die eerste nodus in 'n spesifieke deurkruising, en 7 is die laaste nodus.
Hierdie algemene deurkruisings kan as 'n enkele algoritme voorgestel word, met die veronderstelling dat elke nodus drie keer besoek word. Die Euler-toer is 'n wandeling om 'n binêre boom waar elke rand behandel word as 'n muur wat die gebruiker nie kan oorsteek nie. In hierdie stap sal elke nodus óf aan die linkerkant, óf onder, óf aan die regterkant besoek word. Die Euler-toer, wat die nodusse aan die linkerkant besoek, veroorsaak dat die voorsetsel omseil word. Wanneer die nodusse hieronder besoek word, word hulle in volgorde deurkruis. En wanneer die nodusse aan die regterkant besoek word - krystap-vir-stap omseil.
Navigasie en ontfouting
Om dit makliker te maak om deur die boom te navigeer, skep funksies wat eers kyk of hulle die linker- of regterkind is. Om die posisie van 'n nodus te verander, moet daar maklike toegang tot die wyser by die ouernodus wees. Om 'n boom korrek te implementeer is baie moeilik, so jy moet ontfoutingsprosesse ken en toepas. 'n Binêre soekboom met 'n implementering het dikwels wysers wat nie eintlik die reisrigting aandui nie.
Om dit alles uit te vind, word 'n funksie gebruik wat kyk of die boom korrek kan wees, en help om baie foute te vind. Byvoorbeeld, dit kontroleer of die ouernodus 'n kindnodus is. Met assert(is_wellformed(root)) kan baie foute voortydig opgevang word. Deur 'n paar gegewe breekpunte binne hierdie funksie te gebruik, kan jy ook presies bepaal watter wyser verkeerd is.
Function Konsolenausgabe
Hierdie funksie spoel die hele boom na die konsole en is dus baie nuttig. Die volgorde waarin die boom-uitsetdoel uitgevoer word, is:
- Om dit te doen, moet jy eers bepaal watter inligting deur die nodus uitgevoer sal word.
- En jy moet ook weet hoe wyd en hoog die boom is om rekening te hou met hoeveel spasie om te laat.
- Die volgende funksies bereken hierdie inligting vir die boom en elke subboom. Aangesien jy net reël vir reël na die konsole kan skryf, sal jy ook die boom reël vir reël moet druk.
- Nou het ons 'n ander manier nodig om te onttrekdie hele boom, nie net reël vir reël nie.
- Met die hulp van die stortingsfunksie kan jy die boom lees en die uitsetalgoritme aansienlik verbeter, wat spoed betref.
Hierdie funksie sal egter moeilik wees om op groot bome te gebruik.
Kopieer konstruktor en vernietiger
Omdat 'n boom nie 'n triviale datastruktuur is nie, is dit beter om 'n kopiekonstruktor, 'n vernietiger en 'n opdragoperateur te implementeer. Die vernietiger is maklik om rekursief te implementeer. Vir baie groot bome kan dit "hoop oorloop" hanteer. In hierdie geval word dit iteratief geformuleer. Die idee is om die blaar te verwyder wat die kleinste waarde van alle blare verteenwoordig, so dit is aan die linkerkant van die boom. Om die eerste blare af te sny, skep nuwes, en die boom krimp totdat dit uiteindelik ophou bestaan.
Die kopie-konstruktor kan ook rekursief geïmplementeer word, maar wees versigtig as 'n uitsondering gegooi word. Andersins word die boom vinnig verwarrend en foutief. Dit is hoekom die iteratiewe weergawe verkies word. Die idee is om deur die ou boom en die nuwe boom te gaan, soos jy sou in die vernietiger, en al die nodusse wat in die ou boom is, maar nie die nuwes, te kloneer nie.
Met hierdie metode is die implementering van die binêre soekboom altyd in 'n gesonde toestand en kan selfs in 'n onvolledige toestand deur die vernietiger verwyder word. As 'n uitsondering voorkom, hoef jy net die vernietiger te gee om die halfvoltooide boom uit te vee. opdrag operateurkan maklik geïmplementeer word met Kopieer en Ruil.
Skep 'n binêre soekboom
Optimale binêre soekbome is ongelooflik doeltreffend as dit reg bestuur word. Sommige reëls vir binêre soekbome:
- 'n Ouernodus het hoogstens 2 kindernodusse.
- Die linkerkindnodus is altyd kleiner as die ouernodus.
- 'n Geldige kindernodus is altyd groter as of gelyk aan die ouernodus.
Die skikking wat gebruik sal word om die binêre soekboom te bou:
- 'n Basis heelgetal skikking van sewe waardes in ongesorteerde volgorde.
- Die eerste waarde in die skikking is 10, dus die eerste stap in die bou van die boom is om 'n 10-wortelknoop te skep, soos hier getoon.
- Met 'n stel wortelnodusse sal alle ander waardes kinders van hierdie knoop wees. Met verwysing na die reëls, die eerste stap wat geneem moet word om 7 by die boom te voeg, is om dit met die wortelknoop te vergelyk.
- As die waarde 7 minder as 10 is, sal dit die linkerkindnodus word.
- As die waarde 7 groter as of gelyk aan 10 is, sal dit na regs beweeg. Aangesien dit bekend is dat 7 minder as 10 is, word dit as die linkerkindnodus aangewys.
- Voer rekursief vergelykings vir elke element uit.
- Volg dieselfde patroon, voer dieselfde vergelyking met die 14de waarde in die skikking uit.
- Vergelyk die waarde 14 met die wortelknooppunt 10, met die wete dat 14 die korrekte kind is.
- Loop deur die skikking,kom tot 20.
- Begin deur die skikking met 10 te vergelyk, wat ook al die grootste is. So skuif na regs en vergelyk dit met 14, hy is ouer as 14 en het geen kinders aan die regterkant nie.
- Nou is daar 'n waarde van 1. Volg dieselfde patroon as die ander waardes, vergelyk 1 met 10, beweeg na links en vergelyk met 7 en laastens met die 1 linker kind van die 7de nodus.
- As die waarde 5 is, vergelyk dit met 10. Aangesien 5 minder as 10 is, gaan na links en vergelyk dit met 7.
- Om te weet dat 5 minder as 7 is, gaan voort in die boom af en vergelyk 5 met 1 waarde.
- As 1 geen kinders het nie en 5 is groter as 1, dan is 5 'n geldige kind van 1 nodus.
- Voeg laastens die waarde 8 in die boom in.
- Wanneer 8 minder as 10 is, skuif dit na links en vergelyk dit met 7, 8 is groter as 7, so skuif dit na regs en voltooi die boom, maak 8 'n regte kind van 7.
Kry en evalueer die eenvoudige elegansie van optimale binêre soekbome. Soos baie onderwerpe in programmering, kom die krag van binêre soekbome uit hul vermoë om data in klein, verwante komponente op te los. Van nou af kan jy op 'n georganiseerde manier met die volledige datastel werk.
Potensiële Binêre Soekkwessies
Binêre soekbome is wonderlik, maar daar is 'n paar waarskuwings om in gedagte te hou. Hulle is gewoonlik net effektief as hulle gebalanseerd is. 'n Gebalanseerde boom is 'n boom waarindie verskil tussen die hoogtes van die subbome van enige nodus in die boom is hoogstens een. Kom ons kyk na 'n voorbeeld wat kan help om die reëls te verduidelik. Kom ons stel ons voor dat die skikking as sorteerbaar begin.
As jy probeer om 'n binêre soekboomalgoritme op hierdie boom te laat loop, sal dit presies werk asof dit net deur die skikking herhaal word totdat die verlangde waarde gevind is. Die krag van binêre soektog lê in die vermoë om ongewenste waardes vinnig uit te filter. Wanneer 'n boom nie gebalanseer is nie, sal dit nie dieselfde voordele as 'n gebalanseerde boom bied nie.
Dit is baie belangrik om die data te ondersoek waarmee die gebruiker werk wanneer 'n binêre soekboom geskep word. Jy kan roetines soos skikking-ewekansing integreer voordat jy 'n binêre soekboom vir heelgetalle implementeer om dit uit te balanseer.
Binêre soektog-berekeningvoorbeelde
Ons moet bepaal watter soort boom sal ontstaan as 25 in die volgende binêre soekboom ingevoeg word:
10
/
/
5 15
/ /
/ /
2 12 20
Wanneer x in 'n boom T ingevoeg word wat nog nie x bevat nie, word die sleutel x altyd in 'n nuwe blaar geplaas. In verband hiermee sal die nuwe boom so lyk:
10
/
/
5 15
/ /
/ /
2 12 20
25
Watter soort boom sal jy kry as jy 7 in die volgende binêre soekboom ingevoeg het?
10
/
/
5 15
/ /
/ /
2 12 20
Antwoord:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
'n Binêre soekboom kan gebruik word om enige voorwerp te stoor. Die voordeel van die gebruik van 'n binêre soekboom in plaas van 'n gekoppelde lys is dat indien die boom redelik gebalanseerd is en meer soos 'n "volle" boom as 'n "lineêre" boom is, invoeging, soek en alle uitvee bewerkings geïmplementeer kan word om in te loop. O(log N) tyd.
