(а, б) -дерево

В информатике , (а, б) дерево является своего рода сбалансированного дерева поиска .

У (a, b) -дерева все листья находятся на одной глубине, и все внутренние узлы, кроме корня, имеют от a до b дочерних элементов , где a и b - целые числа, такие что 2 ≤ a ≤ ( b +1) / 2 . У корня, если это не лист, есть от 2 до b потомков.

Определение [ править ]

Пусть a , b - натуральные числа такие, что 2 ≤ a ≤ ( b +1) / 2 . Тогда корневое дерево T является (a, b) -деревом, когда:

• Каждый внутренний узел, кроме корня, имеет не менее a и не более b детей.
• У корня не более b детей.
• Все пути от корня до листьев одинаковой длины.

Представление внутреннего узла [ править ]

Каждый внутренний узел v (a, b) -дерева T имеет следующее представление:

• Позвольте быть количеством дочерних узлов узла v .${\displaystyle \rho _{v}}$
• Позвольте быть указателями на дочерние узлы.${\displaystyle S_{v}[1\dots \rho _{v}]}$
• Позвольте быть массивом ключей, равным наибольшему ключу в поддереве, на которое указывает .${\displaystyle H_{v}[1\dots \rho _{v}-1]}$${\displaystyle H_{v}[i]}$${\displaystyle S_{v}[i]}$

См. Также [ править ]

• B-дерево
• 2-3 дерева
• 2-4 дерево

Ссылки [ править ]

•  Эта статья включает материалы, являющиеся общественным достоянием  из  документа NIST :  Black, Paul E. "(a, b) -tree" . Словарь алгоритмов и структур данных .