На этом шаге мы рассмотрим особенности использования этой операции.
Приведём рекурсивную реализацию операции "включение в корень BST-дерева" (по [1, с.513]):
- (1) вначале необходимо рекурсивно включить новый элемент в соответствующее поддерево основного дерева (в качестве корня этого поддерева);
- (2) выполнить необходимое число раз операцию "ротация" для того, чтобы сделать новый элемент корнем основного дерева.
Пример (по [1, с.515]). Построим BST-дерево путём последовательного включения ключей
A, S, E, R, C, H, I
Замечание (важное). Практическое преимущество использования операции "включение в корень" состоит в том, что недавно вставленные ключи располагаются в окрестности вершины.
Следовательно, затраты времени при поиске недавно включённых ключей, скорее всего, будут меньше.
(1) Седжвик Р. Фундаментальные алгоритмы C++. Анализ. Структуры данных. Сортировка. Поиск. - К.: ДиаСофт, 2001. - 688 с.
На следующем шаге мы рассмотрим операцию "скос".
