Деревья являются одним из самых пугающих вещей в разработке. Еще хуже дело обстоит, когда программист встречает задачу, связанную с деревьями, во время собеседования. В этой статье я постараюсь минимизировать боль, связанную с этой темой.
Деревья бывают разные. Мы рассмотрим двоичное сбалансированное.
В данной статье мы рассмотрим наиболее популярные — двоичные сбалансированные (красно-черные) деревья.
Пример бинарного дерева. У каждого листка может быть не более двух наследников.
Основные понятия.
Рассматривая бинарные деревья нужно знать следующие понятия:
- Node - он же узел. Это элемент дерева, содержащий какое-то значение, которое может быть любым, от примитива (например, числа) до объекта (например, пользователя).
- Edge или ребро. Ссылка, соединяющая один узел с другим или указывающая на пустое значение (null).
- Root Node. Верхний узел дерева, от которого начинается вся структура.
- Leaf - Узел, не имеющий наследников, то есть находящийся в самом низу иерархии.
- Высота дерева - Количество "уровней", от корня до самого нижнего узла.
Несбалансированные деревья могут выродиться в связный список.
Несбалансированные деревья — это деревья, у которых высота левой и правой веток может значительно отличаться. В худшем случае все узлы могут располагаться по одной стороне. В этом случае дерево деградирует до связного списка.
деградированное дерево вырожденное в связанный список.
Сбалансированные деревья.
Сбалансированные (например красно-черные) при каждом добавлении нового узла проверяют, является ли дерево "несбалансированным". Если условие истино то дерево делает "разворот" свои узлов.
Пример красно черного сбалансированного дерева. Именно такое используется в TreeMap
Сбалансированные деревья никогда не вырождаются в связанные списки. В J ava джаве деревья представлены коллекцие TreeMap и TreeSet (который инкапсулирует TreeMap внутри себя).
Как могут быть представлены деревья на уровне кода.
Если мы не используем готовые решения вроде TreeMap то простейшее дерево может быть представлено в виде следующего класса:
Простейший узел. По большому счету это единственный важный момент.
Итого что мы имеем:
- String data это то значение которое хранит узел. Это может быть любым объектом - в нашем случае просто строка.
- Node left - ссылка на левого наследника.
- Node right - ссылка на правого.
Используя Node класс создадим дерево
Поочередно инициализируем наше дерево с 7 узлами
Изобразим полученное дерево:
Итерация по дереву - один из самых важных навыков для решения задач.
Большинство (если не все) задач, связанных с деревьями требуют итерации или обхода узлов. Чаще всего, умея обходить дерево, вы решаете львиную часть проблемы. В данной статье мы рассмотрим лишь 1 вариант итерации, я напишу отдельные статьи чтобы рассмотреть другие подходы.
Используем рекурсию для итерации и распечатки всех элементов.
Каждый раз когда вам прилетела задача по деревьям, помните - скорее всего в основании решения будет рекурсия (это не всегда так, но довольно часто). Те у вас будет функция которая будет вызывать сама себя. Для распечатки дерева напишем рекурсию которая обходит все элементы начиная с левого наследника:
Код вроде простой но не стоит его недооценивать. Давайте проговорим этапы:
- Распечатываем значение узла
- Идем к левому наследнику и повторяем действие (те опять распечатываем и идем влево)
- после того мы обошли все левые и уткнулись в null мы "возвращаемся" на уровень который находится наверху от нижнего левого и идем в правый наследник
- зайдя в правый распечатывем и идем влево повторяя шаги 2-3.
Все это звучит странно проще будет изобразить:
Это лишь первая статья но в ней мы ознакомились с основными понятиями. Также мы обошли дерево, используя рекурсию. Это один из самых популярных подходов в решениии подобных задач. В следующей части мы рассмотрим альтернативные варианты работы с деревьями.
Кому интересна разработка приглашаю в мой телеграм канал