Hloubka vs. Vyska vs. Hladina

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ů.
_angwin

Hloubka vs. Vyska vs. Hladina

Příspěvek od _angwin »

Jak se tak postupne prokousavam Koubkovyma skriptama, tak jsem narazil na tyto tri terminy. Vzdy se jedna o vzdalenosti vrcholu od korene, resp. od listu.

Zatim jsem nezavrhnul hypotezu, ze vyska se cisluje od listu a hloubka/hladina se cisluje od korene. Muzete to nekdo prosim potvrdit nebo ty veci v textu pouziva zcela nahodne? Asi jsem prehlidel nejakou definici...
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 162
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

Re: Hloubka vs. Vyska vs. Hladina

Příspěvek od Myshaak »

_angwin píše:Jak se tak postupne prokousavam Koubkovyma skriptama, tak jsem narazil na tyto tri terminy. Vzdy se jedna o vzdalenosti vrcholu od korene, resp. od listu.

Zatim jsem nezavrhnul hypotezu, ze vyska se cisluje od listu a hloubka/hladina se cisluje od korene. Muzete to nekdo prosim potvrdit nebo ty veci v textu pouziva zcela nahodne? Asi jsem prehlidel nejakou definici...
Zdar, je to tak, jak rikas. Teda nerucim za to, ze to je konzistentne v celych skriptech, ale treba v popisu A-sortu je zminena "vyska" a znamena to vzdalenost od listu, zatimco "hloubka" se pocita od korene.
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Schiroo
Matfyz(ák|ačka) level I
Příspěvky: 28
Registrován: 1. 2. 2006 13:54
Typ studia: Informatika Bc.
Bydliště: Praha

Re: Hloubka vs. Vyska vs. Hladina

Příspěvek od Schiroo »

Definice hloubky a hladiny je u (a,b)-stromů:
Když v \ro(v) synů, pak jsou očíslovány od 1 do \ro(v). Řekneme, že vrchol v je v hloubce h, když cesta z kořene t do v má délku h. Množina všech vrcholů v hloubce h se nazývá h-tá hladina.
Už jsem se dočetl i k výšce (Hladinově propojené (a,b)-stromy s prstem, amortizovaná složitost operací ) :)
Připomínáme, že výška vrcholu v kořenovém stromě je maximální délka cesty z tohoto vrcholu do některého listu v jeho podstromu, V (a,b)-stromech nezáleží na tom, který list budeme uvažovat, všechny cesty mají stejnou délku.
Tedy Mishaak měl pravdu, nová informace je ta, že je to (snad) ve skriptech konzistentní vzhledem k tomu, že je to tam explicitně definované.
May the source be with you!
Odpovědět

Zpět na „TIN066 Datové struktury I“