Diskuse:B-strom
Přidat témaNás učili B-stromy jinak. Tvrdili, že řád stromu n je minimální počet prvků v uzlu. Maximální počet prvků v uzlu je pak 2n. Takhle funguje moje animace o b stromech
Na en: je definice ještě jinak: tam mají řád stromu jako maximální počet odkazů. Což z našich evidentně ekvivalentních definic dělá nepřehledný guláš. Ví někdo jak je to správně? --slady 21:21, 12. 6. 2006 (UTC)
- opraveno podle skript z MFF (teď je to stejné jako na EN wikipedii, slidy třeba zde: http://kocour.ms.mff.cuni.cz/~pokorny/vyuka/pokorny/ (část pátá - B stromy) ) - u stromu stupně n má každý uzel kromě kořene alespoň upper_bound(n/2) a nejvýše n potomků (a tedy (upper_bound(n/2)-1) - (n-1) položek) -- Tento nepodepsaný komentář přidal(a) uživatel(ka) 78.128.196.95 (diskuse)
Nepravdiva formulace vety z uvodu. 'B-strom je díky této vlastnosti vyvážený' - vyvazeny je kvuli specificke implementaci operaci; podminka na pocet potomku uzlu nezarucuje, ze strom nezdegeneruje.
Zpochybněno. V zahraničních zdrojích se mluví u řádu T, jako o minimálním počtu potomků, počet prvků je potom T-1 až 2T-1 (někde jsem se dokonce dočetl, že listy mohou obsahovat prvků více). Mimo jiné z toho vyplývá, že maximální kapacita vnitřního listu je vždy lichá (to je důležité pro algoritmus mazání). A zde uvedený algoritmus mazání není správný, správně se používá jednoprůchodový. Viz sekce 18 T. Cormen et al.: Introduction to Algorithms Zde uvedené špatné informace mě stály hodně nervů :) Až budu mít čas, tak to předělám (po zkouškovém). --89.24.184.26 16. 1. 2012, 09:44 (UTC)
- Tak jak je řečeno v anglické verzi, existuje několik variant, co znamená řád B-stromu. Poslední definice je od Knutha z roku 1998 a odpovídá tomu, že řád B-stromu je maximální počet potomků. (VK)
- jednopruchodovy alg. vkladani i mazani lze pouzit na (T,2T) stromy, napr. 2-4, ale ne na (T-1,2T-1) stromy, tj. 2-3 stromy. Jednopruchodovost me teda stojí pamet, vrcholy jsou prumerne mene naplneny. Jj14 (diskuse) 22. 7. 2013, 02:55 (UTC)
Špatná formulace v úvodu ve větě: "B-strom je speciální případ (a,b)-stromu, který poskytuje větší volnost ve volbě minimálního a maximálního počtu potomků." - svádí to k nejasnostem ohledně toho, který strom má větší volnost, což je (a,b)-strom
