(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 S_{v}[1\dots \rho _{v}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/940e5aaddc38a94cb4dfbc7717d73831ecc0292b)
![{\displaystyle H_{v}[1\dots \rho _{v}-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/991ab321ee4d679a64de75c26e9bfa0d0008dea8)
![{\displaystyle H_{v}[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19724308bb4f9c608be8ab9c29460bb789d4433b)
![{\displaystyle S_{v}[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a51cbe22f47a52c0f164ddf8505f583be9ea4f1c)
См. также [ править ]
Ссылки [ править ]
В этой статье использованы общедоступные материалы из Пол Э. Блэк. «(a,b)-дерево» . Словарь алгоритмов и структур данных . НИСТ .
 | Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее . |