Дерево двоичного поиска
Дерево двоичного поиска — это структура данных, которая позволяет быстро работать с отсортированном списком чисел.
- Дерево двоичное, потому что у каждого узла не более двух дочерних элементов.
- Дерево поиска, потому что его можно использовать для проверки вхождения числа — за время O(log(n)) .
Чем отличается от обычного двоичного дерева
- Все узлы левого поддерева меньше корневого узла.
- Все узлы правого поддерева больше корневого узла.
- Оба поддерева каждого узла тоже являются деревьями двоичного поиска, т. е. также обладают первыми двумя свойствами.
У правого дерева есть поддерево со значением 2, которое меньше, чем корень 3 — таким дерево двоичного поиска быть не может.
Операции с двоичным деревом поиска
Поиск элемента
Сложность в среднем: O(log n)
Сложность в худшем случае: O(n)
Алгоритм зависит от свойств дерева: у каждого левого поддерева есть значения, которые ниже корня или у каждого правого поддерева есть значения, которые выше корня.
Если значение ниже корня, мы можем точно сказать, что оно находится не в правильном поддереве. Тогда нам нужно искать только в левом поддереве. А если значение выше корня, можно точно сказать, что значения нет в левом поддереве. Тогда ищем только в правом поддереве.
Алгоритм:
Изобразим это на диаграмме.
• Не нашли 4 → идем по левому поддереву корня 8
• Не нашли 4 → идем по левому поддереву корня 3
• Не нашли 4 → идем по левому поддереву корня 6
Если мы нашли значение, мы возвращаем его так, чтобы оно распространялось на каждом шаге рекурсии — рассмотрите рисунок ниже.
Как вы могли заметить, мы четыре раза вызывали search(struct node*) . Когда мы возвращаем новый узел или NULL , значение возвращается снова и снова, пока search(root) не вернет окончательный результат.
Если мы не нашли значение, значит, мы достигли левого или правого дочернего элемента листового узла, который имеет значение NULL — это значение также рекурсивно распространяется и возвращается.
Вставка элемента
Сложность в среднем: O(log n)
Сложность в худшем случае: ΘO(n)
Операция вставки значения похожа на поиск элемента. Мы также придерживаемся правила: левое поддерево меньше корня, правое поддерево — больше.
Мы продолжаем переходить либо к правому поддереву, либо к левому поддереву в зависимости от значения узла, и когда достигаем точки, в которой левое или правое поддерево имеет значение NULL, помещаем туда новый узел.
Алгоритм:
Алгоритм не такой простой, как может показаться на первый взгляд. Давайте визуализируем процесс.
• 4 < 8 → идем через левого «ребенка» 8.
• 4 > 3 → идем через правого «ребенка» 3.
• 4 < 6 → идем через левого «ребенка» 6.
• Левого «ребенка» у 6 нет → вставляем 4 как левый дочерний элемент 6.
Мы вставили узел в нужное место, но нам всё еще нужно выйти из функции, не повредив при этом остальную часть дерева. Здесь пригодится return node; . В случае с NULL , вновь созданный узел возвращается и присоединяется к родительскому узлу, иначе тот же узел возвращается без каких-либо изменений по мере продвижения вверх, пока мы не вернемся к корню.
Таким образом, когда мы будем двигаться обратно вверх по дереву, связи других узлов не изменятся.
Корень возвращаем в конце — так ничего не сломается.
Удаление элемента
Сложность в среднем: O(log n)
Сложность в худшем случае: O(n)
Всего может быть три случая при удаление элемента из дерева двоичного поиска. Давайте рассмотрим каждый.
Случай I: лист
Первый случай — когда нужно удалить листовой элемент. Просто удаляем узел из дерева.
• Нужно удалить 4.
• Просто удалили узел.
Случай II: есть дочерний элемент
Во втором случае у узла, который мы хотим удалить, есть один дочерний узел. В этом случае действуем так:
/dev/energy
Сайт о том, как стать программистом и как с этим жить потом
О простом. Построение простого дерева.
Совсем недавно я обнаружил очень интересную особенность развития современных web-программистов. Мы смело оперируем фабриками, синглтонами и декораторами, но забываем о такой фундаментальной части программирования, как классические алгоритмы. Ведь если присмотреться к их реализации, то это тоже своего рода паттерны. С институтской скамьи можно вспомнить, к примеру, nested sets, b-tree, сортировку «пузырьком». Реализация многих алгоритмов давно устоялась. А потому, я хотел бы посвятить несколько статей алгоритмам и их применении в PHP.
Начну я с самого простого — построения древовидной иерархии.
Казалось бы, что тут сложного? В базе данных есть таблица примерно следующего содержания:
| ID узла — id_node | ID родителя — id_parent | Заголовок — title |
|---|---|---|
| 1 | 2 | Один |
| 2 | 0 | Два |
| 3 | 4 | Три |
| 4 | 1 | Четыре |
| 5 | 2 | Пять |
Необходимо представить этот массив в виде древовидного меню. Я не буду говорить о том, какими неправильными способами можно решить эту задачу =)
Единственно верный подход в данном случае — рекурсивный метод.
Алгоритм (паттерн, если так хотите) будет примерно следующим:
0. Создаем объект дерева и выбираем все элементы в таблице.
1. Вызываем метод построения. Он инициализирует сборку массива родительских категорий. Именно этот момент является ноу-хау данного алгоритма. Он позволяет нам организовать изящную рекурсию.
2. Итеративно обходим массив, начиная с нулевого элемента. Выводим информацию о текущем элементе.
3. Увеличиваем уровень погружения. Рекурсивно вызываем метод для дочернего элемента. Если он есть в массиве родительских категорий, то идем к шагу 2, иначе — выходим в шаг-инициализатор.
4. Уменьшаем уровень погружения. Выходим из итерации.
Итак, метод сборки массива категорий будет выглядеть примерно вот так
Далее напишем наш рекурсивный метод в соответствии с приведенным выше алгоритмом
Теперь можем вызвать построение дерева, начиная с 0 элемента и 0 уровня. Замечу, что приведенный метод может вызывать построение с любой вложенной ноды и не ограничен по глубине.
А вот как будет выглядеть наше дерево в итоге : посмотреть
Данный метод применим при построении меню на сайте, каталогов продукции и т.п. У него, разумеется, есть недостатки. При построении достаточно большого каталога метод будет работать довольно долго. Но выигрыш тут в том, что метод можно модифицировать и ограничить не только уровнем входа, но и уровнем погружения. Таким образом, можно достраивать дерево постепенно при запросе пользователей, что решит данную проблему.
Я не рассматриваю здесь проблемы хранения такой структуры, т.к. нас сейчас интересует только обход массива.
Перемещение элементов массива на бинарное дерево
Помогите пожалуйста, стоит задача сформировать минимальное пирамидальное дерево для поиска на нем определенного элемента (уровня на котором он находится в дереве и позиции на этом уровне). Алгоритм стоит следующий: 1. Сформировать последовательность случайных чисел (без повторений); 2. Занести их в массив; 3. Массив отсортировать по возрастанию (дабы легче было переносить его на дерево и не пришлось сортировать само дерево); 4. Упорядоченный массив перенести на дерево по принципу (в корне стоит a[0] — минимальный элемент, потомки корня — левый a[1], правый a[2], потомки потомков корня слево-направо т.е. a[3] a[4] и тд. 5. Пользователь вводит число и программа ищет это число в дереве, если оно есть то программы пишет уровень и позицию где находится число. Так вот, с первыми тремя пунктами проблем нет, а вот дальше я не понимаю как записать в виде программы вышесказанное. Буду благодарен за любую помощь. Заранее спасибо.