Подумайте как можно построить дерево поиска из массива данных
Перейти к содержимому

Подумайте как можно построить дерево поиска из массива данных

  • автор:

Бинарные деревья поиска и рекурсия – это просто

Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.

Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями.

image

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

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

image

Рис. 2 Бинарное дерево поиска
Сбалансированное бинарное дерево поиска — это бинарное дерево поиска с логарифмической высотой. Данное определение скорее идейное, чем строгое. Строгое определение оперирует разницей глубины самого глубокого и самого неглубокого листа (в AVL-деревьях) или отношением глубины самого глубокого и самого неглубокого листа (в красно-черных деревьях). В сбалансированном бинарном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма). В вырожденном случае несбалансированного бинарного дерева поиска, например, когда в пустое дерево вставлялась отсортированная последовательность, дерево превратится в линейный список, и операции поиска, вставки и удаления будут выполняться за линейное время. Поэтому балансировка дерева крайне важна. Технически балансировка осуществляется поворотами частей дерева при вставке нового элемента, если вставка данного элемента нарушила условие сбалансированности.

image

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

Сбалансированное бинарное дерево поиска применяется, когда необходимо осуществлять быстрый поиск элементов, чередующийся со вставками новых элементов и удалениями существующих. В случае, если набор элементов, хранящийся в структуре данных фиксирован и нет новых вставок и удалений, то массив предпочтительнее. Потому что поиск можно осуществлять алгоритмом бинарного поиска за то же логарифмическое время, но отсутствуют дополнительные издержки по хранению и использованию указателей. Например, в С++ ассоциативные контейнеры set и map представляют собой сбалансированное бинарное дерево поиска.

image

Рис. 4 Экстремально несбалансированное бинарное дерево поиска

Теперь кратко обсудим рекурсию. Рекурсия в программировании – это вызов функцией самой себя с другими аргументами. В принципе, рекурсивная функция может вызывать сама себя и с теми же самыми аргументами, но в этом случае будет бесконечный цикл рекурсии, который закончится переполнением стека. Внутри любой рекурсивной функции должен быть базовый случай, при котором происходит выход из функции, а также вызов или вызовы самой себя с другими аргументами. Аргументы не просто должны быть другими, а должны приближать вызов функции к базовому случаю. Например, вызов внутри рекурсивной функции расчета факториала должен идти с меньшим по значению аргументом, а вызовы внутри рекурсивной функции обхода дерева должны идти с узлами, находящимися дальше от корня, ближе к листьям. Рекурсия может быть не только прямой (вызов непосредственно себя), но и косвенной. Например А вызывает Б, а Б вызывает А. С помощью рекурсии можно эмулировать итеративный цикл, а также работу структуры данных стек (LIFO).

int factorial(int n) < if(n return n * factorial(n - 1); //рекурсивеый вызов с другим аргументом > // factorial(1): return 1 // factorial(2): return 2 * factorial(1) (return 2 * 1) // factorial(3): return 3 * factorial(2) (return 3 * 2 * 1) // factorial(4): return 4 * factorial(3) (return 4 * 3 * 2 * 1) // Вычисляет факториал числа n (n должно быть небольшим из-за типа int // возвращаемого значения. На практике можно сделать long long и вообще // заменить рекурсию циклом. Если важна скорость рассчетов и не жалко память, то // можно совсем избавиться от функции и использовать массив с предварительно // посчитанными факториалами). void reverseBinary(int n) < if (n == 0) // Базовый случай < return; >cout // Печатает бинарное представление числа в обратном порядке void forvardBinary(int n) < if (n == 0) // Базовый случай < return; >forvardBinary(n/2); //рекурсивеый вызов с другим аргументом cout // Поменяли местами две последние инструкции // Печатает бинарное представление числа в прямом порядке // Функция является примером эмуляции стека void ReverseForvardBinary(int n) < if (n == 0) // Базовый случай < return; >cout // Функция печатает сначала бинарное представление в обратном порядке, // а затем в прямом порядке int product(int x, int y) < if (y == 0) // Базовый случай < return 0; >return (x + product(x, y-1)); //рекурсивеый вызов с другим аргументом > // Функция вычисляет произведение x * y ( складывает x y раз) // Функция абсурдна с точки зрения практики, // приведена для лучшего понимания рекурсии 

Кратко обсудим деревья с точки зрения теории графов. Граф – это множество вершин и ребер. Ребро – это связь между двумя вершинами. Количество возможных ребер в графе квадратично зависит от количества вершин (для понимания можно представить турнирную таблицу сыгранных матчей). Дерево – это связный граф без циклов. Связность означает, что из любой вершины в любую другую существует путь по ребрам. Отсутствие циклов означает, что данный путь – единственный. Обход графа – это систематическое посещение всех его вершин по одному разу каждой. Существует два вида обхода графа: 1) поиск в глубину; 2) поиск в ширину.

Поиск в ширину (BFS) идет из начальной вершины, посещает сначала все вершины находящиеся на расстоянии одного ребра от начальной, потом посещает все вершины на расстоянии два ребра от начальной и так далее. Алгоритм поиска в ширину является по своей природе нерекурсивным (итеративным). Для его реализации применяется структура данных очередь (FIFO).

