B-ağaclar

Əgər ağac danışa bilsəydi...

B-ağacı, ikincil yaddaşda (məsələn, sərt diskdə) məlumatların saxlanılması üçün istifadə olunan bir quruluşdur. B-ağacının bir neçə əsas xüsusiyyəti var:

1. Yarpaq olmayan hər bir zirvənin uşaq sayı $t$-dən az və $2t$-dən çox ola bilməz, burada $t$ — budaqlanma dərəcəsi adlanan bir parametrdir.

2. Hər bir yarpaqda t-1 ilə 2t-1 arasında açar saxlanılır.

3. Bütün yarpaqlardan kökə qədər olan məsafə eynidir.

Qeyd etmək lazımdır ki, kök yarpaq ola bilər.

İki B-ağacı fərqli hesab olunur, əgər onlar işarələnmiş zirvələrə malik qraf kimi fərqlidirlərsə və ya eyni işarəyə malik zirvə fərqli sayda açar ehtiva edirsə. Məsələn, $2$ budaqlanma dərəcəsi və dörd açarla cəmi $8$ fərqli B-ağacı mövcuddur:

Yarpaqlarda $n$ açarla və budaqlanma dərəcəsi $t$ olan fərqli B-ağaclarının sayını hesablayın.