Прежде чем мы поговорим о двоичном дереве поиска, давайте рассмотрим некоторые основные свойства структуры данных Tree.
Что такое дерево?
Хм, название Tree происходит от способа структурирования данных, то есть оно выглядит как перевернутое дерево. Дерево - это набор узлов. И эти узлы соединены ребрами. И каждый узел имеет значение, называемое ключ, и ссылки на дочерние узлы.
Первый узел дерева называется корнем. А узлы без дочерних узлов называются листьями.
Что такое двоичное дерево?
Как следует из названия, двоичное дерево - это древовидная структура данных, в которой каждый узел имеет не более двух дочерних элементов, которые называются левыми дочерний и правый дочерний.
Что такое двоичное дерево поиска?
Дерево двоичного поиска (BST) также называется упорядоченным или отсортированным двоичным деревом. По сути, BST может быть определен следующими условиями:
- Это дерево
- Бинарный
- Имеет свойство двоичного поиска
Я объясню, о чем идет речь в последнем пункте. Последний пункт означает, что:
- ключ левого дочернего элемента узла будет меньше, чем ключ узла.
- ключ правого дочернего элемента узла будет больше, чем ключ узла.
И это все. Теперь проверьте приведенный выше рисунок и посмотрите, соответствует ли он условиям для BST.
Итак, в этой части мы познакомились с деревьями двоичного поиска. Далее мы реализуем BST в коде.
:)
Я начал эту публикацию, чтобы помочь мне лучше понять вещи, поделившись ею с другими. Так что, если у вас есть предложения, пишите в комментариях. Спасибо за внимание.