Поиск в глубину (DFS) идет из начальной вершины, посещая еще не посещенные вершины без оглядки на удаленность от начальной вершины. Алгоритм поиска в глубину по своей природе является рекурсивным. Для эмуляции рекурсии в итеративном варианте алгоритма применяется структура данных стек.

С формальной точки зрения можно сделать как рекурсивную, так и итеративную версию как поиска в ширину, так и поиска в глубину. Для обхода в ширину в обоих случаях необходима очередь. Рекурсия в рекурсивной реализации обхода в ширину всего лишь эмулирует цикл. Для обхода в глубину существует рекурсивная реализация без стека, рекурсивная реализация со стеком и итеративная реализация со стеком. Итеративная реализация обхода в глубину без стека невозможна.

Асимптотическая сложность обхода и в ширину и в глубину O(V + E), где V – количество вершин, E – количество ребер. То есть является линейной по количеству вершин и ребер. Записи O(V + E) с содержательной точки зрения эквивалентна запись O(max(V,E)), но последняя не принята. То есть, сложность будет определятся максимальным из двух значений. Несмотря на то, что количество ребер квадратично зависит от количества вершин, мы не можем записать сложность как O(E), так как если граф сильно разреженный, то это будет ошибкой.

DFS применяется в алгоритме нахождения компонентов сильной связности в ориентированном графе. BFS применяется для нахождения кратчайшего пути в графе, в алгоритмах рассылки сообщений по сети, в сборщиках мусора, в программе индексирования – пауке поискового движка. И DFS и BFS применяются в алгоритме поиска минимального покрывающего дерева, при проверке циклов в графе, для проверки двудольности.
Обходу в ширину в графе соответствует обход по уровням бинарного дерева. При данном обходе идет посещение узлов по принципу сверху вниз и слева направо. Обходу в глубину в графе соответствуют три вида обходов бинарного дерева: прямой (pre-order), симметричный (in-order) и обратный (post-order).

Прямой обход идет в следующем порядке: корень, левый потомок, правый потомок. Симметричный — левый потомок, корень, правый потомок. Обратный – левый потомок, правый потомок, корень. В коде рекурсивной функции соответствующего обхода сохраняется соответствующий порядок вызовов (порядок строк кода), где вместо корня идет вызов данной рекурсивной функции.

Если нам дано изображение дерева, и нужно найти его обходы, то может помочь следующая техника (см. рис. 5). Обводим дерево огибающей замкнутой кривой (начинаем идти слева вниз и замыкаем справа вверх). Прямому обходу будет соответствовать порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами слева. Для симметричного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами снизу. Для обратного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами справа. В коде рекурсивного вызова прямого обхода идет: вызов, левый, правый. Симметричного – левый, вызов, правый. Обратного – левый правый, вызов.

image

Рис. 5 Вспомогательный рисунок для обходов

Для бинарных деревьев поиска симметричный обход проходит все узлы в отсортированном порядке. Если мы хотим посетить узлы в обратно отсортированном порядке, то в коде рекурсивной функции симметричного обхода следует поменять местами правого и левого потомка.

struct TreeNode < double data; // ключ/данные TreeNode *left; // указатель на левого потомка TreeNode *right; // указатель на правого потомка >; void levelOrderPrint(TreeNode *root) < if (root == NULL) < return; >queue q; // Создаем очередь q.push(root); // Вставляем корень в очередь while (!q.empty() ) // пока очередь не пуста < TreeNode* temp = q.front(); // Берем первый элемент в очереди q.pop(); // Удаляем первый элемент в очереди cout data left != NULL ) q.push(temp->left); // Вставляем в очередь левого потомка if ( temp->right != NULL ) q.push(temp->right); // Вставляем в очередь правого потомка > > void preorderPrint(TreeNode *root) < if (root == NULL) // Базовый случай < return; >cout data left); //рекурсивный вызов левого поддерева preorderPrint(root->right); //рекурсивный вызов правого поддерева > // Функция печатает значения бинарного дерева поиска в прямом порядке. // Вместо печати первой инструкцией функции может быть любое действие // с данным узлом void inorderPrint(TreeNode *root) < if (root == NULL) // Базовый случай < return; >preorderPrint(root->left); //рекурсивный вызов левого поддерева cout data right); //рекурсивный вызов правого поддерева > // Функция печатает значения бинарного дерева поиска в симметричном порядке. // То есть в отсортированном порядке void postorderPrint(TreeNode *root) < if (root == NULL) // Базовый случай < return; >preorderPrint(root->left); //рекурсивный вызов левого поддерева preorderPrint(root->right); //рекурсивный вызов правого поддерева cout data // Функция печатает значения бинарного дерева поиска в обратном порядке. // Не путайте обратный и обратноотсортированный (обратный симметричный). void reverseInorderPrint(TreeNode *root) < if (root == NULL) // Базовый случай < return; >preorderPrint(root->right); //рекурсивный вызов правого поддерева cout data left); //рекурсивный вызов левого поддерева > // Функция печатает значения бинарного дерева поиска в обратном симметричном порядке. // То есть в обратном отсортированном порядке void iterativePreorder(TreeNode *root) < if (root == NULL) < return; >stack s; // Создаем стек s.push(root); // Вставляем корень в стек /* Извлекаем из стека один за другим все элементы. Для каждого извлеченного делаем следующее 1) печатаем его 2) вставляем в стек правого! потомка (Внимание! стек поменяет порядок выполнения на противоположный!) 3) вставляем в стек левого! потомка */ while (s.empty() == false) < // Извлекаем вершину стека и печатаем TreeNode *temp = s.top(); s.pop(); cout data right) s.push(temp->right); // Вставляем в стек правого потомка if (temp->left) s.push(temp->left); // Вставляем в стек левого потомка > > // В симметричном и обратном итеративном обходах просто меняем инструкции // местами по аналогии с рекурсивными функциями. 

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

