´ rn´ı vyhleda ´ va ´ n´ı a bst bina Karel Hor´ak, Petr Ryˇsav´y 23. bˇrezna 2016 ˇ Katedra poˇ c´ıtaˇ c˚ u, FEL, CVUT
Pˇr´ıklad 1
Naimplementujte bin´arn´ı vyhled´av´an´ı. Upravte metodu BinarySearch::binarySearch.
1
Pˇr´ıklad 2
Mysl´ım si ˇc´ıslo mezi 1 a 10000. Navrhnˇete algoritmus, kter´y uhodne ˇc´ıslo, kter´e si mysl´ım. M˚ uˇzete pokl´adat pouze ot´azky, na kter´e je odpovˇed’ ano/ne. Protoˇze jsem l´ın´y, snaˇzte se co nejmenˇs´ı poˇcet ot´azek. Kolik ot´azek budete muset maxim´alnˇe poloˇzit, neˇz odhal´ıte ˇc´ıslo, kter´e si mysl´ım.
2
ˇ sen´ı 2 Reˇ
Vhodn´ym ˇreˇsen´ım je pouˇz´ıt bin´arn´ı vyhled´av´an´ı. Vˇzdy m´ame k dispozici nˇejak´y interval, ze kter´eho je myˇslen´e ˇc´ıslo. Interval rozdˇel´ıme na dvˇe poloviny a zept´ame se ot´azku, zda je myˇslen´e ˇc´ıslo vˇetˇs´ı neˇz prostˇredn´ı bod intervalu. Podle odpovˇedi interval nahrad´ıme jeho levou nebo pravou polovinou. K ˇreˇsen´ı je tˇreba dlog2 10000 + 1e ot´azek, coˇz je 15 ot´azek.
3
Pˇr´ıklad 3
ˇ ısla ze zadan´e posloupnosti postupnˇe vkl´adejte do pr´azdn´eho bin´arn´ıho C´ vyhled´avac´ıho stromu (BVS). Jak bude vypadat takto vytvoˇren´y BVS? Pot´e postupnˇe odstraˇ nte prvn´ı tˇri prvky. Jak bude vypadat v´ysledn´y BVS? 1. 14, 24, 5, 13, 1, 3, 22, 10, 19, 11 2. 10, 16, 5, 17, 4, 15, 3, 1, 23, 13, 2, 11
4
Pˇr´ıklad 4
ˇ ıslo n je lich´e. Nejprve vloˇz´ıme do BVS Mˇejme kl´ıˇce 1, 2, 3, . . . , n. C´ vˇsechny sud´e kl´ıˇce v rostouc´ım poˇrad´ı a pak vˇsechny lich´e kl´ıˇce tak´e v rostouc´ım poˇrad´ı. Jak´a bude hloubka v´ysledn´eho stromu? Zmˇenil by se nˇejak tvar stromu, kdybychom lich´a ˇc´ısla vkl´adali v n´ahodn´em poˇrad´ı?
5
ˇ sen´ı 4 Reˇ
1 z´ıme vˇsechny sud´e Hloubka v´ysledn´eho stromu bude n−1 2 . Pokud vloˇ n−1 uzly, bude hloubka 2 − 1. Po pˇrid´an´ı lich´ych uzl˚ u se hloubka zv´yˇs´ı o jedna, protoˇze n bude vˇzdy napravo od n − 1.
Pokud bychom vkl´adali lich´a ˇc´ısla v n´ahodn´em poˇrad´ı, strom se nezmˇen´ı. Jeho tvar je jiˇz urˇcen vloˇzen´ymi sud´ymi ˇc´ısly.
1 Pˇ redpokl´ ad´ ame,
ˇze hloubka stromu o jednom uzlu je 0. 6
Pˇr´ıklad 5
V jak´em poˇrad´ı vyp´ıˇseme prvky bin´arn´ıho vyhled´avac´ıho stromu, pokud ho projdeme inorder?
7
ˇ sen´ı 5 Reˇ
Prvky budou seˇrazen´e podle velikosti.
8
Pˇr´ıklad 6
Pˇredpokl´adejme, ˇze bin´arn´ı vyhled´avac´ı strom obsahuje pˇrirozen´a ˇc´ısla mezi 1 a 1000. Kter´e z n´asleduj´ıc´ıch sekvenc´ı navˇst´ıven´ych uzl˚ u nemohou nastat, pokud hled´ame kl´ıˇc 363? 1. 2, 252, 401, 398, 330, 363 2. 399, 387, 219, 266, 382, 381, 278, 363 3. 3, 923, 220, 911, 244, 898, 258, 362, 363 4. 4, 924, 278, 347, 621, 299, 392, 358, 363 5. 5, 925, 202, 910, 245, 363 [http://www.cs.princeton.edu/courses/archive/fall12/ cos126/precepts/BSTex.pdf] 9
ˇ sen´ı 6 Reˇ
Moˇznost 4 nem˚ uˇze nastat. Hodnota 299 nem˚ uˇze b´yt po 621, protoˇze to by pak byla v lev´em podstromˇe uzlu s kl´ıˇcem 347.
10
Pˇr´ıklad 7
Jak´a je asymptotick´a sloˇzitost operac´ı insert, find a delete pro 1. vyv´aˇzen´y bin´arn´ı vyhled´avac´ı strom; 2. obecn´y bin´arn´ı vyhled´avac´ı strom.
11
ˇ sen´ı 7 Reˇ
V pˇr´ıpadˇe vyv´aˇzen´eho bin´arn´ıho vyhled´avac´ıho stromu vˇsechny operace trvaj´ı Θ(log n). V pˇr´ıpadˇe obecn´eho bin´arn´ıho vyhled´avac´ıho stromu mohou trvat aˇz O(n).
12
Pˇr´ıklad 8
V jak´em poˇrad´ı m´ame vkl´adat 2n − 1 prvk˚ u do bin´arn´ıho vyhled´avac´ıho stromu tak, aby byl vyv´aˇzen´y? Formulujte nutnou a postaˇcuj´ıc´ı podm´ınku, aby byl v´ysledn´y vyhled´avac´ı strom vyv´aˇzen´y.
13
ˇ sen´ı 8 Reˇ
Existuje pr´avˇe jeden vyv´aˇzen´y strom o dan´ych 2n − 1 prvc´ıch. Pokud ho chceme vybudovat, je nutnou a postaˇcuj´ıc´ı podm´ınkou, abychom z´ıskali stejn´y strom, ˇze vkl´ad´ame vˇzdy uzel dˇr´ıve neˇz jeho potomky. Takto doc´ıl´ıme toho, ˇze strom budujeme odshora. Pˇri vkl´ad´an´ı je jen jedno moˇzn´e m´ısto, kam lze nov´y uzel vloˇzit. Pokud vkl´ad´ame dalˇs´ı uzel a jeho rodiˇc a vˇsechny uzly na cestˇe ke koˇreni z vyv´aˇzen´eho stromu jsou jiˇz vloˇzeny do stromu, pak je uzel vloˇzen na stejn´e m´ısto jako ve vyv´aˇzen´em stromˇe. Protoˇze uzel vkl´ad´ame vˇzdy pˇred jeho potomky, plat´ı, ˇze z´ısk´ame vyv´aˇzen´y strom.
14
Pˇr´ıklad 9
Mˇejme bin´arn´ı vyhled´avac´ı strom. Jak´a je asymptotick´a sloˇzitost operace, kter´a spoˇcte poˇcet kl´ıˇc˚ u, jejichˇz hodnota je menˇs´ı neˇz x, pokud do uzl˚ u nepˇrid´av´ame ˇz´adn´e pomocn´e informace? Navrhnˇete efektivnˇejˇs´ı algoritmus, pokud si m˚ uˇzete uloˇzit pomocn´e informace.
15
ˇ sen´ı 9 Reˇ
Pokud nepˇrid´av´ame ˇz´adn´e dalˇs´ı informace do stromu, je nutn´e BST proch´azet v poˇrad´ı inorder, dokud nenaraz´ıme na kl´ıˇc, kter´y je alespoˇ n x. Poˇcet navˇst´ıven´ych uzl˚ u je pak poˇzadovan´e ˇc´ıslo. Sloˇzitost operace je tedy O(n). Efektivnˇejˇs´ım by mohlo b´yt pamatovat si velikost kaˇzd´eho podstromu. Pak by n´am staˇcilo vyhledat prvek s hodnotou x a pˇriˇc´ıst velikosti vˇsech lev´ych podstrom˚ u vrchol˚ u cesty, kter´e jsme nenavˇst´ıvili plus poˇcet navˇst´ıven´ych uzl˚ u, kter´e mˇely kl´ıˇce menˇs´ı. Asymptotick´a sloˇzitost je O(n), ale v pˇr´ıpadˇe vyv´aˇzen´eho stromu poklesne na Θ(log2 n).
16
Pˇr´ıklad 10
Naimplementujte vyhled´an´ı minima v bin´arn´ım vyhled´avac´ım stromu a operaci delete.
17
Programovac´ı u´lohy k procviˇcen´ı
https://open.kattis.com/problems/insert
18
