Binary Tree

В этой теме мы узнаем:

• что такое Binary Tree и зачем нужны бинарные деревья;
• как реализовать пользовательское двоичное дерево поиска в Go;
• каковы основные функциональные возможности Binary Tree (вставка узла, обход дерева, получение минимального и максимального элемента).

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

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

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

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

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

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

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

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

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

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