Вы когда‑нибудь задумывались, почему результаты поиска файлов появляются так быстро? В этой статье мы рассмотрим удивительную структуру данных, известную как двоичное дерево (бинарное дерево), и узнаем, как именно она позволяет достичь такой быстрой обработки и поиска.

Быстрый поиск

В этой статье вы узнаете, что такое двоичные деревья, как работает один из типов двоичных деревьев — двоичное дерево поиска, и почему сегодня они используются во многих алгоритмах.

Двои́чное де́рево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево является упорядоченным ориентированным деревом[1].

Двоичное дерево

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

Полное бинарное дерево — это дерево, в котором каждый узел имеет ноль или два ребенка. Другими словами, не существует единичных узлов.

Примером идеального бинарного дерева может служить семейное дерево, в котором у каждого ребенка есть мать и отец.

А сбалансированное бинарное дерево — это такое дерево, которое имеет минимально возможную высоту.

Бинарные деревья, которые очень, очень глубоки, которые не сбалансированы правильно, могут быть очень неэффективными.

Поэтому мы стараемся организовать деревья минимально возможной высоты.

Еще два термина, которые вам могут встретиться, это «поиск в ширину» (Breadth‑First Search) и «поиск в глубину» (Depth‑First Search).

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

С другой стороны, поиск в глубину подразумевает исследование дерева до самого его конца. В этом случае вы предполагаете, что искомые данные или решение проблемы находятся глубоко в структуре дерева. Решение задач, связанных с лабиринтами, является типичным примером использования поиска в глубину в двоичном дереве.

Не стоит волноваться, если вы не знаете, как реализовать или применить эти термины на практике. Они важны для понимания, особенно в контексте технических собеседований, чтобы вы могли с уверенностью заявить: «Да, я слышал об этих терминах». Возможно, вы не сталкиваетесь с ними ежедневно в своей работе, и это нормально.

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

Как они работают?

Один из способов получить хорошее представление о том, как работают бинарные деревья, — это рассмотреть метод find в так называемом бинарном дереве поиска.

Бинарное дерево поиска — это дерево, узлы которого отсортированы сверху вниз. Отсортированные узлы означают, что все узлы слева от родителя меньше родителя. В то время как все узлы справа больше родительского. Под больше или меньше мы понимаем ключи. Используемые ключи уникально представляют этот узел. Сортируя двоичное дерево сверху вниз, мы теперь имеем дерево в таком состоянии, что можем сделать с ним что‑то очень мощное и крутое — Мы можем начать быстрый поиск.

поиск(find)

Подробное описание

Реализация find для двоичного дерева поиска выглядит примерно так. Допустим, мы ищем число четыре или ключ четыре в нашем упорядоченном двоичном дереве. Мы начинаем с корня, с самой вершины. Мы спрашиваем, тот ли это ключ, который мы ищем? Если это не так, мы продолжаем поиск и спрашиваем: ну, а искомый ключ меньше или больше текущего узла? В данном случае, поскольку четыре меньше пяти, мы идем влево и здесь повторяем вопрос. Есть ли у нас четверка? Если нет, продолжаем искать. Четыре меньше, чем три? В данном случае четыре больше трех. Поэтому мы идем вправо и продолжаем этот процесс, продвигаясь все дальше и дальше по двоичному дереву, пока не найдем либо искомый узел, либо не достигнем конца нашего дерева, в этом случае мы просто вернем null.

Двоичные деревья состоят из более мелких деревьев и поддеревьев, которые вложены друг в друга. Когда мы рассматриваем их код, мы видим, что это становится очевидным благодаря рекурсии. Кроме того, важно отметить, что при поиске или принятии решений в двоичном дереве мы сокращаем область поиска вдвое каждый раз. Каждый переход от одного уровня к следующему через узел фактически устраняет половину дерева. Это особенность двоичных деревьев, которая позволяет выполнять поиск очень быстро со временной сложностью O(log n). Этот непрерывный процесс сокращения вдвое обеспечивает временную сложность O(log n) для поиска в двоичных деревьях. Чтобы увидеть и понять, как это работает, давайте рассмотрим его в коде.

