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

BI
BI-EFA

asked 2014-11-06 21:24:02 +0100

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

updated 2014-11-06 21:38:32 +0100

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?

edit retag flag offensive close delete

1 Answer

Sort by » oldest newest most voted

answered 2014-11-07 14:01:45 +0100

Viktor Chlumský
765 ●14 ●24

updated 2014-11-07 15:35:34 +0100

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

edit flag offensive delete publish 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 ( 2014-11-07 14:31:26 +0100 )edit

Question tools

1 follower

Stats

Asked: 2014-11-06 21:24:02 +0100

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