Kaj je binarno drevo iskanja?
Binarno drevo iskanja je napreden algoritem, ki se uporablja za analizo vozlišča, njegovih levih in desnih vej, ki so modelirane v drevesni strukturi in vrnejo vrednost. BST je zasnovan na arhitekturi osnovnega algoritma binarnega iskanja; zato omogoča hitrejše iskanje, vstavljanje in odstranjevanje vozlišč. Zaradi tega je program res hiter in natančen.
V tej vadnici o strukturi podatkov boste izvedeli:
- Kaj je binarno drevo iskanja?
- Atributi binarnega drevesa iskanja
- Zakaj potrebujemo binarno drevo iskanja?
- Vrste binarnih dreves
- Kako deluje binarno drevo iskanja?
- Pomembni pogoji
Atributi binarnega drevesa iskanja
BST je sestavljen iz več vozlišč in je sestavljen iz naslednjih atributov:
- Vozlišča drevesa so predstavljena v odnosu starš-otrok
- Vsako nadrejeno vozlišče ima lahko nič podrejenih vozlišč ali največ dve podvozli ali poddrevesi na levi in desni strani.
- Vsako pod drevo, znano tudi kot binarno drevo iskanja, ima podveje na desni in levi strani sebe.
- Vsa vozlišča so povezana s pari ključ / vrednost.
- Ključi vozlišč, prisotnih v levem poddrevesu, so manjši od ključev njihovega nadrejenega vozlišča
- Podobno imajo ključi levega poddrevesa manjše vrednosti kot ključi nadrejenega vozlišča.
- Tam je glavno vozlišče ali nadrejena raven 11. Pod njim so leva in desna vozlišča / veje s svojimi ključnimi vrednostmi
- Desno pod drevo ima vrednosti ključev večje od nadrejenega vozlišča
- Levo pod drevo ima vrednosti kot nadrejeno vozlišče
Zakaj potrebujemo binarno drevo iskanja?
- Dva glavna dejavnika, zaradi katerih je binarno drevo iskanja optimalna rešitev za resnične težave, sta hitrost in natančnost.
- Ker je binarno iskanje v obliki, podobni veji, z odnosi med starši in otroki, algoritem ve, na kateri lokaciji drevesa je treba elemente iskati. To zmanjša število primerjav ključ-vrednost, ki jih mora narediti program, da poišče želeni element.
- Poleg tega vozlišče ve, katero drevesno stran je treba iskati, če je element, ki ga je treba iskati večji ali manjši od nadrejenega vozlišča. Razlog je v tem, da je levo pod drevo vedno manjše od nadrejenega vozlišča, desno poddrevo pa ima vrednosti vedno enake ali večje od nadrejenega vozlišča.
- BST se pogosto uporablja za izvajanje zapletenih iskanj, robustne logike iger, samodejnega dokončanja dejavnosti in grafike.
- Algoritem učinkovito podpira operacije, kot so iskanje, vstavljanje in brisanje.
Vrste binarnih dreves
Tri vrste binarnih dreves so:
- Popolno binarno drevo: Vse ravni v drevesih so polne možnih izjem na zadnji ravni. Podobno so vsa vozlišča polna in usmerjajo skrajno levo.
- Polno binarno drevo: Vsa vozlišča imajo 2 podrejena vozlišča, razen lista.
- Uravnoteženo ali popolno binarno drevo: v drevesu imajo vsa vozlišča dva otroka. Poleg tega obstaja enaka raven vsakega podvozla.
Kako deluje binarno drevo iskanja?
Drevo ima vedno korensko vozlišče in nadaljnja podrejena vozlišča, bodisi na levi ali desni. Algoritem izvede vse operacije s primerjavo vrednosti s korenom in njegovimi nadaljnjimi podrejenimi vozlišči v levem ali desnem pod drevesu.
Odvisno od elementa, ki ga je treba vstaviti, poiskati ali izbrisati, lahko algoritem po primerjavi lahko enostavno spusti levo ali desno poddrevo korenskega vozlišča.
BST v prvi vrsti ponuja naslednje tri vrste operacij:
- Iskanje: poišče element iz binarnega drevesa
- Vstavi: doda element v binarno drevo
- Delete: izbriši element iz binarnega drevesa
Vsaka operacija ima svojo strukturo in način izvedbe / analize, najbolj zapletena pa je operacija Delete.
Iskalna operacija
Vedno zaženite drevo za analiziranje na korenskem vozlišču in se nato pomaknite naprej v desno ali levo poddrevo korenskega vozlišča, odvisno od tega, ali je element, ki se nahaja, manjši ali večji od korenskega.
- Element za iskanje je 10
- Primerjajte element s korenskim vozliščem 12, 10 <12, zato se premaknete v levo poddrevo. Ni treba analizirati desnega poddrevesa
- Zdaj primerjajte 10 z vozliščem 7, 10> 7, zato se pomaknite na desno poddrevo
- Nato primerjajte 10 z naslednjim vozliščem, ki je 9, 10> 9, poglejte v desno podrevo podrejeno
- 10 ujemanj z vrednostjo v vozlišču, 10 = 10, vrne vrednost uporabniku.
Vstavite postopek
To je zelo neposredna operacija. Najprej se vstavi korensko vozlišče, nato se naslednja vrednost primerja s korenskim vozliščem. Če je vrednost večja od korena, se doda v desno poddrevo, če je manjša od korena, pa se doda v levo poddrevo.
- Obstaja seznam 6 elementov, ki jih je treba vstaviti v BST po vrsti od leve proti desni
- Vstavite 12 kot korensko vozlišče in primerjajte naslednji vrednosti 7 in 9 za ustrezno vstavljanje v desno in levo poddrevo
- Preostale vrednosti 19, 5 in 10 primerjajte s korenskim vozliščem 12 in jih ustrezno namestite. 19> 12 ga postavi kot desnega otroka 12, 5 <12 in 5 <7, zato ga postavi kot levega otroka 7 let.
- Zdaj primerjajte 10, 10 je <12 in 10 je> 7 & 10 je> 9, mesto 10 postavite kot desno poddrevo 9.
Izbriši operacije
Izbriši je najbolj napredna in zapletena med vsemi ostalimi operacijami. V BST je za brisanje obravnavano več primerov.
- Primer 1 - Vozlišče z nič podrejenimi: to je najlažje, samo izbrisati morate vozlišče, ki nima nadaljnjih podrejenih na desni ali levi.
- Primer 2 - Vozlišče z enim otrokom: ko vozlišče izbrišete, njegovo podrejeno vozlišče preprosto povežite z nadrejenim vozliščem izbrisane vrednosti.
- Primer 3 Vozlišče z dvema otrokoma: to je najtežja situacija in deluje po naslednjih dveh pravilih
- 3a - V predhodniku naročila: vozlišče z dvema podrejenima morate izbrisati in nadomestiti z največjo vrednostjo v levem poddrevu izbrisanega vozlišča
- 3b - V vrstnem redu naslednika: vozlišče z dvema podrejenima morate izbrisati in nadomestiti z največjo vrednostjo na desnem poddrevu izbrisanega vozlišča
- To je prvi primer brisanja, v katerem izbrišete vozlišče, ki nima podrejenih elementov. Kot lahko vidite na diagramu, 19, 10 in 5 nima otrok. Izbrisali pa bomo 19.
- Izbrišite vrednost 19 in odstranite povezavo z vozlišča.
- Oglejte si novo strukturo BST brez 19
- To je drugi primer brisanja, v katerem izbrišete vozlišče z 1 podrejenim, kot lahko vidite na diagramu, da ima 9 enega podrejenega.
- Izbrišite vozlišče 9 in ga nadomestite z njegovim podrejenim 10 ter dodajte povezavo od 7 do 10
- Oglejte si novo strukturo BST brez 9
- Tukaj boste izbrisali vozlišče 12, ki ima dva otroka
- Izbris vozlišča se izvede na podlagi pravila predhodnika po vrstnem redu, kar pomeni, da ga bo nadomestil največji element v levem poddrevesu 12.
- Izbrišite vozlišče 12 in ga zamenjajte z 10, saj je to največja vrednost v levem poddrevesu
- Oglejte si novo strukturo BST po brisanju 12
- 1 Izbrišite vozlišče 12, ki ima dva podrejena elementa
- 2 Izbris vozlišča bo potekal na podlagi pravila In Order Successor, kar pomeni, da ga bo nadomestil največji element v desnem poddrevu 12
- 3 Izbrišite vozlišče 12 in ga zamenjajte z 19, saj je največja vrednost na desnem poddrevesu
- 4. Oglejte si novo strukturo BST po brisanju 12
Pomembni pogoji
- Vstavi - vstavi element v drevo / ustvari drevo.
- Iskanje - išče element v drevesu.
- Preorder Preorder - prehod drevesa na način prednaročila.
- Prehod po vrstnem redu - drevo prečka po vrstnem redu.
- Prehod po naročilu - prehod drevesa na način po naročilu.
Povzetek
- BST je napredni algoritem, ki izvaja različne operacije na podlagi primerjave vrednosti vozlišča s korenskim vozliščem.
- Katera koli točka v hierarhiji starš-otrok predstavlja vozlišče. Vsaj eno nadrejeno ali korensko vozlišče ostane ves čas prisotno.
- Obstajata levo in desno drevo. Levo poddrevo vsebuje vrednosti, ki so manjše od korenskega vozlišča. Vendar desno poddrevo vsebuje vrednost, ki je večja od korenskega vozlišča.
- Vsako vozlišče ima lahko nič, enega ali dva otroka.
- Binarno drevo iskanja omogoča primarne operacije, kot so iskanje, vstavljanje in brisanje.
- Najbolj zapleteno brisanje ima več primerov, na primer vozlišče brez otroka, vozlišče z enim otrokom in vozlišče z dvema otrokoma.
- Algoritem se uporablja v resničnih rešitvah, kot so igre, samodokončanje podatkov in grafika.