(a,b)-дерево

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

(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–3–4 дерево

Рекомендации

•  Эта статья включает общедоступные материалы Пола Э. Блэка. «(а,б)-дерево». Словарь алгоритмов и структур данных . НИСТ .