class Node < var key: Int = 0 var left: Node? var right: Node? init(_ key: Int) < self.key = key >var min: Node < if left == nil < return self >else < return left!.min >> > class BST < var root: Node? // вставка func insert(key: Int) < root = insertItem(root, key) >private func insertItem(_ node: Node?, _ key: Int) -> Node < // Если узел равен nil - значит сюда мы и вставим guard let node = node else < let node = Node(key) return node >if key < node.key < node.left = insertItem(node.left, key) >if key > node.key < node.right = insertItem(node.right, key) >// Если мы дошли сюда значит у нас дубликат. // Дубликаты запрещены в дереве поэтому просто игнорируем // Мы закончили, Наше дерево готово! return node; > // поиск func find(key: Int) -> Int? < guard let root = root else < return nil >guard let node = find(root, key) else < return nil >return node.key > private func find(_ node: Node?, _ key: Int) -> Node? < guard let node = node else < return nil >if node.key == key < return node >else if key < node.key < return find(node.left, key) >else if key > node.key < return find(node.right, key) >return nil // Note: дублирование ключей запрещено так что нам не нужна проверка >

Описание кода

Класс Node: Этот класс представляет узел дерева. Каждый узел имеет ключ (key), который является значением узла, а также ссылки на левого и правого потомка (left и right). У него есть инициализатор, который принимает ключ в качестве входного параметра, и свойство min, которое возвращает узел с наименьшим ключом в поддереве.

Класс BST (Binary Search Tree): Этот класс представляет собой двоичное дерево поиска. У него есть корневой узел (root) и две основные функции:

Функция insert(key: Int): Это функция добавляет новый узел с указанным ключом в дерево. Она вызывает вспомогательную функцию insertItem, которая рекурсивно ищет место для вставки нового узла и создает его при достижении nil (то есть достигнута конечная точка в ветке дерева). Если в дереве уже присутствует узел с таким же ключом, то новый узел не будет добавлен, поскольку дубликаты запрещены.

Функция find(key: Int): Эта функция ищет узел с заданным ключом в дереве. Она также использует вспомогательную функцию find, которая рекурсивно ищет узел в дереве. Если узел с заданным ключом не найден, функция возвращает nil.

Вставка(insert)

вставка

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

Вот как мы бы это сделали:

Мы начнем наш путь с вершины дерева, где сейчас находится число пять. Задумаемся на мгновение: мы собираемся вставить двойку, так что нам нужно определить, куда она будет подходить лучше всего. Вспомним правило двоичного дерева: все числа меньше родительского узла должны быть слева. В нашем случае двойка меньше пяти, поэтому мы уверенно направляемся к левой ветке дерева, где находится тройка. Теперь у нас новый узел для сравнения — это тройка. Проверяем ещё раз: наше число, двойка, меньше тройки, так что мы продолжаем движение вниз по левой ветке. Наша цель — найти место, которое ещё не занято, или, говоря техническим языком, достичь nil значения в нашем дереве. В этом месте мы и вставим нашу двойку.

Нахождение минимума(findMin)

Теперь, прежде чем мы перейдем к работе с удалениями, один метод, который действительно полезно разобрать, — это поиск минимума в дереве двоичного поиска. И это на самом деле очень просто.
Если вы просто вспомните, что всякий раз, когда мы смотрим на дерево двоичного поиска, мы знаем, что все элементы слева будут меньше, чем все элементы справа.
Поэтому все, что нам действительно нужно сделать, это пройти по левой стороне нашего дерева, пока мы не встретим ноль.

И когда мы это делаем, это означает, что нет элементов меньше, чем тот, на котором мы сейчас находимся, поэтому мы можем просто вернуть этот узел.

В коде это будет выглядеть примерно так.

func findMin() -> Int < guard let root = root else < return 0 >return findMin(root).key; > private func findMin(_ node: Node) -> Node

Мы можем поместить эту ответственность прямо в сам класс узла, и это всего лишь четыре строчки кода. Когда мы вызываем minimum на узле, мы просто проверяем, есть ли что‑нибудь слева от нас? Если нет, мы знаем, что достигли минимума, и можем просто вернуть его. Но если нет, давайте просто продолжим повторять и идти вниз по левой стороне дерева, пока не встретим этот null, а затем вернем его.

Обработка удалений

