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

Материал из WEGA
Перейти к навигации Перейти к поиску

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

Brother tree.jpg

Другое название - [math]\displaystyle{ HB }[/math]-дерево.

Литература

[Евстигнеев/85],

[Евстигнеев-Касьянов/94]