Fórum studentů MFF UK

sory, cela moja reprezentacia je zla, nepochopil som to Hv, dik za osvetlenie

[quote="lavor"]z mojho prikladu: Hv(1) = 1 a Hv(2) = 3 teda Hv je definovane v mojom priklade pre prvky 1..Ró a nie 1.. Ró-1 ako je to v definicii Hv v skriptach.

Mozno to chapem uplne zle, teda ak mate nejake ine chapanie celeho (a,b)-stromu skuste mi to prosim osvetlit.[/quote]

Tiez velmi nerozumiem, co chces osvetlit.. Z akeho dovodu pouzivas Hv[1..Ró] namiesto Hv[1..Ró-1]?

Aha, ale pole H(v) je definovane pro syny [1..Ro(v) - 1], pro nejpravejsiho syna se ta hodnota nedefinuje. Myslim ze ve skriptech je to popsano pekne, zvlast kdyz si clovek uvedomi, ze z te definice plyne, ze maximalni ulozeny prvek ve strome neni v zadnem poli H(v) nejakeho vrcholu v a taky pomuze, kdyz si odtrasujes proceduru Vyhledej(x) a pak se podivas, pri jake operaci a k cemu se pouziva vystupni hodnota w.

z mojho prikladu: Hv(1) = 1 a Hv(2) = 3 teda Hv je definovane v mojom priklade pre prvky 1..Ró a nie 1.. Ró-1 ako je to v definicii Hv v skriptach.

Mozno to chapem uplne zle, teda ak mate nejake ine chapanie celeho (a,b)-stromu skuste mi to prosim osvetlit.

[quote="lavor"]Potom ale vrchol oznaceny (*), ma Ró(v) = 2 a |Hv| = 2[/quote]

Mozna mi to jen po jidle pomaleji chape, ale proc by mel ten vrchol mit |Hv| = 2?

                                    |3|7|
                              /        |        \
                        (*)|1|3|     |5|6|7|     |8|9|
                           /   \      /  |  \     |  \
                         |1|  |3|   |5| |6| |7|  |8| |9|

Nazdar, potreboval by som pomoct s deklaraciou uzlov (a,b)-stromu, podla mna si (ciastocne) odporuje.

Vytah zo skript(ps-file).
[quote]
Deklarace vnitrnıch vrcholu (a, b)-stromu (T, t):
Ró(v) – pocet synu vrcholu v,
Sv(1..Ró(v)) – pole ukazatelu na syny vrcholu v, kde Sv(i) je i-ty syn v pro i = 1, . . . , Ró(v),
Hv(1..Ró(v) − 1) – pole prvku z U takove, ze Hv(i) je nejvetsı prvek z S reprezentovany v
podstromu i-teho syna vrcholu v.

Deklarace listu:
listu v je prirazen prvek key(v) ∈ S.
[/quote]

Ja si to teda predstavujem takto:
V kazdej hladine nech plati deklaracia vnutornych vrcholov okrem poslednej, kde kazdy jeden vrchol(list) ma prave jednu hodnotu.
Priklad:
[code]
|3|7|
/ | \
(*)|1|3| |5|6|7| |8|9|
/ \ / | \ | \
|1| |3| |5| |6| |7| |8| |9|
[/code]

Potom ale vrchol oznaceny (*), ma Ró(v) = 2 a |Hv| = 2 (podla definicie by mal byt |Hv| = Ró(v) - 1, teda 1).
Jedno riesenie vidim v tom ze kazda predposledna hladina ma syna Nil (najpravejsi syn).

Vysvetlujete si to podobne, alebo na to idem uplne zle? Dik za kazdy postreh.

EDIT: mal som tam chybu v tom priklade v koreni mala byt 3 namiesto 4. Opravene.