BB-Дерево

Материал из WikiGrapp
Перейти к:навигация, поиск
BB-Tree.png

BB-Дерево (BB-Tree) — дерево T_{n} \, = \, (T_{l}, r, T_{r}) с корнем r называется BB-деревом с балансом \alpha, 0 \leq \alpha \leq 1/2, если:

а) для корневого баланса \rho(T_{n}) выполняется условие \alpha \leq \rho(T_{n}) \leq 1-\alpha;

б) T_{l} и T_{r}BB-деревья с балансом \alpha.


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

Литература

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