Удаление элементов из двоичного дерева поиска — это вполне достижимая задача, хотя и с некоторыми нюансами. Как вы упомянули, у нас есть три различных случая для рассмотрения: узлы без детей, узлы с одним ребенком и узлы с двумя детьми.

  1. Узел без детей — это самый простой случай. Здесь наш узел — это лист дерева, он сам по себе, без каких‑либо ветвей, растущих от него. Чтобы удалить такой узел, достаточно просто оборвать связь, которая связывает его с родителем. Можно представить, что этот узел — это капля воды на листе дерева, которая просто катится и падает, когда мы ее трогаем.
  2. Узел с одним ребенком — это немного сложнее, но всё же вполне управляемый случай. Здесь у нашего узла есть одна ветка — может быть либо слева, либо справа. Чтобы удалить этот узел, мы просто перенаправляем ссылку от родительского узла к ребенку этого узла. Это как переключить стрелку дорожного указателя, чтобы она указывала прямо на следующий узел.
  3. Наконец, узел с двумя детьми — это наиболее сложный случай. Однако, несмотря на это, в нём есть своя логика и порядок. Здесь наш узел имеет две ветви, и мы не можем просто перенаправить ссылку, как в предыдущем случае. Вместо этого мы находим минимальный узел в правом поддереве (или максимальный узел в левом поддереве), заменяем удаляемый узел этим узлом и затем удаляем найденный узел. Рассмотрим код:
 func delete(key: Int) < guard let _ = root else < return >root = delete(&root, key); > private func delete(_ node: inout Node?, _ key: Int) -> Node? < guard let nd = node else < return nil >if key < nd.key < nd.left = delete(&nd.left, key) >else if key > nd.key < nd.right = delete(&nd.right, key) >else < // Кейс 1: Нет детей if nd.left == nil && nd.right == nil < return nil >// Кейс 2: Один ребенок else if nd.left == nil < return nd.right else if nd.right == nil < return nd.left >// Кейс 3: Двое детей else < // Находим минимальный узел справа // (также может быть максимум слева) let minRight = findMin(nd.right!) // копируем значения nd.key = minRight.key // удаляем ноду которую только что копировали nd.right = delete(&nd.right, nd.key) >> return nd >

Обход двоичного дерева

Ранее мы рассмотрели два различных способа обхода двоичного дерева. Вы можете пройтись по двоичному дереву в ширину и в глубину. В этом разделе мы рассмотрим три различных способа, которыми можно пройтись по двоичному дереву в глубину, и несколько различных способов обхода.

Обход двоичного дерева — это процесс посещения каждого узла в дереве в определенном порядке. Существуют три основные стратегии обхода: «inorder» (симметричный обход), «preorder» (прямой обход) и «postorder» (обратный обход). Каждый из этих методов обхода применяется для различных задач и имеет свои особенности.

Inorder (Симметричный обход): При этом типе обхода, мы сначала посещаем левый дочерний узел, затем родительский узел, и наконец правый дочерний узел. Если используется на дереве двоичного поиска, симметричный обход выводит узлы в возрастающем порядке.

Preorder (Прямой обход): В этом типе обхода сначала посещается родительский узел, затем его левый дочерний узел, и наконец правый дочерний узел. Этот метод обхода полезен для создания копии дерева, так как он клонирует корень дерева перед его поддеревьями.

Postorder (Обратный обход): Здесь сначала посещаются оба дочерних узла, и только после этого посещается родительский узел. Этот метод обхода полезен при удалении узлов дерева, так как он сначала удаляет дочерние узлы, прежде чем удалять родительский узел.
Важно помнить, что во всех этих методах обхода каждый узел посещается ровно один раз.

Характеристики времени выполнения

Когда мы говорим о двоичных деревьях поиска, одно из самых важных понятий — это временная сложность, которая обозначается как O(log n). Это относится к скорости, с которой происходят операции поиска, вставки и удаления в двоичном дереве поиска.

Если вы пытаетесь понять, что означает O(log n), подумайте о том, как работает двоичное дерево. Каждый раз, когда мы проходим через уровень дерева, количество операций, которые нам нужно выполнить, уменьшается вдвое. То есть, мы «расщепляем» пространство поиска на половины с каждым шагом. Это и есть логарифмическое сокращение, отсюда и выражение log n. Так что просто запомните: время, которое потребуется для выполнения операций поиска, вставки или удаления в двоичном дереве поиска, определяется как O(log n).

Заключение

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

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

Вы также усвоили, что существуют разные подходы к исследованию дерева: можно идти вглубь или вширь. Если вы услышите эти термины, вы будете знать, о чем идет речь. И помимо глубины, есть различные способы обхода двоичного дерева.

Но самое главное, что стоит помнить о двоичных деревьях поиска, — это их эффективность в вопросах поиска. Их «суперсила» — это возможность осуществлять поиск со скоростью O(log n), что означает очень быстрый поиск.

Спасибо, что дочитали до конца! Удачи в ваших проектах и дальнейшем развитии в области iOS‑разработки! Подписывайтесь на мой канал с авторским контентом SwiftyGroup.

  • бинарные деревья
  • двоичные деревья
  • swift
  • структуры данных
  • алгоритмы поиска

Бинарное дерево на основе массива

Author24 — интернет-сервис помощи студентам

Всем привет. Начал изучать бинарное дерево на основе массива, нужна подсказка, я правильно начал делать? Или лучше использовать классы? И кто-нибудь может показать, для примера, как написать функцию добавления элемента. Поискал в интернете, но на основе массива толком ничего нет. Заранее спасибо!

1 2 3 4 5 6 7 8 9 10 11 12 13
#include using namespace std; const int MaxLength = 100; //Описание структуры struct Node { int Values[MaxLength]; int father; int left; int right; int free; // Индекс свободного списка Node() { father = left = right = free = 0; }; };

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при.

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

