Ключевая разница - двоичное дерево против двоичного дерева поиска
Структура данных - это систематический способ организации данных для их эффективного использования. Организация данных с использованием структуры данных должна сократить время выполнения или время выполнения. Также структура данных должна требовать минимального объема памяти. Иногда данные могут быть организованы в виде древовидной структуры. Дерево представляет собой узел, соединенный ребрами. Самый верхний узел является корнем. Каждый узел может иметь максимум два узла. Они известны как дочерние узлы. Узел слева от родительского узла является левым дочерним узлом, а узел справа от родительского узла является правым узлом. Двоичное дерево и двоичное дерево поиска - это две древовидные структуры данных. Двоичное дерево - это тип структуры данных, в которой каждый родительский узел может иметь не более двух дочерних узлов. Двоичное дерево поиска - это бинарное дерево, в котором левый дочерний элемент содержит только узлы со значениями, меньшими или равными родительскому узлу, а правый дочерний элемент содержит только узлы со значениями, превышающими значение родительского узла. Это ключевое отличие. В отличие от таких структур данных, как массивы, бинарное дерево и бинарное дерево поиска не имеют верхнего предела хранения данных.
Что такое бинарное дерево?
При размещении данных в древовидной структуре узел в верхней части дерева называется корневым узлом. У всего дерева может быть только один корень. Любой узел, кроме корневого узла, имеет одно ребро, направленное вверх к узлу. Он называется родительским узлом. Узел ниже родительского кода называется его дочерним узлом. Каждый родительский узел может иметь максимум два дочерних узла. Они называются левым дочерним узлом и правым дочерним узлом. Узел без дочерних узлов называется листовым узлом. Не существует определенного способа упорядочивания данных в двоичном дереве. Существует путь от корневого узла к каждому узлу.
Рисунок 01: Пример бинарного дерева
Выше приведен пример бинарного дерева. Элемент 2 в верхней части дерева является корнем. Каждый узел имеет максимум два узла. Если дерево содержит какие-либо петли или если один узел содержит более двух узлов, его нельзя классифицировать как бинарное дерево. Чтобы перейти от одного узла к другому, всегда есть один путь. Дочерними узлами корневого узла 2 являются 7 и 5. Также возможно, что узел не имеет узлов. Но любой узел не может иметь более двух узлов. Правый элемент корня равен 5. Этот элемент 5 является родительским узлом для дочернего узла 9. Узлы 4 и 11 не имеют дочерних элементов. Следовательно, они являются листовыми узлами.
Двоичное дерево используется для хранения данных в иерархическом порядке. Она похожа на файловую структуру компьютера. Структура данных, такая как массив, может хранить определенное количество данных. Но в бинарном дереве нет верхнего предела количества узлов.
Что такое двоичное дерево поиска?
Двоичное дерево поиска - это структура данных двоичного дерева. Подобно бинарному дереву, бинарное дерево поиска также может иметь два узла. Любой узел, кроме корневого узла, имеет одно ребро, направленное вверх к узлу. Он называется родительским узлом. Узел ниже данного, соединенный ребром вниз, называется его дочерним узлом. Узел без дочерних узлов называется листовым узлом. Каждый родительский узел может иметь максимум два узла. Есть дочерние узлы, ссылающиеся на левый дочерний узел и правый дочерний узел. Самый верхний элемент называется корневым узлом. Левый дочерний элемент содержит только узлы со значениями меньше или равными родительскому узлу. Правый дочерний элемент содержит только узлы, значения которых больше или равны родительскому узлу.
Рисунок 02: Пример двоичного дерева поиска
Элемент 8 является самым верхним элементом. Следовательно, это корневой узел. Если 3 - родительский узел, то 1 и 6 - дочерние узлы. 1 - это левый дочерний узел, а 6 - правый дочерний узел. Левый дочерний узел содержит значения, меньшие или равные родительскому узлу. Когда 3 является родительским узлом, в левой части должен быть элемент, который меньше или равен 3. В этом примере это 1. Правый дочерний элемент содержит только узлы со значениями, превышающими родительский узел. Когда 3 является родительским узлом, правый дочерний узел должен иметь большее значение, чем 3. В этом примере это 6. Точно так же существует определенный порядок расположения каждого элемента данных в двоичном дереве поиска. Эта структура данных обеспечивает эффективный способ сортировки, извлечения и поиска данных.
Каковы сходства между двоичным деревом и двоичным деревом поиска?
- И двоичное дерево, и двоичное дерево поиска являются иерархическими структурами данных.
- И двоичное дерево, и двоичное дерево поиска имеют корень.
- И двоичное дерево, и двоичное дерево поиска могут иметь не более двух дочерних узлов.
В чем разница между двоичным деревом и двоичным деревом поиска?
Двоичное дерево против двоичного дерева поиска |
|
| Двоичное дерево - это тип структуры данных, в которой каждый родительский узел может иметь максимум два дочерних узла. | Двоичное дерево поиска - это бинарное дерево, в котором левый дочерний элемент содержит только узлы со значениями, меньшими или равными родительскому узлу, а правый дочерний элемент содержит только узлы со значениями, превышающими родительский узел. |
| Порядок расположения данных | |
| Двоичное дерево не имеет определенного порядка расположения элементов данных. | Двоичное дерево поиска имеет определенный порядок расположения элементов данных. |
| Использование | |
| Двоичное дерево используется для эффективного поиска данных и информации в древовидной структуре. | Двоичное дерево поиска используется для вставки, удаления и поиска данных. |
Резюме - бинарное дерево против бинарного дерева поиска
Структура данных - это способ организации данных. Иногда данные могут быть организованы в виде древовидной структуры. Два из них - бинарное дерево и бинарное дерево поиска. В этой статье обсуждалась разница между бинарным деревом и бинарным деревом поиска. Двоичное дерево - это тип структуры данных, в которой каждый родительский узел может иметь не более двух дочерних узлов. Двоичное дерево поиска - это бинарное дерево, в котором левый дочерний элемент содержит только узлы со значениями, меньшими или равными родительскому узлу, а правый дочерний элемент содержит только узлы со значениями, превышающими родительский узел.
Загрузить PDF-файл Binary Tree vs Binary Search Tree
Вы можете загрузить PDF-версию этой статьи и использовать ее в автономном режиме в соответствии с примечанием к цитированию. Загрузите PDF-версию здесь: Разница между двоичным деревом и двоичным деревом поиска
