Binárny vyhľadávací strom – štruktúrovaná databáza obsahujúca uzly, dva odkazy na ďalšie uzly, pravý a ľavý. Uzly sú objekt triedy, ktorý má dáta, a NULL je znak, ktorý označuje koniec stromu.
Často sa označuje ako BST, ktorý má špeciálnu vlastnosť: uzly väčšie ako koreň sa nachádzajú napravo od neho a menšie naľavo.
Všeobecná teória a terminológia
V binárnom vyhľadávacom strome je každý uzol, s výnimkou koreňa, spojený orientovanou hranou z jedného uzla do druhého, ktorý sa nazýva rodič. Každý z nich môže byť pripojený k ľubovoľnému počtu uzlov, nazývaných deti. Uzly bez "detí" sa nazývajú listy (vonkajšie uzly). Prvky, ktoré nie sú listami, sa nazývajú vnútorné. Uzly s rovnakým rodičom sú súrodenci. Najvyšší uzol sa nazýva koreň. V BST priraďte prvok ku každému uzlu a uistite sa, že má preň nastavenú špeciálnu vlastnosť.
Stromová terminológia:
- Hĺbka uzla je počet hrán definovaných od koreňa k nemu.
- Výška uzla je počet hrán definovaných od neho po najhlbší list.
- Výška stromu je určená výškou koreňa.
- Binárny vyhľadávací strom je špeciálny dizajn, poskytuje najlepší pomer výšky a počtu uzlov.
- Výška h s N uzlami najviac O (log N).
To môžete ľahko dokázať spočítaním uzlov na každej úrovni, počnúc od koreňa, za predpokladu, že obsahuje najväčší počet z nich: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Toto riešenie pre h dostane h=O (log n).
Výhody dreva:
- Odrážajú štrukturálne vzťahy údajov.
- Používa sa na znázornenie hierarchií.
- Zabezpečte efektívnu inštaláciu a vyhľadávanie.
- Stromy sú veľmi flexibilné údaje, ktoré vám umožňujú presúvať podstromy s minimálnym úsilím.
Metóda vyhľadávania
Vo všeobecnosti, ak chcete zistiť, či je hodnota v BST, spustite binárny vyhľadávací strom v jeho koreni a zistite, či spĺňa požiadavky:
- byť pri koreni;
- byť v ľavom podstrome koreňa;
- v pravom podstrome koreňa.
Ak nie je splnený žiadny základný register, vykoná sa rekurzívne vyhľadávanie v príslušnom podstrome. V skutočnosti existujú dve základné možnosti:
- Strom je prázdny – vráťte hodnotu false.
- Hodnota je v koreňovom uzle – vráti true.
Treba si uvedomiť, že binárny vyhľadávací strom s rozvinutou schémou vždy začína hľadať pozdĺž cesty od koreňa po list. V horšom prípade ide až po list. Preto je najhorší čas úmerný dĺžke najdlhšej cesty od koreňa po list, čo je výška stromu. Vo všeobecnosti je to vtedy, keď potrebujete vedieť, ako dlho trvá vyhľadávanie v závislosti od počtu hodnôt uložených v strome.
Inými slovami, existuje vzťah medzi počtom uzlov v BST a výškou stromu v závislosti od jeho „tvaru“. V najhoršom prípade majú uzly iba jedného potomka a vyvážený binárny vyhľadávací strom je v podstate prepojený zoznam. Napríklad:
50
/
10
15
30
/
20
Tento strom má 5 uzlov a výšku=5. Na nájdenie hodnôt v rozsahu 16-19 a 21-29 bude potrebná nasledujúca cesta od koreňa ku listu (uzol obsahujúci hodnotu 20), t.j., bude to trvať úmerne k počtu uzlov. V najlepšom prípade majú všetci 2 deti a listy sú umiestnené v rovnakej hĺbke.
Tento binárny vyhľadávací strom má 7 uzlov a výšku=3. Vo všeobecnosti bude mať strom ako tento (celý strom) výšku približne log 2 (N), kde N je počet uzlov v strome. Hodnota log 2 (N) je počet, koľkokrát (2), koľkokrát (2) je možné rozdeliť N pred dosiahnutím nuly.
Zhrnutie: Najhorší čas potrebný na vyhľadávanie v BST je O (výška stromu). Najhorším prípadom „lineárneho“stromu je O(N), kde N je počet uzlov v strome. V najlepšom prípade je „úplný“strom O(log N).
BST binárna vložka
Pýtam sa, kde by mal byťnový uzol sa nachádza v BST, musíte pochopiť logiku, musí byť umiestnený tam, kde ho používateľ nájde. Okrem toho si musíte pamätať na pravidlá:
- Duplikáty nie sú povolené, pokus o vloženie duplicitnej hodnoty vyvolá výnimku.
- Verejná metóda vkladania používa na skutočné vloženie pomocnú rekurzívnu „pomocnú“metódu.
- Uzol obsahujúci novú hodnotu sa vždy vloží ako list v BST.
- Verejná metóda vkladania vracia hodnotu void, ale pomocná metóda vracia BSTnode. Robí to na riešenie prípadu, keď je uzol, ktorý mu bol odovzdaný, null.
Vo všeobecnosti pomocná metóda označuje, že ak je pôvodný binárny vyhľadávací strom prázdny, výsledkom je strom s jedným uzlom. V opačnom prípade bude výsledkom ukazovateľ na rovnaký uzol, ktorý bol odovzdaný ako argument.
Vymazanie v binárnom algoritme
Ako by ste mohli očakávať, odstránenie prvku zahŕňa nájdenie uzla, ktorý obsahuje hodnotu, ktorá sa má odstrániť. V tomto kóde je niekoľko vecí:
- BST používa pomocnú, preťaženú metódu odstránenia. Ak sa hľadaný prvok nenachádza v strome, pomocná metóda sa nakoniec zavolá s n==null. Toto sa nepovažuje za chybu, strom sa v tomto prípade jednoducho nemení. Pomocná metóda vymazania vráti hodnotu – ukazovateľ na aktualizovaný strom.
- Keď je list odstránený, odstránenie z binárneho vyhľadávacieho stromu nastaví zodpovedajúci podriadený ukazovateľ jeho rodiča na hodnotu null alebo koreň na hodnotu null, ak je odstránenýuzol je koreň a nemá žiadne deti.
- Všimnite si, že volanie delete musí byť jedno z nasledujúcich: root=delete (koreň, kľúč), n.setLeft (delete (n.getLeft (), kľúč)), n.setRight (delete(n. getRight(), kľúč)). Vo všetkých troch prípadoch je teda správne, že metóda odstránenia jednoducho vráti hodnotu null.
- Po úspešnom vyhľadávaní uzla obsahujúceho hodnotu, ktorá sa má vymazať, sú tri možnosti: uzol, ktorý sa má odstrániť, je list (nemá žiadne potomky), uzol, ktorý sa má odstrániť, má jedného potomka, má dve deti.
- Keď má odstraňovaný uzol jedného potomka, môžete ho jednoducho nahradiť potomkom a vrátiť mu ukazovateľ.
- Ak uzol, ktorý sa má vymazať, má nula alebo 1 potomka, metóda odstránenia bude „sledovať cestu“od koreňového k tomuto uzlu. Najhorší čas je teda úmerný výške stromu pre vyhľadávanie aj vkladanie.
Ak má uzol, ktorý sa má odstrániť, dve deti, vykonajú sa tieto kroky:
- Nájdite uzol, ktorý chcete odstrániť, podľa cesty od koreňa k nemu.
- Nájdite najmenšiu hodnotu v v pravom podstrome a pokračujte po ceste k listu.
- Rekurzívne odstráňte hodnotu v, postupujte rovnako ako v kroku 2.
- V najhoršom prípade sa teda cesta od koreňa k listu vykonáva dvakrát.
Poradie prechodov
Traversal je proces, ktorý navštevuje všetky uzly v strome. Pretože binárny vyhľadávací strom C je nelineárna dátová štruktúra, neexistuje žiadny jedinečný prechod. Napríklad niekedy niekoľko algoritmov prechoduzoskupené do nasledujúcich dvoch typov:
- hĺbka kríženia;
- prvý prechod.
Existuje len jeden druh šírkového prechodu – obchádzanie úrovne. Toto prechádzanie navštevuje uzly o úroveň nižšie a vľavo, hore a vpravo.
Existujú tri rôzne typy hĺbkových prechodov:
- Prechádza predobjednávkou – najskôr navštívte rodiča a potom ľavé a pravé dieťa.
- Passing InOrder – návšteva ľavého dieťaťa, potom rodiča a pravého dieťaťa.
- Past the PostOrder – návšteva ľavého dieťaťa, potom pravého dieťaťa a potom rodiča.
Príklad štyroch prechodov binárneho vyhľadávacieho stromu:
- Predobjednávka – 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- V poradí – 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- PostOrder – 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- Poradie úrovne – 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Obrázok ukazuje poradie, v ktorom sú navštívené uzly. Číslo 1 je prvý uzol v konkrétnom prechode a číslo 7 je posledný uzol.
Tieto všeobecné prechody môžu byť reprezentované ako jeden algoritmus za predpokladu, že každý uzol je navštívený trikrát. Eulerova prehliadka je prechádzka okolo binárneho stromu, kde každá hrana je považovaná za stenu, ktorú používateľ nemôže prekročiť. V tejto prechádzke bude každý uzol navštívený buď vľavo, alebo pod alebo vpravo. Eulerova cesta, ktorá navštevuje uzly vľavo, spôsobuje obídenie predložky. Keď sú navštívené uzly nižšie, prechádzajú sa v poradí. A keď sú navštívené uzly vpravo - získajtevynechanie krok za krokom.
Navigácia a ladenie
Na uľahčenie navigácie v strome vytvorte funkcie, ktoré najskôr skontrolujú, či ide o ľavé alebo pravé dieťa. Ak chcete zmeniť polohu uzla, musí byť jednoduchý prístup k ukazovateľu v nadradenom uzle. Správna implementácia stromu je veľmi náročná, takže musíte poznať a aplikovať ladiace procesy. Binárny vyhľadávací strom s implementáciou má často ukazovatele, ktoré v skutočnosti neudávajú smer cesty.
Na toto všetko sa používa funkcia, ktorá kontroluje, či je strom správny, a pomáha nájsť veľa chýb. Napríklad skontroluje, či nadradený uzol je podriadený uzol. Pomocou Assert(is_wellformed(root)) je možné predčasne zachytiť mnohé chyby. Pomocou niekoľkých daných bodov prerušenia v rámci tejto funkcie môžete tiež presne určiť, ktorý ukazovateľ je nesprávny.
Funkcia Konsolenausgabe
Táto funkcia vyprázdni celý strom do konzoly, a preto je veľmi užitočná. Poradie, v ktorom sa vykoná cieľ výstupu zo stromu, je:
- Ak to chcete urobiť, musíte najprv určiť, aké informácie budú výstupom cez uzol.
- A tiež potrebujete vedieť, aký široký a vysoký je strom, aby ste zohľadnili, koľko miesta vám zostane.
- Nasledujúce funkcie vypočítavajú tieto informácie pre strom a každý podstrom. Keďže do konzoly môžete písať iba riadok po riadku, budete musieť vytlačiť aj strom riadok po riadku.
- Teraz potrebujeme iný spôsob odstúpenia od zmluvycelý strom, nielen riadok po riadku.
- Pomocou funkcie výpisu môžete čítať strom a výrazne zlepšiť výstupný algoritmus, pokiaľ ide o rýchlosť.
Túto funkciu však bude ťažké použiť na veľkých stromoch.
Kopírovať konštruktor a deštruktor
Keďže strom nie je triviálna dátová štruktúra, je lepšie implementovať konštruktor kopírovania, deštruktor a operátor priradenia. Deštruktor sa dá ľahko implementovať rekurzívne. Pri veľmi veľkých stromoch si poradí s „prepadom haldy“. V tomto prípade je formulovaný iteratívne. Cieľom je odstrániť list predstavujúci najmenšiu hodnotu zo všetkých listov, takže je na ľavej strane stromu. Odrezaním prvých listov vznikajú nové a strom sa zmenšuje, až napokon prestane existovať.
Konštruktor kopírovania možno implementovať aj rekurzívne, ale buďte opatrní, ak dôjde k vyvolaniu výnimky. V opačnom prípade sa strom rýchlo stane mätúcim a náchylným na chyby. Preto je preferovaná iteratívna verzia. Cieľom je prejsť starý strom a nový strom, ako by ste to urobili v deštruktore, klonovať všetky uzly, ktoré sú v starom strome, ale nie tie nové.
Pri tejto metóde je implementácia binárneho vyhľadávacieho stromu vždy v dobrom stave a deštruktor môže byť odstránený aj v neúplnom stave. Ak sa vyskytne výnimka, stačí, aby ste deštruktorovi dali pokyn, aby vymazal rozpracovaný strom. operátor priradeniamožno jednoducho implementovať pomocou funkcie Copy & Swap.
Vytvorenie binárneho vyhľadávacieho stromu
Optimálne binárne vyhľadávacie stromy sú neuveriteľne efektívne, ak sú správne spravované. Niektoré pravidlá pre binárne vyhľadávacie stromy:
- Rodičovský uzol má najviac 2 podriadené uzly.
- Ľavý podradený uzol je vždy menší ako nadradený uzol.
- Platný podriadený uzol je vždy väčší alebo rovný rodičovskému uzlu.
Pole, ktoré sa použije na zostavenie binárneho vyhľadávacieho stromu:
- Pole základných celých čísel so siedmimi hodnotami v nezoradenom poradí.
- Prvá hodnota v poli je 10, takže prvým krokom pri vytváraní stromu je vytvorenie 10 koreňového uzla, ako je znázornené tu.
- S množinou koreňových uzlov budú všetky ostatné hodnoty potomkami tohto uzla. Podľa pravidiel je prvým krokom na pridanie 7 do stromu jeho porovnanie s koreňovým uzlom.
- Ak je hodnota 7 menšia ako 10, stane sa ľavým podriadeným uzlom.
- Ak je hodnota 7 väčšia alebo rovná 10, posunie sa doprava. Keďže je známe, že 7 je menej ako 10, je označený ako ľavý podriadený uzol.
- Rekurzívne vykonajte porovnania pre každý prvok.
- Na základe rovnakého vzoru vykonajte rovnaké porovnanie so 14. hodnotou v poli.
- Porovnanie hodnoty 14 s koreňovým uzlom 10 s vedomím, že 14 je správne dieťa.
- Prechádzka po poli,príďte do 20.
- Začnite porovnaním poľa s 10, podľa toho, čo je väčšie. Presuňte sa teda doprava a porovnajte to so 14, má viac ako 14 rokov a vpravo nemá žiadne deti.
- Teraz je tu hodnota 1. Podľa rovnakého vzoru ako ostatné hodnoty porovnajte 1 až 10, presuňte sa doľava a porovnajte so 7 a nakoniec s 1 ľavým potomkom 7. uzla.
- Ak je hodnota 5, porovnajte ju s 10. Keďže 5 je menej ako 10, prejdite doľava a porovnajte ju so 7.
- Vediac, že 5 je menej ako 7, pokračujte v strome a porovnajte 5 s 1 hodnotou.
- Ak 1 nemá žiadne deti a 5 je väčšie ako 1, potom 5 je platným potomkom 1 uzla.
- Nakoniec vložte do stromu hodnotu 8.
- Keď je 8 menšie ako 10, posuňte ho doľava a porovnajte so 7, 8 je väčšie ako 7, takže ho posuňte doprava a dokončite strom, čím sa 8 stane správnym potomkom 7.
Získanie a vyhodnotenie jednoduchej elegancie optimálnych binárnych vyhľadávacích stromov. Rovnako ako mnohé témy v programovaní, sila binárnych vyhľadávacích stromov pochádza z ich schopnosti rozložiť údaje na malé súvisiace komponenty. Odteraz môžete pracovať s celým súborom údajov organizovaným spôsobom.
Potenciálne problémy s binárnym vyhľadávaním
Binárne vyhľadávacie stromy sú skvelé, no treba mať na pamäti niekoľko upozornení. Zvyčajne sú účinné len vtedy, ak sú vyvážené. Vyvážený strom je strom, v ktoromrozdiel medzi výškami podstromov ktoréhokoľvek uzla v strome je najviac jedna. Pozrime sa na príklad, ktorý by mohol pomôcť objasniť pravidlá. Predstavme si, že pole začína ako zoraditeľné.
Ak sa pokúsite spustiť binárny algoritmus vyhľadávacieho stromu na tomto strome, bude sa správať presne tak, ako keby len iteroval cez pole, kým sa nenájde požadovaná hodnota. Sila binárneho vyhľadávania spočíva v schopnosti rýchlo odfiltrovať nežiaduce hodnoty. Keď strom nie je vyvážený, nebude poskytovať rovnaké výhody ako vyvážený strom.
Pri vytváraní binárneho vyhľadávacieho stromu je veľmi dôležité preskúmať údaje, s ktorými používateľ pracuje. Pred implementáciou binárneho vyhľadávacieho stromu pre celé čísla môžete integrovať rutiny, ako je randomizácia poľa, aby ste to vyvážili.
Príklady výpočtu binárneho vyhľadávania
Musíme určiť, aký druh stromu vznikne, ak sa 25 vloží do nasledujúceho binárneho vyhľadávacieho stromu:
10
/
/
5 15
/ /
/ /
2 12 20
Pri vkladaní x do stromu T, ktorý ešte neobsahuje x, sa kľúč x vždy umiestni do nového listu. V súvislosti s tým bude nový strom vyzerať takto:
10
/
/
5 15
/ /
/ /
2 12 20
25
Aký druh stromu by ste získali, keby ste do nasledujúceho binárneho vyhľadávacieho stromu vložili 7?
10
/
/
5 15
/ /
/ /
2 12 20
Odpoveď:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
Binárny vyhľadávací strom možno použiť na uloženie akéhokoľvek objektu. Výhodou použitia binárneho vyhľadávacieho stromu namiesto prepojeného zoznamu je, že ak je strom primerane vyvážený a pripomína skôr „úplný“strom ako „lineárny“, možno implementovať operácie vkladania, vyhľadávania a všetkých mazacích operácií. O(log N) čas.
