(a, b) -tree - (a,b)-tree

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

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

• 1 Определение
• 2 Представление внутреннего узла
• 3 См. Также
• 4 Ссылки

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

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

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

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

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

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

.