Diskuse:(a,b)-strom

Neviem s kade to mate a-b strom, nikde v cudzojazycnej literature som o takom strome nenasiel zmienku. a-b strom je B-strom

Pravda, článek by se měl zapracovat do B-stromu. --Adam Zivner 19:17, 10. 6. 2007 (UTC)

Nemyslím si, jde o to odkud člověk čerpá; na anglické wiki je B-strom definován jako na české (a,b)-strom, ale zároveň v anglické literatuře uvedené v odkazech na wiki je B-strom definován tak jako je definován zde na české.

Ono jde o to, že všechny reálně používané (a,b) stromy jsou B-stromy. Teoreticky může existovat obecnější třída (a,b) stromů, která zahrnuje všechny B-stromy. Je to ale zbytečné, protože (a,b) strom, který není B-stromem, je v praxi na nic. Proto se (a,b) strom považuje za synonymum pro B-strom (a naopak). Nemyslím si, že je nutné mít články o obou pojmech, stačí přidat do B-stromu zmínku ... --Adam Zivner 16:50, 24. 6. 2007 (UTC)

Koukám že ten (a,b) strom je i v anglické wiki.. http://en.wikipedia.org/wiki/(a%2Cb)-tree Rhadesan 07:05, 25. 6. 2007 (UTC)

Logaritmický čas?

Pro takto obecně definovaný strom nelze zaručit logaritmický čas operací (např. pro strom 1-10). Na enwiki mají zas definici o trochu jinou, vůbec ji ale nechápu. Podle mě je toto heslo zbytečné, stačí zmínka o něm v článku B-strom. --Adam Zivner 14:06, 26. 6. 2007 (UTC)

Co s článkem?

Naše verze článku si odporuje (odstavec výše), na en.wiki je nesmyslná definice a pojem je jen těžko k dohledání. Podle mě je vhodné článek smazat a jako odstavec začlenit do článku B-strom, ať už je totiž definovaný jakkoliv, je nevýznamný. --Adam Zivner 11:11, 29. 6. 2007 (UTC)

Keci

Ty stromy musi splnovat integritni omezeni mensiPulka(b+1) >= a. To znamena pro liche b

b+1 >= 2a

a pro sude b

b >= 2a

ten logaritmicky cas to splnuje a logaritmus je o zakladu a. Davat za a=1 nema moc smysl log1 taky neni definovany. jedna na kolikatou je pet?

Jo a kdyz dozeneme to integritni omezeni az na dren tak dostaneme b-strom mensiPulka(b+1) = a

Je to proto, ze kdyz pridavame polozku do listu kde je b polozek bude b+1 polozek a ty musime rozdelit na dve pulky a zajistit aby ta mensi pulka byla vetsi nez a.

Kdyz odebirame zaznam a v listu bylo a polozek je treba jej umet spojit s listem vedle a ten muze mit jenom a polozek. Proto 2a - 1 <=b.

Jo a taky se to lisi jestli jsou data jenom v listech nebo i v nelistovych polozkach. (a, b) strom je ma vetsinou jenom v listech. Kdyby i v nelistovych polozkach integritni omezeni by vypadaly trochu jinak(odecitani 1 od b).

Polozky v listech: integrita na insert

V nejhorsim pridam tam kde uz je b polozek ... bude b+1 ... jednu ale dam na rozdelovani mensipulka(b) >=a integrita na delete

V nejhorsim pripade tam bude a polozek a smazu jednu a potrebuju to spojit s a. Jedna mi ale pribyde z toho nelistu nahore takze 2a >= b

A tedka hlavni rozdil je ze v ab stromech je v kazdem listu a-b polozek, kde polozka == odkaz nebo polozka listoveho zaznamu.

Kdybysme tedy chteli v ab stromech dat zaznamy do vrcholu vevnitr tak je jich tam a-1 az b-1.

Takze a b stromy jsou ty kde na listovych vrcholech jsou zaznamy a na nelistovych odkazy nikoli zaznamy.

B stromy jsou ty kde jsou zaznamy i uvnitr struktury, ale za cenu toho, ze v nelistech jich smi byt jiny pocet nez v listech. A chceteli jsou to a b stromy co plni sve integritni omezeni fak dobre.