Разница между двоичным деревом и двоичным деревом поиска

Что такое бинарное дерево?

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

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

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

Бинарное дерево поиска - это тип структуры данных бинарного дерева, в которой узлы упорядочены по порядку, поэтому также называется «упорядоченным бинарным деревом». Это структура данных на основе узлов, которая обеспечивает эффективный и быстрый способ сортировки, поиска и поиска данных. Для каждого узла элементы в левом поддереве должны быть меньше или равны ключу в его родительском узле (LP). Там не должно быть дубликатов ключей. Проще говоря, это особый вид структуры данных бинарного дерева, которая эффективно хранит и управляет элементами в памяти.

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

Разница между двоичным деревом и двоичным деревом поиска

1. Определение двоичного дерева и дерева двоичного поиска - Двоичное дерево - это иерархическая структура данных, в которой дочерний элемент может иметь ноль, один или максимум два дочерних узла; каждый узел содержит левый указатель, правый указатель и элемент данных. Там нет конкретного порядка, как узлы должны быть организованы в дереве. Двоичное дерево поиска, с другой стороны, является упорядоченным двоичным деревом, в котором существует относительный порядок организации узлов..
2. Структура из Двоичное дерево и двоичное дерево поиска- Самый верхний узел в дереве представляет корневой указатель в двоичном дереве, а левый и правый указатели представляют меньшие деревья с обеих сторон. Это специализированная форма дерева, которая представляет данные в древовидной структуре. Двоичное дерево поиска, с другой стороны, представляет собой тип двоичного дерева, в котором все узлы в левом поддереве меньше или равны значению корневого узла, а узлы правого поддерева больше или равны значению корневого узла.
3. операция из Двоичное дерево и двоичное дерево поиска- Двоичное дерево может быть любым, у которого есть два дочерних элемента и один родительский элемент. Обычные операции, которые могут быть выполнены с двоичным деревом, - это вставка, удаление и обход. Двоичные деревья поиска - это больше отсортированные двоичные деревья, которые позволяют быстро и эффективно искать, вставлять и удалять элементы. В отличие от бинарных деревьев, бинарные поисковые деревья сохраняют свои ключи отсортированными, поэтому поиск обычно реализует бинарный поиск для операций.
4. Типы из Двоичное дерево и двоичное дерево поиска- Существуют различные типы бинарных деревьев, среди которых «Полное двоичное дерево», «Полное двоичное дерево», «Совершенное двоичное дерево» и «Расширенное двоичное дерево». Некоторые общие типы деревьев бинарного поиска включают в себя T-деревья, AVL-деревья, Splay-деревья, Tango-деревья, красно-черные деревья и т. Д..

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

Сводка двоичного дерева и дерева двоичного поиска

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