Loading web-font TeX/Main/Regular

Kolik listů má minimálně 5-ární B-strom s hloubkou 2.

BI
BI-EFA

asked Nov 6 '14

Ondřej Máca
192 ●7 ●11 ●20

updated Nov 6 '14

shejby

271 ●5 ●9 ●20 http://shejby.cz/

Na FW píšou že 6, ale já bych řekl, že stačí jeden, protože každý uzel může mít 0-5 potomků. Nebo se pletu?

add a comment

1 Answer

Sort by » oldest newest most voted

answered Nov 7 '14

Viktor Chlumský
765 ●14 ●24

updated Nov 7 '14

Pro obecný vyhledávací strom ano, ale B-strom má navíc pravidla:

všechny listy mají stejnou hloubku
pokud kořen není listem, má minimálně 2 syny
vnitřní uzly (kromě kořenu) musí mít minimálně $\lceil m/2 \rceil = 3$ syny

(source)

Takže aby to bylo splněné, musí mít 6 listů, a vypadá nějak takhle:

image description

link

Comments

aha díky, toho B jsem si nějak nevšiml a nejspíš to bylo proto, že jsme to ještě nebrali a tak jsem si myslel, že se jedná o obecný strom. Ale bylo mi divný, proč je ve druhé písemce látka, která by měla být v první :D

Ondřej Máca (Nov 7 '14)

add a comment

Question tools

1 follower

Stats

Asked: Nov 6 '14

Seen: 420 times

Last updated: Nov 07 '14

Kolik listů má minimálně 5-ární B-strom s hloubkou 2.

1 Answer

Comments

Your answer

Question tools

Stats

Related questions