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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Вставить операцию

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

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

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

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

3. Удалить операцию

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15 методов массива JavaScript, которые вы должны освоить сегодня

Хотите разобраться в массивах JavaScript, но не можете с ними разобраться? Ознакомьтесь с нашими примерами массивов JavaScript для руководства.

Читать далее

Об авторе