Matfyz Wiki
Diff for ''
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| {| style="width: 20em; float: right; font-size: 95%; margin: 0 0 1em 1em; border: 1px solid #aaa; border-collapse: collapse; clear: right;" |- | style="padding: 0.5em; background: #cde; font-size: larger; border: 1px solid black;" | '''[[:Category:Předměty|{{{1}}}]]''' |- | {| style="margin-left: 1em;" |- style="vertical-align: top;" |Kód předmětu: |style="padding-left: 1em;" | [http://is.cuni.cz/studium/predmety/index.php?do=predmet&kod=N{{{3}}} N{{{3}}}] |- style="vertical-align: top;" |Přednáší: |style="padding-left: 1em;" | '''[[{{{2}}}]]''' |} |} |
# Hloubka vs. Vyska vs. Hladina |
| Line 16: | Line 3: |
| <{ForumPost(poster="_angwin", timestamp=2009-02-04 23:41:55)}> 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... <{/ForumPost}> |
|
| Line 17: | Line 9: |
| <{ForumPost(poster="Myshaak", timestamp=2009-02-05 00:59:24)}> | |
| Line 18: | Line 11: |
| > _angwin wrote: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... |
|
| Line 19: | Line 15: |
| 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. <{/ForumPost}> |
|
| Line 20: | Line 18: |
| [[Category:Předměty]] | <{ForumPost(poster="Schiroo", timestamp=2009-02-09 14:02:16)}> Definice hloubky a hladiny je u (a,b)-stromů: > Když *v* má * \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é. <{/ForumPost}> |