Шаг 147.
Основы языка Haskell. Рекурсивные типы данных. BST-деревья. Операция "включение в корень бинарного дерева поиска"

    На этом шаге мы рассмотрим особенности использования этой операции.

    Приведём рекурсивную реализацию операции "включение в корень BST-дерева" (по [1, с.513]):

    Пример (по [1, с.515]). Построим BST-дерево путём последовательного включения ключей

   A, S, E, R, C, H, I
в первоначально пустое дерево с использованием операции "включение в корень":


    Замечание (важное). Практическое преимущество использования операции "включение в корень" состоит в том, что недавно вставленные ключи располагаются в окрестности вершины.

    Следовательно, затраты времени при поиске недавно включённых ключей, скорее всего, будут меньше.



(1) Седжвик Р. Фундаментальные алгоритмы C++. Анализ. Структуры данных. Сортировка. Поиск. - К.: ДиаСофт, 2001. - 688 с.

    На следующем шаге мы рассмотрим операцию "скос".




Предыдущий шаг Содержание Следующий шаг