«Дерево», вероятно, является одной из наиболее часто используемых структур данных. Деревья помогают представлять данные, которые имеют древовидную структуру или форму. На самом деле существует множество различных типов деревьев, каждое из которых используется для своей цели. В этом блоге я собираюсь рассказать о структуре данных двоичного дерева поиска (также называемой BST).
Двоичное дерево — это иерархическая структура данных, в которой каждый узел имеет значение и ссылку на левого и правого дочерних элементов. Узел без родителя называется корнем, узлы без потомков называются листьями. Узел с родительским и дочерним элементами называется внутренними узлами. Каждый узел в бинарном дереве поиска подчиняется следующему правилу: левый дочерний узел меньше корня этого узла, тогда как правый больше. Соответственно, бинарное дерево поиска очень легко преобразовать в массив или найти искомое число. Допустим, у нас есть следующее дерево:
Поиск наименьшего значения невероятно прост — это всегда самый левый узел, т. е. начиная сверху, на каждом разветвлении мы всегда выбираем левого потомка. Как только мы видим, что детей больше нет, значит, мы достигли наименьшего значения.
Это та же самая концепция с самым большим значением — это всегда значение, расположенное дальше всего справа.
Поиск элемента выполняется следующим образом:
1) Как всегда, мы начинаем с корневого узла.
2) Проверяем, соответствует ли значение узла тому, что мы ищем. Если да, вернитесь.
3) Если нет, мы проверяем, больше или меньше значение. Перейти к соответствующему дочернему элементу (ветке).
4) Если списка нет, значит, нет элемента. Если есть список, повторите шаг 2.
Пустое дерево поиска не имеет членов. Глубина узла равна количеству ребер от корня до узла. Высота узла равна количеству ребер между этими узлами и его самым дальним листом. Высота всего дерева равна высоте корня (например, высота описанного выше BST равна 2). Если бинарное дерево поиска состоит только из корня, его высота равна нулю.
Сбалансированное бинарное дерево поиска — это дерево логарифмической высоты. В сбалансированном дереве поиска вставка и удаление узла занимают логарифмическое время. Кроме того, если это несбалансированное дерево поиска отсортированных значений, так что все узлы расположены линейно, то поиск, удаление/удаление или вставка элемента будут занимать линейное время. Поэтому балансировка бинарного дерева поиска очень важна.
Пустое дерево поиска не имеет членов. Глубина узла равна количеству ребер от корня до узла. Высота узла равна количеству ребер между этими узлами и его самым дальним листом. Высота всего дерева равна высоте корня. Если бинарное дерево поиска состоит только из корня, его высота равна нулю.
Сбалансированное бинарное дерево поиска — это дерево логарифмической высоты. В сбалансированном дереве поиска вставка и удаление узла занимают логарифмическое время. Кроме того, если это несбалансированное дерево поиска отсортированных значений, в котором все узлы расположены линейно, то поиск, удаление/удаление или вставка элемента будут занимать линейное время. Поэтому балансировка бинарного дерева поиска очень важна.
