Рекурсивное определение дерева.

1.Пустое множество вершин есть (пустое) дерево;

2. Одна вершина, не связанная ни с какой другой вершиной, образует дерево и является корнем этого дерева;

3. Пусть имеется к деревьев Ti,...,Tk с корнями Аi,..., Ак, тогда, связывая вершину А с вершинами Ai,...,Ak, мы получим новое дерево, в котором А есть корень, а Тi...Тк — поддеревья.

Определение 6. Назовем ключом вершины дерева некоторое значение, которое однозначно вычисляется по содержательной информации, хранящейся в данной вершине, и связано неко­торым отношением порядка с ключами других вершин. Ключ используется для поиска или сравнения вершин дерева.

Определение 7. Будем называть бинарное дерево деревом поиска, если для любой вершины ключ этой вершины не меньше ключа любой вершины левого поддерева и строго меньше ключа любой вершины правого поддерева.

Определение 8. Бинарное дерево называется идеально сбалансированным, если длины любых двух его ветвей (считая от корня) отличаются не более чем на единицу.

Идеально сбалансированное дерево решает поставленную задачу, так как в нем длина любой ветви не превосходит величины [log₂ ЛГ] + 1. К сожалению, формирование такого дерева достаточно трудоемкая процедура. Поэтому мы несколько ослабим требования на идеальность балансировки дерева и попы­таемся за счет этого построить более эффективные алгоритмы. Итак, вместо идеально сбалансированного дерева введем понятие сбалансированного дерева.

Определение 9. Длиной дерева будем называть длину его максимальной ветви.

Определение 10. Бинарное дерево называется сбалансиро­ванным¹, если в любой его вершине длины левого и правого поддеревьев отличаются не более чем на 1.

 

Двоичное дерево поиска (by Wiki)

 

Двоичное дерево поиска — это структура данных двоичное дерево, в котором данные, привязанные к каждому узлу представляют собой пару (key, value) (ключ и значение), причём на ключах определена операция сравнения "меньше", и для всех узлов дерева выполнено свойство, называемое свойством дерева поиска:

у всех узлов левого поддерева произвольного узла n значение ключей меньше, нежели значения ключа узла n,

у всех узлов правого поддерева произвольного узла n значение ключей не меньше, нежели значения ключа узла n.Содержание [убрать]

1 Основные операции в двоичном дереве поиска

1.1 Поиск элемента (FIND)

1.2 Добавление элемента (ADD)

1.3 Удаление узла (DEL)

1.4 Обход дерева (TRAVERSE)

1.5 Сортировка с помощью двоичного дерева поиска

 

Основные операции в двоичном дереве поиска

 

Базовый интерфейс двоичного дерева поиска состоит из трех операций:

FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K.

ADD(K,V) — добавление в дерево пары (key, value) = (K, V).

DEL(K) — удаление узла, в котором хранится пара (key, value) с key = K.

 

Этот абстрактный интерфейс является общим случаем, например, таких интерфейсов, взятых из прикладных задач:

«Телефонная книжка» — хранилище записей (имя человека, его телефон) с операциями поиска и удаления записей по имени человека, и операцией добавления новой записи.

Domain Name Server — хранилище пар (доменное имя, IP адрес) с операциями модификации и поиска.

Namespace — хранилище имен переменных с их значениями, возникающее в трансляторах языков программирования.

 

По сути, двоичное дерево поиска — это структура данных, способная хранить таблицу пар (key, value) и поддерживающая три операции: FIND, ADD, DEL.

 

Кроме того, интерфейс двоичного дерева включает ещё три дополнительных операции обхода узлов дерева: INFIX_TRAVERSE, PREFIX_TRAVERSE и POSTFIX_TRAVERSE. Первая из них позволяет обойти узлы дерева в порядке неубывания ключей.

 

Поиск элемента (FIND)

 

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

 

Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.

 

Алгоритм:

Если дерево пусто, сообщить, что узел не найден, и остановиться.

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

Если K=X, выдать ссылку на этот узел и остановиться.

Если K>X, рекурсивно искать ключ K в правом поддереве Т.

Если K<X, рекурсивно искать ключ K в левом поддереве Т.

 

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

 

Дано: дерево Т и пара (K,V).

 

Задача: добавить пару (K, V) в дерево Т.

 

Алгоритм:

Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), nil, nil) и остановиться.

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

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

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

 

Удаление узла (DEL)

 

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

 

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

 

Алгоритм:

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

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

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

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

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

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

Если оба ребёнка присутствуют, то

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

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

у родителя узла m заменим ссылку на узел m ссылкой на правого ребёнка узла m (который, в принципе, может быть равен nil).

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

 

Обход дерева (TRAVERSE)

 

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов.

 

Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию call_back_function. Эта функция обычно работает только c парой (K,V), хранящейся в узле. Операция INFIX_TRAVERSE реализуется рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.

INFIX_TRAVERSE (call_back_function) — обойти всё дерево, следуя порядку (левое поддерево, вершина, правое поддерево).

PREFIX_TRAVERSE (call_back_function) — обойти всё дерево, следуя порядку (вершина, левое поддерево, правое поддерево).

POSTFIX_TRAVERSE (call_back_function) — обойти всё дерево, следуя порядку (левое поддерево, правое поддерево, вершина).

 

 

