BB-Дерево

$BB$-Дерево ($BB$-Tree) — дерево $T_n=(T_l,r,T_r)$ с корнем $r$ называется $BB$-деревом с балансом $\alpha$, $0\le \alpha \le 1/2$, если:

а) для корневого баланса $\rho (T_n)$ выполняется условие $\alpha \le \rho (T_n)\le 1-\alpha$;

б) $T_l$ и $T_r$ — $BB$-деревья с балансом $\alpha$.

Другое название — Балансированное по весу дерево.

Литература

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

• Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980.