Перемещение элементов массива на бинарное дерево
Добрый день. Помогите пожалуйста, стоит задача сформировать минимальное пирамидальное дерево для.

Бинарное дерево с использованием статического массива
Помогите пожалуйста с программой. Мне дали вот такое задание: Cпроектировать структуру типа.

Форумчанин

Эксперт CЭксперт С++

8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453

Бинарное дерево — структура данных с самоадресацией, массив ограничивает количество элементов, так что с помощью него никто Бин.дерево не реализовывает, это изврат.

Комп_Оратор)

Эксперт по математике/физике

8950 / 4704 / 629
Регистрация: 04.12.2011
Сообщений: 14,001
Записей в блоге: 16

ЦитатаСообщение от Aidar Посмотреть сообщение

ачал изучать бинарное дерево на основе массива

Aidar, ссылку дайте. Бывают разреженные массивы и хеш-таблицы не основе BST но не наоборот.
Хотя массив бинарных деревьев указателей на бинарные деревья создать можно.

Регистрация: 21.09.2015
Сообщений: 51
MrGluck, преподавателю также сказать?
Форумчанин

Эксперт CЭксперт С++

8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453

ЦитатаСообщение от Aidar Посмотреть сообщение

MrGluck, преподавателю также сказать?
Можете сказать. Только прикрепите это реализацией на структурах с указателями.
Регистрация: 21.09.2015
Сообщений: 51

IGPIGP, вот, что я имел виду(задание): реализовать все типовые операции над двоичным деревом поиска на базе одномерного массива.

Добавлено через 6 минут
MrGluck, а если не пройдет, вы поможете?

Добавлено через 5 минут
MrGluck, а если использовать динамический массив, допустим, вектор, это тоже изврат?

Комп_Оратор)

Эксперт по математике/физике

8950 / 4704 / 629
Регистрация: 04.12.2011
Сообщений: 14,001
Записей в блоге: 16

ЦитатаСообщение от Aidar Посмотреть сообщение

IGPIGP, вот, что я имел виду(задание): реализовать все типовые операции над двоичным деревом поиска на базе одномерного массива.

На базе массива можно, например, организовать бинарный поиск если его упорядочить. Но дерево на основе массива делать можно лишь как дерево указателей на элементы. Это достаточно изощрённый подход, но он имеет право на жизнь если экземпляры имеют большой размер, а приходят как поток. Тогда можно быстро создавать хранилище как список или даже массив (агромадный статический), а поисковую структуру организовать в виде дерева указателей.
Я думаю, это не о том. Или Вы излагаете задачу языком далёким от её постановки.
Тут скорее всего либо бинарный поиск на массиве либо разреженный массив на основе дерева. Последнее технически и идеологически намного сложнее. Советую уточнить задание и точный текст — сюда, если не всё понятно.

Дерево поиска, наивная реализация

Бинарное дерево поиска (англ. binary search tree, BST) — структура данных для работы с упорядоченными множествами.

Бинарное дерево поиска обладает следующим свойством: если [math]x[/math] — узел бинарного дерева с ключом [math]k[/math] , то все узлы в левом поддереве должны иметь ключи, меньшие [math]k[/math] , а в правом поддереве большие [math]k[/math] .

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

Для представления бинарного дерева поиска в памяти будем использовать следующую структуру:

struct Node: T key // ключ узла Node left // указатель на левого потомка Node right // указатель на правого потомка Node parent // указатель на предка 

Обход дерева поиска

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

  • [math]\mathrm[/math] — обход узлов в отсортированном порядке,
  • [math]\mathrm[/math] — обход узлов в порядке: вершина, левое поддерево, правое поддерево,
  • [math]\mathrm[/math] — обход узлов в порядке: левое поддерево, правое поддерево, вершина.
func inorderTraversal(x : Node): if x != null inorderTraversal(x.left) print x.key inorderTraversal(x.right)

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 3 4 6 7 8 10 13 14.

func preorderTraversal(x : Node) if x != null print x.key preorderTraversal(x.left) preorderTraversal(x.right)

При выполнении данного обхода вершины будут выведены в следующем порядке: 8 3 1 6 4 7 10 14 13.

func postorderTraversal(x : Node) if x != null postorderTraversal(x.left) postorderTraversal(x.right) print x.key

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 4 7 6 3 13 14 10 8.

Данные алгоритмы выполняют обход за время [math]O(n)[/math] , поскольку процедура вызывается ровно два раза для каждого узла дерева.

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

Поиск элемента 4

Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы [math]O(h)[/math] , где [math]h[/math] — высота дерева.

Node search(x : Node, k : T): if x == null or k == x.key return x if k < x.key return search(x.left, k) else return search(x.right, k)

Поиск минимума и максимума

Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям [math]left[/math] от корня дерева, пока не встретится значение [math]null[/math] . Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.

Node minimum(x : Node): if x.left == null return x return minimum(x.left)
Node maximum(x : Node): if x.right == null return x return maximum(x.right)

Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время [math]O(h)[/math] .

Поиск следующего и предыдущего элемента

