Реализация пользовательского двоичного дерева поиска в Go

Важно уделить внимание реализации бинарного дерева на Golang и использованию нескольких функций для добавления или удаления узлов. Узел в Go может быть представлен как структура:

Эта структура хранит значения int, но она может быть изменена для хранения других типов данных. Левое и правое поле в структуре указывают на другие узлы дерева.

Вставка узла в дерево

Это довольно просто: мы постоянно сравниваем значение вставляемого узла с узлами в двоичном дереве. Если значение вставляемых данных меньше, чем сравниваемый с ним узел, и если левый потомок  равен нулю, мы можем вставить новый узел как левый. Иначе мы сравниваем его с левым поддеревом и повторяем процесс.

Каждая из этих функций принимает параметр.

Извлечение минимума

Эта функция рекурсивно находит минимальный элемент дерева:

Мы проверяем значения левых потомков, пока не достигнем nil.

Извлечение максимума

Эта функция находит максимальный элемент дерева. Подход тот же, но до достижения nil обходятся все правые потомки:

Обход бинарного дерева

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

С реализацией кода ты можешь ознакомиться по ссылке.

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

Правильное двоичное дерево будет иметь значение левого потомка меньше корня, а значение правого потомка больше корня.

С полной версией статьи ты можешь ознакомиться по ссылке.