Как следует из названия, двоичное дерево поиска ничем не отличается от деревьев на тротуаре. У каждого дерева есть ствол с множеством других ветвей, которые отходят от него и затем раскалываются. Точно так же дерево двоичного поиска имеет «ствол» и несколько ветвей, выходящих из него.
Теперь, когда мы знаем, как выглядит двоичное дерево поиска, давайте обсудим терминологию, которую используют компьютерные ученые, чтобы говорить о различных частях этого изменяемого дерева. Каждый элемент в дереве называется узлом (кружки относятся к диаграмме ниже). BST имеет корневой узел, левое поддерево и правое поддерево. Левое и правое поддеревья могут содержать или не содержать данные. Узлы, которые имеют одного и того же родителя, называются одноуровневыми. Узел без дочерних узлов называется листом. Подобно реальным деревьям, у BST есть листья, которые представляют собой узлы, не имеющие левого или правого поддеревья, которые находятся в конце каждой ветви. Для большей ясности, родительский корень BST ниже - 8, а листья - это узлы 1, 4, 7 и 13.
Что делает бинарные деревья поиска уникальными и заслуживающими упоминания? Их очень важная характеристика, которая делает поиск определенных элементов, которые он содержит, очень легким и очень быстрым, делает их важной темой. Дерево организовано таким образом, что значение узла больше, чем все его дочерние элементы в левом поддереве, и меньше, чем все значения в его последнем правом поддереве. Мы легко можем понять, что при создании двоичного дерева поиска рекурсия играет важную роль в создании и организации значений каждого узла. Рекурсивное определение применяется к каждому левому и правому поддереву.
Два метода, которые обычно встречаются как часть класса BST, - это вставка и поиск. Чтобы вставить новый узел со значением 5, нам нужно сохранить свойство, и для этого новый узел будет размещен как левый дочерний узел 6, а узел 5 будет иметь 4 как его новый левый дочерний элемент. Этот уникальный метод вставки упрощает поиск элементов с определенным значением, хранящимся в произвольном узле. Например, если мы ищем 7 в двоичном дереве, алгоритм поиска BST выполняет следующие очень конкретные шаги: начинается с корня BST, который в данном случае равен 8, поскольку 7 меньше 8, идет влево. поддерево. 3 сравнивается с 7, и алгоритм замечает, что 7 больше 3, поэтому он переходит к правому поддереву. Правый узел поддерева имеет значение 6 в качестве значения узла, а 7 все еще больше 6, поэтому алгоритм переходит к правому поддереву, и, к счастью, именно здесь алгоритм прекращает дальнейший поиск, потому что узел, содержащий 7, был нашел. Это примеры кода, написанные на языке программирования Python для поиска и вставки в дерево двоичного поиска.
Подводя итог, можно сказать, что деревья двоичного поиска - очень полезные структуры данных при работе с любыми типами данных. Во-первых, они представляют собой иерархии в массивной структуре данных. Во-вторых, они обеспечивают организованный способ вставки и поиска. Самое главное - взаимосвязь между данными, которые хранятся.
Это все для этого сообщения в блоге. Получите код и увидимся на следующей неделе!