Реализация с использованием информации о родителе

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

Node next(x : Node): if x.right != null return minimum(x.right) y = x.parent while y != null and x == y.right x = y y = y.parent return y
Node prev(x : Node): if x.left != null return maximum(x.left) y = x.parent while y != null and x == y.left x = y y = y.parent return y

Обе операции выполняются за время [math]O(h)[/math] .

Реализация без использования информации о родителе

Рассмотрим поиск следующего элемента для некоторого ключа [math]x[/math] . Поиск будем начинать с корня дерева, храня текущий узел [math]current[/math] и узел [math]successor[/math] , последний посещенный узел, ключ которого больше [math]x[/math] .
Спускаемся вниз по дереву, как в алгоритме поиска узла. Рассмотрим ключ текущего узла [math]current[/math] . Если [math]current.key \leqslant x[/math] , значит следующий за [math]x[/math] узел находится в правом поддереве (в левом поддереве все ключи меньше [math]current.key[/math] ). Если же [math]x \lt current.key[/math] , то [math]x \lt next(x) \leqslant current.key[/math] , поэтому [math]current[/math] может быть следующим для ключа [math]x[/math] , либо следующий узел содержится в левом поддереве [math]current[/math] . Перейдем к нужному поддереву и повторим те же самые действия.
Аналогично реализуется операция поиска предыдущего элемента.

Node next(x : T): Node current = root, successor = null // root — корень дерева while current != null if current.key > x successor = current current = current.left else current = current.right return successor

Вставка

Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.

Реализация с использованием информации о родителе
func insert(x : Node, z : Node): // x — корень поддерева, z — вставляемый элемент while x != null if z.key > x.key if x.right != null x = x.right else z.parent = x x.right = z break else if z.key < x.key if x.left != null x = x.left else z.parent = x x.left = z break 
Реализация без использования информации о родителе
Node insert(x : Node, z : T): // x — корень поддерева, z — вставляемый ключ if x == null return Node(z) // подвесим Node с key = z else if z < x.key x.left = insert(x.left, z) else if z > x.key x.right = insert(x.right, z) return x

Время работы алгоритма для обеих реализаций — [math]O(h)[/math] .

Удаление

Нерекурсивная реализация

Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на [math]null[/math] . Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка), его правого потомка подвесить на место найденного элемента, а удаляемый узел заменить найденным узлом. Таким образом, свойство бинарного дерева поиска не будет нарушено. Данная реализация удаления не увеличивает высоту дерева. Время работы алгоритма — [math]O(h)[/math] .

Случай Иллюстрация
Удаление листа Bst del1.png
Удаление узла с одним дочерним узлом Bst del2.png
Удаление узла с двумя дочерними узлами Bst del3.png
func delete(t : Node, v : Node): // [math]t[/math] — дерево, [math]v[/math] — удаляемый элемент p = v.parent // предок удаляемого элемента if v.left == null and v.right == null // первый случай: удаляемый элемент - лист if p.left == v p.left = null if p.right == v p.right = null else if v.left == null or v.right == null // второй случай: удаляемый элемент имеет одного потомка if v.left == null if p.left == v p.left = v.right else p.right = v.right v.right.parent = p else if p.left == v p.left = v.left else p.right = v.left v.left.parent = p else // третий случай: удаляемый элемент имеет двух потомков successor = next(v, t) v.key = successor.key if successor.parent.left == successor successor.parent.left = successor.right if successor.right != null successor.right.parent = successor.parent else successor.parent.right = successor.right if successor.right != null successor.right.parent = successor.parent
Рекурсивная реализация

При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить этот минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма — [math]O(h)[/math] . Рекурсивная функция, возвращающая дерево с удаленным элементом [math]z[/math] :

Node delete(root : Node, z : T): // корень поддерева, удаляемый ключ if root == null return root if z < root.key root.left = delete(root.left, z) else if z > root.key root.right = delete(root.right, z) else if root.left != null and root.right != null root.key = minimum(root.right).key root.right = delete(root.right, root.key) else if root.left != null root = root.left else if root.right != null root = root.right else root = null return root

Задачи о бинарном дереве поиска

Проверка того, что заданное дерево является деревом поиска

Задача:
Определить, является ли заданное двоичное дерево деревом поиска.

Пример дерева, для которого недостаточно проверки лишь его соседних вершин

Для того чтобы решить эту задачу, применим обход в глубину. Запустим от корня рекурсивную логическую функцию, которая выведет [math]\mathtt[/math] , если дерево является BST и [math]\mathtt[/math] в противном случае. Чтобы дерево не являлось BST, в нём должна быть хотя бы одна вершина, которая не попадает под определение дерева поиска. То есть достаточно найти всего одну такую вершину, чтобы выйти из рекурсии и вернуть значение [math]\mathtt[/math] . Если же, дойдя до листьев, функция не встретит на своём пути такие вершины, она вернёт значение [math]\mathtt[/math] .

