Binarno iskalno drevo - strukturirana baza podatkov, ki vsebuje vozlišča, dve povezavi do drugih vozlišč, desno in levo. Vozlišča so objekt razreda, ki ima podatke, NULL pa je znak, ki označuje konec drevesa.
Pogosto se imenuje BST, ki ima posebno lastnost: vozlišča, večja od korena, se nahajajo desno od njega, manjša pa levo.
Splošna teorija in terminologija
V binarnem iskalnem drevesu je vsako vozlišče, razen korena, povezano z usmerjenim robom od enega vozlišča do drugega, ki se imenuje nadrejeno. Vsako od njih je mogoče povezati s poljubnim številom vozlišč, imenovanih otrok. Vozlišča brez "otrok" se imenujejo listi (zunanja vozlišča). Elementi, ki niso listi, se imenujejo notranji. Vozlišča z istim staršem so bratje in sestre. Najvišje vozlišče se imenuje koren. V BST vsakemu vozlišču dodelite element in se prepričajte, da ima zanj nastavljeno posebno lastnost.
Drevesna terminologija:
- Globina vozlišča je število robov, definiranih od korena do njega.
- Višina vozlišča je število robov, definiranih od njega do najglobljega lista.
- Višina drevesa je določena z višino korenine.
- Binarno iskalno drevo je posebna zasnova, ki zagotavlja najboljše razmerje med višino in številom vozlišč.
- Višina h z N vozlišči največ O (log N).
To lahko enostavno dokažete s štetjem vozlišč na vsaki ravni, začenši od korena, ob predpostavki, da jih vsebuje največje število: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Če to rešimo za h, dobimo h=O (log n).
Prednosti lesa:
- Odražajo strukturna razmerja podatkov.
- Uporablja se za predstavljanje hierarhij.
- Zagotovite učinkovito namestitev in iskanje.
- Drevesa so zelo prilagodljivi podatki, ki vam omogočajo premikanje poddreves z minimalnim naporom.
Način iskanja
Na splošno, če želite ugotoviti, ali je vrednost v BST, zaženite drevo binarnega iskanja v njegovem korenu in ugotovite, ali izpolnjuje zahteve:
- bodi v korenu;
- bodi v levem poddrevesu korena;
- v desnem poddrevesu korena.
Če ni zadovoljen noben osnovni register, se v ustreznem poddrevesu izvede rekurzivno iskanje. Dejansko obstajata dve osnovni možnosti:
- Drevo je prazno - vrni false.
- Vrednost je v korenskem vozlišču - vrni true.
Upoštevati je treba, da binarno iskalno drevo z razvito shemo vedno začne iskati po poti od korena do lista. V najslabšem primeru gre vse do lista. Zato je najslabši čas sorazmeren z dolžino najdaljše poti od korenine do lista, kar je višina drevesa. Na splošno je to takrat, ko morate vedeti, koliko časa je potrebno za iskanje v odvisnosti od števila vrednosti, shranjenih v drevesu.
Z drugimi besedami, obstaja povezava med številom vozlišč v BST in višino drevesa, odvisno od njegove "oblike". V najslabšem primeru imajo vozlišča samo enega otroka in uravnoteženo binarno iskalno drevo je v bistvu povezan seznam. Na primer:
50
/
10
15
30
/
20
To drevo ima 5 vozlišč in višino=5. Iskanje vrednosti v območju 16-19 in 21-29 bo zahtevalo naslednjo pot od korena do lista (vozlišče, ki vsebuje vrednost 20), tj., bo potreben čas, sorazmeren s številom vozlišč. V najboljšem primeru imajo vsi 2 otroka in listi se nahajajo na isti globini.
To binarno iskalno drevo ima 7 vozlišč in višino=3. Na splošno bo imelo takšno drevo (polno drevo) višino približno log 2 (N), kjer je N število vozlišč v drevesu. Vrednost log 2 (N) je število krat (2), ki ga je mogoče razdeliti N, preden je dosežena nič.
Povzetek: najslabši čas, potreben za iskanje v BST, je O (višina drevesa). Najslabše "linearno" drevo je O(N), kjer je N število vozlišč v drevesu. V najboljšem primeru je "popolno" drevo O(log N).
BST binarni vložek
Sprašujem se, kje bi moral bitinovo vozlišče se nahaja v BST, morate razumeti logiko, nameščeno mora biti tam, kjer ga uporabnik najde. Poleg tega si morate zapomniti pravila:
- Dvojniki niso dovoljeni, poskus vstavljanja podvojene vrednosti bo povzročil izjemo.
- Javna metoda vstavljanja uporablja pomožno rekurzivno "pomočniško" metodo za dejansko vstavljanje.
- Vozlišče, ki vsebuje novo vrednost, je vedno vstavljeno kot list v BST.
- Javna metoda vstavljanja vrne void, pomožna metoda pa vrne BSTnode. To naredi za obravnavo primera, ko je vozlišče, ki mu je bilo posredovano, nič.
Na splošno metoda pomoči kaže, da če je izvirno drevo binarnega iskanja prazno, je rezultat drevo z enim vozliščem. V nasprotnem primeru bo rezultat kazalec na isto vozlišče, ki je bilo posredovano kot argument.
Brisanje v binarnem algoritmu
Kot lahko pričakujete, brisanje elementa vključuje iskanje vozlišča, ki vsebuje vrednost, ki jo je treba odstraniti. V tej kodi je več stvari:
- BST uporablja pomožno, preobremenjeno metodo brisanja. Če elementa, ki ga iščete, ni v drevesu, bo pomožna metoda na koncu poklicana z n==null. To se ne šteje za napako, drevo se v tem primeru preprosto ne spremeni. Pomožna metoda za brisanje vrne vrednost – kazalec na posodobljeno drevo.
- Ko je list odstranjen, odstranitev iz binarnega iskalnega drevesa nastavi ustrezni podrejeni kazalec njegovega nadrejenega na nič ali koren na nič, če je odstranjenvozlišče je koren in nima otrok.
- Upoštevajte, da mora biti klic brisanja eden od naslednjih: root=izbriši (koren, ključ), n.setLeft (izbriši (n.getLeft (), ključ)), n.setRight (izbriši (n. getRight(), ključ)). Tako je v vseh treh primerih pravilno, da metoda delete preprosto vrne null.
- Ko je iskanje vozlišča, ki vsebuje vrednost, ki jo želite izbrisati, uspešno, so na voljo tri možnosti: vozlišče, ki ga želite izbrisati, je list (nima otrok), vozlišče, ki ga želite izbrisati, ima enega podrejenega, ima dva otroci.
- Ko ima vozlišče, ki ga odstranimo, enega otroka, ga lahko preprosto zamenjaš z podrejenim, pri čemer vrneš kazalec na otroka.
- Če ima vozlišče, ki ga želite izbrisati, nič ali 1 podrejenih, potem bo metoda brisanja "sledila poti" od korena do tega vozlišča. Torej je najslabši čas sorazmeren z višino drevesa, tako za iskanje kot za vstavljanje.
Če ima vozlišče, ki ga je treba odstraniti, dva otroka, se izvedejo naslednji koraki:
- Poiščite vozlišče, ki ga želite izbrisati, po poti od korena do njega.
- Poiščite najmanjšo vrednost v v desnem poddrevesu, nadaljujte po poti do lista.
- Rekurzivno odstranite vrednost v, sledite isti poti kot v koraku 2.
- Tako se v najslabšem primeru pot od korena do lista izvede dvakrat.
Vrstni red prehodov
Prehod je proces, ki obišče vsa vozlišča v drevesu. Ker je binarno iskalno drevo C nelinearna podatkovna struktura, ni enoličnega prehoda. Na primer, včasih več algoritmov prehodarazvrščeni v naslednji dve vrsti:
- globina prečkanja;
- prvi prehod.
Obstaja samo ena vrsta prečkanja širine - mimo nivoja. Ta prehod obišče vozlišča na nivoju navzdol in levo, zgoraj in desno.
Obstajajo tri različne vrste globinskih prehodov:
- Prejem prednaročila - najprej obiščite starša in nato levega in desnega otroka.
- Prehajanje v vrstni red - obisk levega otroka, nato starša in desnega otroka.
- Mimo poštnega naročila - obisk levega otroka, nato desnega otroka, nato starša.
Primer štirih prehodov binarnega iskalnega drevesa:
- Prednaročilo - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- Po naročilu - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- Naročilo - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Slika prikazuje vrstni red obiska vozlišč. Številka 1 je prvo vozlišče v določenem prehodu, 7 pa zadnje vozlišče.
Ta splošna prehoda je mogoče predstaviti kot en sam algoritem, ob predpostavki, da je vsako vozlišče obiskano trikrat. Eulerjev ogled je sprehod okoli binarnega drevesa, kjer je vsak rob obravnavan kot stena, ki je uporabnik ne more prečkati. V tem sprehodu bo vsako vozlišče obiskano bodisi na levi, bodisi spodaj ali na desni. Eulerjev ogled, ki obišče vozlišča na levi, povzroči, da se predlog zaobide. Ko obiščete spodnja vozlišča, jih prečkate po vrstnem redu. In ko obiščete vozlišča na desni - dobiteobhod po korakih.
Navigacija in odpravljanje napak
Za lažje krmarjenje po drevesu ustvarite funkcije, ki najprej preverijo, ali so levi ali desni otrok. Če želite spremeniti položaj vozlišča, mora obstajati enostaven dostop do kazalca na nadrejenem vozlišču. Pravilna implementacija drevesa je zelo težka, zato morate poznati in uporabiti postopke odpravljanja napak. Binarno iskalno drevo z implementacijo ima pogosto kazalce, ki dejansko ne kažejo smeri vožnje.
Za ugotovitev vsega tega se uporablja funkcija, ki preveri, ali je drevo lahko pravilno, in pomaga najti številne napake. Na primer, preveri, ali je nadrejeno vozlišče podrejeno vozlišče. Z assert(is_wellformed(root)) je mogoče veliko napak ujeti prezgodaj. Z uporabo nekaj danih prelomnih točk v tej funkciji lahko tudi natančno določite, kateri kazalec je napačen.
Function Konsolenausgabe
Ta funkcija splakne celotno drevo v konzolo in je zato zelo uporabna. Vrstni red, v katerem se izvede izhodni cilj drevesa, je:
- Če želite to narediti, morate najprej določiti, katere informacije bodo izšle skozi vozlišče.
- Prav tako morate vedeti, kako široko in visoko je drevo, da upoštevate, koliko prostora ostane.
- Naslednje funkcije izračunajo te informacije za drevo in vsako poddrevo. Ker lahko v konzolo pišete samo vrstico za vrstico, boste morali natisniti tudi drevesno vrstico za vrstico.
- Zdaj potrebujemo drug način za umikcelotno drevo, ne samo vrstica za vrstico.
- S pomočjo funkcije dump lahko preberete drevo in znatno izboljšate izhodni algoritem, kar zadeva hitrost.
Vendar pa bo to funkcijo težko uporabljati na velikih drevesih.
Kopiraj konstruktor in destruktor
Ker drevo ni trivialna podatkovna struktura, je bolje implementirati konstruktor kopiranja, destruktor in operator dodelitve. Destruktor je enostavno izvesti rekurzivno. Za zelo velika drevesa lahko obvlada "prelivanje kopice". V tem primeru se oblikuje iterativno. Ideja je odstraniti list, ki predstavlja najmanjšo vrednost vseh listov, torej je na levi strani drevesa. Odrezovanje prvih listov ustvari nove in drevo se skrči, dokler končno ne preneha obstajati.
Konstruktor kopiranja se lahko izvaja tudi rekurzivno, vendar bodite previdni, če se vrže izjema. V nasprotnem primeru drevo hitro postane zmedeno in nagnjeno k napakam. Zato je prednostna iterativna različica. Ideja je, da greste skozi staro drevo in novo drevo, kot bi v destruktorju, klonirate vsa vozlišča, ki so v starem drevesu, ne pa nova.
S to metodo je izvedba drevesa binarnega iskanja vedno v zdravem stanju in jo lahko destruktor odstrani tudi v nepopolnem stanju. Če pride do izjeme, morate samo naročiti destruktorju, da izbriše delno drevo. operaterja dodelitveje mogoče enostavno implementirati z uporabo Copy & Swap.
Ustvarjanje binarnega iskalnega drevesa
Optimalna drevesa binarnega iskanja so neverjetno učinkovita, če jih pravilno upravljate. Nekaj pravil za drevesa binarnega iskanja:
- Nadrejeno vozlišče ima največ 2 podrejeni vozlišči.
- Levo podrejeno vozlišče je vedno manjše od nadrejenega.
- Veljavno podrejeno vozlišče je vedno večje ali enako nadrejenemu vozlišču.
Matrika, ki bo uporabljena za izgradnjo binarnega iskalnega drevesa:
- Osnovni niz sedmih vrednosti v nerazvrščenem vrstnem redu.
- Prva vrednost v matriki je 10, zato je prvi korak pri gradnji drevesa ustvariti korensko vozlišče 10, kot je prikazano tukaj.
- Z nizom korenskih vozlišč bodo vse druge vrednosti podrejene tega vozlišča. Glede na pravila je prvi korak za dodajanje 7 drevesu, da ga primerjamo s korenskim vozliščem.
- Če je vrednost 7 manjša od 10, bo postalo levo podrejeno vozlišče.
- Če je vrednost 7 večja ali enaka 10, se bo premaknila v desno. Ker je znano, da je 7 manj kot 10, je označeno kot levo podrejeno vozlišče.
- Rekurzivno izvajajte primerjave za vsak element.
- Po istem vzorcu izvedite enako primerjavo s 14. vrednostjo v matriki.
- Primerjava vrednosti 14 s korenskim vozliščem 10, pri čemer vemo, da je 14 pravilen otrok.
- Sprehod skozi niz,pridi do 20.
- Začnite s primerjavo matrike z 10, kar je večje. Zato se premaknite v desno in primerjajte s 14, on je starejši od 14 let in nima otrok na desni.
- Zdaj je vrednost 1. Po istem vzorcu kot druge vrednosti primerjajte 1 z 10, se pomaknite v levo in primerjajte s 7 in končno z 1 levim podrejenim otrokom 7. vozlišča.
- Če je vrednost 5, jo primerjaj z 10. Ker je 5 manj kot 10, pojdi na levo in jo primerjaj s 7.
- Veš, da je 5 manj kot 7, nadaljuj po drevesu in primerjaj 5 z 1 vrednostjo.
- Če 1 nima otrok in je 5 večje od 1, je 5 veljaven podrejeni element 1 vozlišča.
- Nazadnje vstavite vrednost 8 v drevo.
- Ko je 8 manj kot 10, ga premaknite v levo in primerjajte s 7, 8 je večje od 7, zato ga premaknite v desno in dokončajte drevo, tako da bo 8 pravilen otrok 7.
Pridobivanje in vrednotenje preproste elegance optimalnih dreves binarnega iskanja. Kot mnoge teme v programiranju, moč dreves binarnega iskanja izvira iz njihove zmožnosti razreševanja podatkov v majhne, povezane komponente. Od zdaj naprej lahko organizirano delate s celotnim naborom podatkov.
Možne težave z binarnim iskanjem
Drevesa binarnega iskanja so odlična, vendar je treba upoštevati nekaj opozoril. Običajno so učinkoviti le, če so uravnoteženi. Uravnoteženo drevo je drevo, v kateremrazlika med višinami poddreves katerega koli vozlišča v drevesu je največ ena. Poglejmo si primer, ki bi lahko pomagal razjasniti pravila. Predstavljajmo si, da se matrika začne kot razvršljiva.
Če poskusite zagnati algoritem binarnega iskalnega drevesa na tem drevesu, bo deloval natanko tako, kot če bi samo ponavljal matriko, dokler ni najdena želena vrednost. Moč binarnega iskanja je v zmožnosti hitrega filtriranja neželenih vrednosti. Če drevo ni uravnoteženo, ne bo zagotovilo enakih koristi kot uravnoteženo drevo.
Zelo pomembno je, da pri ustvarjanju binarnega iskalnega drevesa preučite podatke, s katerimi uporabnik dela. Pred implementacijo binarnega drevesa iskanja celih števil lahko integrirate rutine, kot je naključna matrika, da jo uravnotežite.
Primeri izračuna binarnega iskanja
Ugotoviti moramo, kakšno drevo bo nastalo, če se 25 vstavi v naslednje binarno iskalno drevo:
10
/
/
5 15
/ /
/ /
2 12 20
Ko vstavite x v drevo T, ki še ne vsebuje x, se ključ x vedno postavi v nov list. V zvezi s tem bo novo drevo izgledalo takole:
10
/
/
5 15
/ /
/ /
2 12 20
25
Kakšno drevo bi dobili, če bi v naslednje binarno iskalno drevo vstavili 7?
10
/
/
5 15
/ /
/ /
2 12 20
Odgovor:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
Binarno iskalno drevo se lahko uporablja za shranjevanje katerega koli predmeta. Prednost uporabe binarnega iskalnega drevesa namesto povezanega seznama je v tem, da če je drevo razumno uravnoteženo in je bolj podobno "polnemu" drevesu kot "linearnemu", se lahko izvajajo operacije vstavljanja, iskanja in brisanja, ki se izvajajo v O(log N) čas.
