Binarne stromy
Binarne stromy
Ahoj, mam otazku ohladom maximalneho resp minimalneho poctu uzlov v binarnych stromoch. Podla definicie to je 2^(h+1) - 1 resp pre min h + 1. Uplne mi to nevychadza, a teda niesom si isty, co mam za uzol pocitat. Ak by som mal koren a z neho dva listy, cize hlbka 1, to podla vzorca pre minimalny pocet ciny 1+1 = 2, pre samotny koren by to bolo teda 0+1. Predpokladal som, ze uzol je v podstate ten spoj/ciara, ale to mi potom nesedi. Podobne to mam potom aj s maximalnym poctom. Viete mi to niekto vysvetlit? Dakujem
Re: Binarne stromy
Oba vzorce mas dobre. Uzly su tie veci, ktore su na konci ciar. Cize koren je uzol, jeho potomkovia (listy) su uzly etc. Tie ciary sa nazyvaju hrany.
Re: Binarne stromy
Dakujem za odpoved. Len jedna vec mi potom nesedi. Ak mas hlbku 1, tak mas koren a 2 listy, teda dokopy 3 uzly. Minimalny pocet pre uplny strom teda vychadza 2. Nie je to blbost?
Inak este mam jednu otazku.
Predpokladajte, ze binarny vyhladavaci strom bol vytvoreny postupnym vlozenim cisel 3, 1, 4 a 2. Ako si to nakreslit, neviem ako sa tam budu vkladat. Myslim si, ze 3 bude koren, 1 a 4 listy z korena a 2 list z 1cky. Bude to takto spravne? Alebo ma to nejaku postupnost?
Dik.
Inak este mam jednu otazku.
Predpokladajte, ze binarny vyhladavaci strom bol vytvoreny postupnym vlozenim cisel 3, 1, 4 a 2. Ako si to nakreslit, neviem ako sa tam budu vkladat. Myslim si, ze 3 bude koren, 1 a 4 listy z korena a 2 list z 1cky. Bude to takto spravne? Alebo ma to nejaku postupnost?
Dik.
Re: Binarne stromy
To co si opisal, koren + 2 listy je naopak maximalny storm hlbky 1. Je maximalny, lebo viac uzlov do toho nedokazes nijako napchat. Dalsie uzly by uz museli ist do vacsej hlbky.
Minimalny strom hlbky dva je koren + jeden jeho list. Miminalny strom hlbky 3 je koren + jeho potomok + potomok tohto potomka. Minimalny strom hlbky X je teda len taky hadik, v ktorom je X+1 uzlov za sebou. Teda v tom vzniknutom strome ti oproti tomu maximalnemu pripadu (ked mas kazdy uzol prave dvoch potomkov) chybaju nejake uzly.
To vkladanie zalezi, neviem ci je nejaky jeden exaktny sposob ako sa vytvaraju stromy z postupnosti. Ten sposob, ktory si to opisal, znie tak ze by mohol byt aj spravny.
Minimalny strom hlbky dva je koren + jeden jeho list. Miminalny strom hlbky 3 je koren + jeho potomok + potomok tohto potomka. Minimalny strom hlbky X je teda len taky hadik, v ktorom je X+1 uzlov za sebou. Teda v tom vzniknutom strome ti oproti tomu maximalnemu pripadu (ked mas kazdy uzol prave dvoch potomkov) chybaju nejake uzly.
To vkladanie zalezi, neviem ci je nejaky jeden exaktny sposob ako sa vytvaraju stromy z postupnosti. Ten sposob, ktory si to opisal, znie tak ze by mohol byt aj spravny.
Re: Binarne stromy
Super, vdaka uz mi to sedi.
K tomu vkladaniu hodnot, mi to pri tejto ulohe vyslo aj s moznostami spravne. No mam este jednu podobnu ulohu, kde takisto postupne vkladam cisla ale tentokrat 2,3,4,1. Myslel som si, ze to bude znovu 2 koren, 3 a 4 listy, a 1cka list z 3ky. No spravna odpoved je, ze uzol obsahujuci hodnotu 4 je pravym potomkom uzlu obsahujuceho 3. Tu to zial nesedi. Vies mi este poradit s tymto, preco je to tak? Dakujem este raz
K tomu vkladaniu hodnot, mi to pri tejto ulohe vyslo aj s moznostami spravne. No mam este jednu podobnu ulohu, kde takisto postupne vkladam cisla ale tentokrat 2,3,4,1. Myslel som si, ze to bude znovu 2 koren, 3 a 4 listy, a 1cka list z 3ky. No spravna odpoved je, ze uzol obsahujuci hodnotu 4 je pravym potomkom uzlu obsahujuceho 3. Tu to zial nesedi. Vies mi este poradit s tymto, preco je to tak? Dakujem este raz
Re: Binarne stromy
Netusim, podla mna v tej ulohe musis mat viac informacii o tom, ako sa taketo stromy vytvaraju.
Re: Binarne stromy
Zial nie, tu je cela uloha http://tinypic.com/r/2nsaz5d/9 Mozno sa najde niekto, kto bude vediet. Kazdopadne aj tak velke dik 
-
jorg22
Medium Professional
- Príspevky: 1087
- Registrovaný: 12 aug 2006, 20:39
- Kontaktovať používateľa:
Re: Binarne stromy
Kedze sa nebavime len o binarnom strome ale konkretne o binarnom vyhladavacom strome, tak algoritmus vkladania hodnot je presne definovany. Takto ma vyzerat pozadovany strom: bin_tree.png
Pri vkladani hodnot staci splnit tieto dve pravidla:
Na tejto stranke si mozes overit svoje riesenia:
https://www.cs.usfca.edu/~galles/visualization/BST.html
Pri vkladani hodnot staci splnit tieto dve pravidla:
Viac info.: https://sk.wikipedia.org/wiki/Bin%C3%A1 ... 3%AD_stromHodnoty v uzloch sú usporiadané tak, že pre každý uzol stromu u platí:
1. hodnota uložená v u je väčšia alebo rovná ako hodnota uložená v ľavom podstrome u
2. hodnota uložená v u je menšia alebo rovná ako hodnota uložená v pravom podstrome u
Na tejto stranke si mozes overit svoje riesenia:
https://www.cs.usfca.edu/~galles/visualization/BST.html
- Prílohy
-
- bin_tree.png (3.02 KiB) 1300 zobrazení
Re: Binarne stromy
Super, dakujem vam velmi pekne. Este ak by bol niekto dobry a povedal mi, ci je toto spravne. Myli ma, ze je mozne pri tejto ulohe oznacit viacero spravnych moznosti, no myslim, si, ze je spravna len jedna. http://tinypic.com/r/yhtn5/9 Myslim si, ze je spravna odpoved len A, cize najprv koren, potom lavy podstrom a nakoniec pravy. Je to spravne? Dakujem.
-
harrison314
Hardcore addict
- Príspevky: 8216
- Registrovaný: 27 máj 2009, 20:42
- Bydlisko: Bratislava
- Kontaktovať používateľa:
Re: Binarne stromy
Ked to das do ggogla, hned prvy link je riesnie : https://en.wikipedia.org/wiki/Tree_trav ... re-order_2