INFIX_TRAVERSE:

 

Дано: дерево Т и функция f

 

Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей

 

Алгоритм:

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

Иначе

Рекурсивно обойти правое поддерево Т.

Применить функцию f к корневому узлу.

Рекурсивно обойти левое поддерево Т.

 

В простейшем случае, функция f может выводить значение пары (K,V). При использовании операции INFIX_TRAVERSE будут выведены все пары в порядке возрастания ключей. Если же использовать PREFIX_TRAVERSE, то пары будут выведены в порядке, соответствующим описанию дерева, приведённого в начале статьи.

 

Сортировка с помощью двоичного дерева поиска

 

Бинарное дерево поиска можно использовать для сортировки. Для этого берётся пустое дерево, к нему добавляют все элементы массива, а затем, используя алгоритм "Обход дерева", записывают элементы дерева в массив в возрастающем порядке.

 

Если элементы массива различны и расположены в случайном порядке, а длина массива N, алгоритм требует в среднем O(NlogN) операций. Если они уже отсортированы в возрастающем или убывающем порядке, то дерево становится несбалансированным (т.е. у него появляется много пустых веток). Тогда алгоритм требует O(N2) операций, и это худший возможный случай. Чтобы сбалансировать дерево следует использовать алгоритм пирамиды или красно-чëрное дерево.

 

 

Билет №19

Реализация множества на базе вектора. Последовательный и двоичный поиск. Битовая реализация множества. Оценка сложности алгоритмов. Хеширование. Методы разрешения коллизий.

Множества

Существуют задачи, где упорядоченность данных не является существенной характеристикой на внешнем уровне представления. Для описания таких наборов данных наиболее подходит математическое понятие множества. С точки зрения задач обработки данных работа с множеством заключается в операциях добавления, удаления элемента, поиска конкретного элемента, а также перебора всех элементов, принадлежащих данному множеству. Отдельную область составляют операции с множествами как с цельными объектами — объединение, пересечение и др. Эти операции можно реализовать на основе операций поиска, добавления, удаления элементов в каждом отдельном множестве. При конкретизации предписаний работы с множеством может получиться следующий результат:

· Создать множество (пустое).

· Уничтожить множество.

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

· Удалить данный элемент.

· Элемент принадлежит множеству?

· Взять какой-нибудь элемент из множества.

· Очистить множество.

· Множество пусто?

· Итератор по элементам множества.

Списки и деревья можно рассматривать как некоторые реализации множеств, поскольку они позволяют организовать перебор всех элементов, а таже поиск элемента по его значению. Легко видеть, что на списках можно реализовать процедуру последовательного поиска, а поиск в бинарном дереве аналогичен методу деления пополам. Процедуры просмотра списка или обхода дерева реализуют операцию перебора в таком множестве.

 

8.1 Битовая реализация множества

Пусть нам требуется реализовать подмножество множества целых чисел, лежащих в диапазоне от 0 до некоторого числа Nmax — 1. В этом случае нам достаточно иметь массив из iV_max элементов, каждый из которых может принимать значения 0 и 1, т.е. элемент массива с номером к будет иметь значение 1, если число к принадлежит нашему множеству, и 0 — в противном случае. Таким образом, для реализации подобного множества нам достаточно хранить массив из iV_max бит, а для добавления или удаления элемента нужно устанавливать соответствующий бит этого массива в 1 или 0. Так как позиция каждого бита легко определяется по его номеру в массиве, то операции добавления и удаления можно выполнить очень эффективно. Реализация подобного множества сводится к реализации битового массива: выделяется некоторый массив целых чисел, каждое из которых рассматрива­ется как набор из фиксированного количества бит. Определение местоположения конкретного бита сводится в вычислению поряд­кового номера элемента базового массива чисел и определении номера нужного нам бита в этом элементе.

 

 

8.2 Хеширование

. Идея метода состоит в разделении исходного большого множество на несколько классов эквивалентности относительно некоторой функции (так назы­ваемой хеш-функции). Само слово хеширование происходит от английского слова hash, что дословно означает "рубить, крошить". Опишем идею хеширования более формально. Итак, пусть М — исходное множество всех возможных элементов интересующего нас типа, а N (- М — подмножество, с которым мы хотим в данный момент работать. Пусть на множестве М определена некоторая функция /, принимающая значения 0,...,р— 1, где р — некоторое натуральное число. Тогда функция / разбивает множество М на классы эквивалентности М_k

M_k = {x (- M: f(x) = k }.

Теперь при работе с множеством N для каждого интересующего нас элемента х нам достаточно вычислить значение k = f(x) и далее работать с множеством N_k = М_k ∩ N. При удачном выборе хеш-функции / количество элементов в множестве Nk будет в среднем в р раз меньше, чем во всем множестве N и, следовательно, поиск, добавление, удаление элементов будут выполняться существенно быстрее.

 

Бытовым примером применения метода хеширования мо­жет служить телефонная записная книжка, где хеш-функция сопоставляет каждому слову (фамилии) его первую букву. Действительно, при поиске информации о данном человеке мы первым делом открываем страницу записной книжки на первую букву фамилии ("вычисляем" хеш-функцию), а затем ищем или добавляем нужную запись в пределах этой страницы (работаем с множеством Nk).