Ask Your Question
1

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

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

Ondřej Máca gravatar image

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

shejby gravatar image

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
4

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

Viktor Chlumský gravatar image

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 more

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

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

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

Seen: 420 times

Last updated: Nov 07 '14