Что такое двоичное дерево поиска?

Двоичные деревья поиска полезны для организации данных. Вот полное описание того, как они работают

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

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

Что такое двоичное дерево поиска?

Image Credit: Pat Hawks/Wikimedia Commons.

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

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

1. Левый узел меньше своего родителя.
2. Правый узел больше своего родителя.
3. Левое и правое поддеревья должны быть деревьями двоичного поиска.

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

Похожие: Библиотеки Data Science для Python, которые должен использовать каждый специалист по анализу данных

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

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

1. Операция поиска

Поиск позволяет нам найти определенное значение, присутствующее в дереве. Мы можем использовать два типа поиска: поиск по ширине (BFS) и поиск по глубине (DFS). Поиск по ширине – это алгоритм поиска, который начинается с корневого узла и проходит по горизонтали, из стороны в сторону, пока не будет найдена цель. Каждый узел посещается один раз во время этого поиска

Глубокий поиск, с другой стороны, обходит дерево по вертикали— начиная с корневого узла и работая вниз по одной ветви. Если цель найдена, операция завершается. Но если нет, то выполняется поиск в других узлах

2. Операция вставки

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

• Случай 1: Когда узла не существует Вставляемый узел становится корневым узлом.

• Случай 2: нет дочерних узлов. В этом случае узел сравнивается с корневым узлом. Если он больше, он станет правым дочерним узлом; в противном случае он станет левым дочерним узлом.

• Случай 3: Когда корень и его дочерние узлы присутствуют. Новый узел будет сравниваться с каждым узлом на его пути, чтобы определить, какой узел он посетит следующим. Если узел больше, чем корневой узел, он будет перемещаться вниз по правому поддереву или, наоборот, по левому. Аналогично, сравнения производятся на каждом уровне, чтобы определить, пойдет ли он направо или налево, пока не прибудет в пункт назначения.

3. Операция удаления

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

• Случай 1: удаление узла-листа. Узел-лист – это узел без дочерних узлов. Его легче всего удалить, так как он не влияет на другие узлы; мы просто обходим дерево, пока не достигнем его, и удаляем его.

• Случай 2: Удаление узла с одним дочерним узлом Удаление родительского узла с одним узлом приведет к тому, что дочерний узел займет его позицию, а все последующие узлы переместятся на уровень выше. Структура поддеревьев не изменится.

• Пример 3: Удаление узла с двумя детьми. Когда нам нужно удалить узел с двумя детьми, мы должны сначала найти последующий узел, который может занять его место. Два узла могут заменить удаленный узел: последовательный или предшественник. Преемник по порядку – это крайний левый ребенок правого поддерева, а предшественник по порядку – крайний правый ребенок левого поддерева. Мы копируем содержимое узла-преемника/предшественника в узел и удаляем порядкового преемника/предшественника.

Похожие: Как строить структуры данных с помощью классов JavaScript ES6

Как пройти по двоичному дереву поиска

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

• In-Order Traversal: При обходе в порядке возрастания получается карта в порядке возрастания. При этом методе мы начинаем с левого поддерева и продолжаем до корня и правого поддерева.

• Pre-Order Traversal: В этом методе сначала посещается корневой узел, затем левое поддерево и правое поддерево.

• Post-Order Traversal: Этот обход предполагает посещение корневого узла последним. Мы начинаем с левого поддерева, затем с правого поддерева, а затем с корневого узла.

Применение в реальном мире

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

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

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

Двоичные деревья поиска: Идеальная отправная точка

Одним из основных способов оценки компетентности инженера является знание и применение им структур данных. Структуры данных полезны и могут помочь создать более эффективную систему. Двоичные деревья поиска – это отличное введение в структуры данных для любого начинающего разработчика