Поиск по сайту:

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Удаление операции

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

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

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

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

Связано: Как создавать структуры данных с помощью классов JavaScript ES6

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

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

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

  • Обход по предварительному заказу. В этом методе сначала посещается корневой узел, затем левое поддерево и правое поддерево.

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

Реальные приложения

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

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

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

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

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

Статьи по данной тематике: