Бинарное дерево на Go для новичка

Введение

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

Вставка узла.
Обход дерева.
Получение минимального и максимального элемента.

Что такое дерево?

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

Дерево бинарного поиска

Примечание: бинарное дерево может иметь любой порядок узлов, но двоичное дерево поиска следует определенному порядку, упорядочивая свои узлы, как описано в следующем разделе.

Зачем нужны бинарные деревья?

Представьте себе, что вы находите элемент в массиве. Временная сложность с линейной структурой, такой как массив, — O(n), где n увеличивается по мере увеличения числа элементов для поиска.

Предположим, что данные представлены в виде древовидной структуры. Тогда число шагов, необходимых для нахождения значения, уменьшается более чем наполовину: логарифмическая временная сложность O(logN). Это происходит потому, что всякий раз, когда значение вставляется в двоичное дерево поиска, добавление узла упорядоченно: значение левого дочернего элемента меньше значения родительского, а значение правого узла больше значения родительского узла.

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

Терминология

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

Дерево бинарного поиска на Go

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

TreeNode struct {
 val   int
 left  *TreeNode
 right *TreeNode
}

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

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

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

(t *TreeNode) Insert(value int) error {
 if t == nil {
 return errors.New("Tree is nil")
 }

 if t.val == value {
 return errors.New("This node value already exists")
 }

 if t.val > value {
 if t.left == nil {
 t.left = &TreeNode{val: value}
 return nil
 }
 return t.left.Insert(value)
 }

 if t.val < value {
 if t.right == nil {
 t.right = &TreeNode{val: value}
 return nil
 }
 return t.right.Insert(value)
 }
 return nil
}

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

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

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

(t *TreeNode) FindMin() int {
 if t.left == nil {
 return t.val
 }
 return t.left.FindMin()
}

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

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

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

(t *TreeNode) FindMax() int {
 if t.right == nil {
 return t.val
 }
 return t.right.FindMax()
}

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

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

func (t *TreeNode) PrintInorder() {
 if t == nil {
 return
 }

 t.left.PrintInorder()
 fmt.Print(t.val)
 t.right.PrintInorder()
}

Заключение

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

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

Полный код с большим количеством других функций доступен по адресу https://github.com/puneeth8994/binary-tree-go-impl.

Перевод статьи Puneeth S: Binary Search Trees in Go

Поделиться статьей:

Вернуться к статьям