(a,b)-stromy

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.
Uživatelský avatar
lavor
Matfyz(ák|ačka) level III
Příspěvky: 121
Registrován: 1. 2. 2005 20:39
Typ studia: Informatika Bc.
Bydliště: kolej 17.11., A1105
Kontaktovat uživatele:

(a,b)-stromy

Příspěvek od lavor »

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

Vytah zo skript(ps-file).
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.
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:

Kód: Vybrat vše

                                    |3|7|
                              /        |        \
                        (*)|1|3|     |5|6|7|     |8|9|
                           /   \      /  |  \     |  \
                         |1|  |3|   |5| |6| |7|  |8| |9|
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.
Milujeme tých, čo nás odmietajú, odmietame tých, čo nás milujú.
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
Příspěvky: 445
Registrován: 22. 9. 2004 21:07
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: (a,b)-stromy

Příspěvek od twoflower »

lavor píše:Potom ale vrchol oznaceny (*), ma Ró(v) = 2 a |Hv| = 2
Mozna mi to jen po jidle pomaleji chape, ale proc by mel ten vrchol mit |Hv| = 2?
Uživatelský avatar
lavor
Matfyz(ák|ačka) level III
Příspěvky: 121
Registrován: 1. 2. 2005 20:39
Typ studia: Informatika Bc.
Bydliště: kolej 17.11., A1105
Kontaktovat uživatele:

Re: (a,b)-stromy

Příspěvek od 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.
Milujeme tých, čo nás odmietajú, odmietame tých, čo nás milujú.
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
Příspěvky: 445
Registrován: 22. 9. 2004 21:07
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: (a,b)-stromy

Příspěvek od twoflower »

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.
chucky
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 17. 5. 2007 16:20
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: (a,b)-stromy

Příspěvek od chucky »

lavor píše: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.
Tiez velmi nerozumiem, co chces osvetlit.. Z akeho dovodu pouzivas Hv[1..Ró] namiesto Hv[1..Ró-1]?
Uživatelský avatar
lavor
Matfyz(ák|ačka) level III
Příspěvky: 121
Registrován: 1. 2. 2005 20:39
Typ studia: Informatika Bc.
Bydliště: kolej 17.11., A1105
Kontaktovat uživatele:

Re: (a,b)-stromy

Příspěvek od lavor »

sory, cela moja reprezentacia je zla, nepochopil som to Hv, dik za osvetlenie
Milujeme tých, čo nás odmietajú, odmietame tých, čo nás milujú.
Odpovědět

Zpět na „TIN066 Datové struktury I“