Функция принимает на вход исследуемую вершину, а также два значения: [math]\mathtt[/math] и [math]\mathtt[/math] , которые до вызова функции равнялись [math] \infty [/math] и [math] -\infty [/math] соответственно, где [math] \infty [/math] — очень большое число, т.е. ни один ключ дерева не превосходит его по модулю. Казалось бы, два последних параметра не нужны. Но без них программа может выдать неверный ответ, так как сравнения только вершины и её детей недостаточно. Необходимо также помнить, в каком поддереве для более старших предков мы находимся. Например, в этом дереве вершина с номером [math]8[/math] находится левее вершины, в которой лежит [math]5[/math] , чего не должно быть в дереве поиска, однако после проверки функция бы вернула [math]\mathtt[/math] .

bool isBinarySearchTree(root: Node): // Здесь root — корень заданного двоичного дерева. bool check(v : Node, min: T, max: T): // min и max — минимально и максимально допустимые значения в вершинах поддерева. if v == null return true if v.key or max return false return check(v.left, min, v.key) and check(v.right, v.key, max) return check(root, [math] -\infty [/math], [math] \infty [/math])

Время работы алгоритма — [math]O(n)[/math] , где [math]n[/math] — количество вершин в дереве.

Задачи на поиск максимального BST в заданном двоичном дереве

Задача:
Найти в данном дереве такую вершину, что она будет корнем поддерева поиска с наибольшим количеством вершин.

Если мы будем приведённым выше способом проверять каждую вершину, мы справимся с задачей за [math]O(n^2)[/math] . Но её можно решить за [math]O(n)[/math] , идя от корня и проверяя все вершины по одному разу, основываясь на следующих фактах:

  • Значение в вершине больше максимума в её левом поддереве;
  • Значение в вершине меньше минимума в её правом поддереве;
  • Левое и правое поддерево являются деревьями поиска.

Введём [math]\mathtt[/math] и [math]\mathtt[/math] , которые будут хранить минимум в левом поддереве вершины и максимум в правом. Тогда мы должны будем проверить, являются ли эти поддеревья деревьями поиска и, если да, лежит ли ключ вершины [math]\mathtt[/math] между этими значениями [math]\mathtt[/math] и [math]\mathtt[/math] . Если вершина является листом, она автоматически становится деревом поиска, а её ключ — минимумом или максимумом для её родителя (в зависимости от расположения вершины). Функция [math]\mathtt[/math] записывает в [math]\mathtt[/math] количество вершин в дереве, если оно является деревом поиска или [math]\mathtt[/math] в противном случае. После выполнения функции ищем за линейное время вершину с наибольшим значением [math]\mathtt[/math] .

int count(root: Node): // root — корень заданного двоичного дерева. int cnt(v: Node): if v == null v.kol = 0 return = 0 if cnt(v.left) != -1 and cnt(v.right) != -1 if v.left == null and v.right == null v.min = v.key v.max = v.key v.kol = 1 return 1 if v.left == null if v.right.max > v.key v.min = v.key v.kol = cnt(v.right) + 1 return v.kol if v.right == null if v.left.min < v.key v.max = v.key v.kol = cnt(v.left) + 1 return v.kol if v.left.min < v.key and v.right.max > v.key v.min = v.left.min v.max = v.right.max v.kol = v.left.kol + v.right.kol + 1 v.kol = cnt(v.left) + cnt(v.right) + 1 return v.kol return -1 return cnt(root)

Алгоритм работает за [math]O(n)[/math] , так как мы прошлись по дереву два раза за время, равное количеству вершин.

Восстановление дерева по результату обхода preorderTraversal

Задача:
Восстановить дерево по последовательности, выведенной после выполнения процедуры [math]\mathrm[/math] .

Восстановление дерева поиска по последовательности ключей

Как мы помним, процедура [math]\mathrm[/math] выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево. Это продолжается до тех пор, пока не будут выведены все вершины. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына. Когда мы, желая найти такую вершину, встречаем какую-нибудь другую, уже имеющую правого сына, проходим по ветке вправо. Мы имеем на это право, так как если такая вершина стоит, то процедура обхода в ней уже побывала и поворачивала вправо, поэтому спускаться в другую сторону смысла не имеет. Вершину с максимальным ключом, с которой будем начинать поиск, будем запоминать. Она будет обновляться каждый раз, когда появится новый максимум.

Процедура восстановления дерева работает за [math]O(n)[/math] .

Разберём алгоритм на примере последовательности [math]\mathtt[/math] [math]\mathtt[/math] [math]\mathtt[/math] [math]\mathtt[/math] [math]\mathtt[/math] [math]\mathtt[/math] .

Будем выделять красным цветом вершины, рассматриваемые на каждом шаге, чёрным жирным — их родителей, курсивом — убывающие подпоследовательности (в случаях, когда мы их рассматриваем) или претендентов на добавление к ним правого ребёнка (когда рассматривается вершина, нарушающая убывающую последовательность).

См. также

  • Поисковые структуры данных
  • Рандомизированное бинарное дерево поиска
  • Красно-черное дерево
  • АВЛ-дерево

Источники информации

  • Википедия — Двоичное дерево поиска
  • Wikipedia — Binary search tree
  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *