Многоходовые деревья

Для сокращения количества обращений к внешней памяти используется некоторое обобщение бинарных деревьев – так называемые многоходовые деревья поиска. Особенности данного типа дерева заключаются в следующем:

1. каждая вершина дерева содержит N ключей и, соответственно, N + 1 указатель на подчиненные вершины (Рис. 7.4);

2. ключи в вершине упорядочены по возрастанию: K₁ < K₂ < … < K_N;

3. ключи в поддеревьях упорядочены по такому же принципу, как и в бинарном дереве.

Рис. 7.4. Структура вершины многоходового дерева

Если обозначить указатели на подчиненные вершины через P, тогда вершина имеет вид:

P₀ K₁ P₁ K₂ P₂ … P_N-1 K_N P_N,

и для ключа K_i текущей вершины должно выполняться условие:

{ K(P_i-1)} < K_i < {K(P_i)},

где {K(P)} определяет множество ключей в поддереве, заданном указателем P.

Пример многоходового дерева приведен на рис. 7.5.

Рис. 7.5. Пример многоходового дерева поиска