Братское дерево

Материал из WEGA
Brother tree.png

Братское дерево (Brother tree) — бинарное дерево, у которого все висячие вершины находятся на одном и том же уровне и каждая вершина [math]\displaystyle{ x }[/math] с одним потомком имеет брата [math]\displaystyle{ \beta (x) }[/math] с двумя потомками. Ключи хранятся только в висячих вершинах, а во внутренних — вспомогательная информация. Другое название - [math]\displaystyle{ HB }[/math]-дерево.

Литература

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