24. Добавление элемента в двоичном дереве поиска.

Добавление элемента

Дано: дерево Т и элемент K.

Задача: добавить элемент K в дерево Т.

Алгоритм:

• Если дерево пусто, заменить его на дерево с одним корневым узлом (K, ПУСТО, ПУСТО) и остановиться.

• Иначе сравнить K с ключом корневого узла X.

  • Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т.

  • Если K<X, рекурсивно добавить (K,V) в левое поддерево Т.

Алгоритм InsertTree (T, k) //k – добавляемое значение

1. if T=nil

2. New (T)

3. T^.key←k

4. T^.left←nil

5. T^.right←nil

6. else

7. if (k<T^.key) then InsertTree (T^.left, k)

8. else InsrtTree (T^.right, k)

9. end if

10. end if

11. return T

Рассмотрим, например, вставку узла 8 в дерево BinSTree_1. Начав с корневого узла 25, определяем, что узел 8 должен быть в левом поддереве узла 25 (8<25). В узле 10 определяем, что место узла 8 должно быть в левом поддереве узла 10, которое в данный момент пусто. Узел 8 вставляется в дерево в качестве левого сына узла 10.

Вычислительная сложность.

Средний вариант – O(log n), худший случай – O(n).

25. Удаление элемента в двоичном дереве поиска.

Удаление узла

Дано: дерево Т с корнем n и ключом K.

Задача: удалить из дерева Т узел с ключом K (если такой есть).

Алгоритм:

• Если дерево T пусто, остановиться

• Иначе сравнить K с ключом X корневого узла n.

  • Если K>X, рекурсивно удалить K из правого поддерева Т.

  • Если K<X, рекурсивно удалить K из левого поддерева Т.

  • Если K=X, то необходимо рассмотреть два случая.

    • Если одного из детей нет, то значения полей второго ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m.

    • Если оба потомка присутствуют, то

      • найдём узел m, являющийся самым левым узлом правого поддерева;

      • скопируем значения полей (ключ, значение) узла m в соответствующие поля узла n.

      • у предка узла m заменим ссылку на узел m ссылкой на правого потомка узла m (который, в принципе, может быть равен ПУСТО).

      • освободим память, занимаемую узлом m (на него теперь никто не указывает, а его данные были перенесены в узел n).

Алгоритм Delete (T, k)

1. if T≠nil then

2. if k<T^.key then Delete (T^.left, k)

3. else if k>T^.key then Delete (T^.right, k)

4. else

5. if (T^.left=nil) and (T^.right=nil) then

6. p←T, T←nil, Dispose (p)

7. else if (T^.left=nil) then

8. p←T, T←T^.right, Dispose (p)

9. else if (T^.right=nil) then

10. p←T, T←T^.left, Dispose (p)

11. else Del (T^.right, p)

Del (T, p)

1. if T^.left=nil then

2. p^.key←T^.key

3. p₁←T

4. T←T^.right

5. Dispose (p₁)

6. return

7. else

8. Del (T^.left, p)

Вычислительная сложность.

Средний вариант – O(log n), худший случай – O(n).

26. Абстрактная таблица. Основные операции. Способ реализации.

Таблица – одна из важнейших структур данных, применяемая для хранения. Таблица состоит из совокупности элементов, снабженных отличительными признаками, называемыми ключами.

Одна строчка в таблице называется записью. Каждая колонка таблицы называется полем.

Одно или несколько полей играют особую роль и используются при поиске элементов. Их называют ключами записи. Ключи используются для доступа к элементам таблицы.

Таблицы данных классифицируются по различным признакам:

1. По месту хранения

   1. В оперативной памяти

   2. Во внешней памяти

2. По отношению связей между элементами

   1. Линейная

   2. Нелинейная

3. По упорядоченности элементов

   1. Упорядоченные

   2. Неупорядоченные

Операции:

1. Включить в таблицу новый элемент.

2. Удалить из таблицы элемент, поисковый ключ которого совпадает с заданным элементом.

3. Извлечь из таблицы элемент, поисковый ключ которого совпадает с заданным элементом.

4. Обойти элементы таблицы в порядке следования их поисковых ключей.

5. Определить, пуста ли таблица.

6. Определить количество элементов в таблице.

Организации таблицы делятся на линейные и нелинейные.

Способ реализации:

1. Линейный

   1. Неупорядоченный массив

   2. Неупорядоченный связный список

   3. Упорядоченный массив

   4. Упорядоченный связный список

2. Нелинейный

   1. Бинарное дерево поиска

   2. Сбалансированное дерево поиска

   3. Хеш-таблица

   4. Б-дерево

Вычислительная сложность

	Вставка	Удаление	Поиск	Обход
Неупорядоченный массив	O(1)	O(n)	O(n)	O(n)
Неупорядоченный список	O(1)	O(n)	O(n)	O(n)
Упорядоченный массив	O(n)	O(n)	O(log n)	O(n)
Упорядоченный список	O(n)	O(n)	O(n)	O(n)
Бинарное дерево поиска	O(log n)	O(log n)	O(log n)	O(n)