Все, что вам нужно знать о древовидных структурах данных

Автор оригинала: TK.

Когда вы впервые учитесь программировать, обычно массивы изучаются как “основная структура данных”.”

В конце концов, вы также узнаете о хэш-таблицах . Если вы хотите получить степень в области компьютерных наук, вы должны пройти курс по структуре данных. Вы также узнаете о связанных списках , очередях и стеках . Эти структуры данных называются “линейными” структурами данных, потому что все они имеют логическое начало и логический конец.

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

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

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

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

• Примеры деревьев

• Его терминология и как он работает

• Как реализовать древовидные структуры в коде.

Давайте начнем это учебное путешествие.

Определение

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

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

Давайте погрузимся в примеры из реальной жизни!

Что я имею в виду, когда говорю иерархически?

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

Приведенный выше рисунок – это мое генеалогическое древо. Тосико, Акикадзу, Хитоми, и Такеми мои бабушка и дедушка.

Тосиаки и Джулиана мои родители.

ТК, Юджи, Бруно и Кайо – дети моих родителей (меня и моих братьев).

Структура организации-это еще один пример иерархии.

В HTML объектная модель документа (DOM) работает как дерево.

Тег HTML содержит другие теги. У нас есть head tag и body tag. Эти теги содержат определенные элементы. Тег head имеет теги meta и title . Тег body содержит элементы, отображаемые в пользовательском интерфейсе, например h1 , a , li и т. Д.

Техническое определение

дерево – это набор сущностей, называемых узлами . Узлы соединены ребрами . Каждый узел содержит значение или данные , и он может иметь или не иметь дочерний узел .

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

Все Узлы дерева соединены ссылками, называемыми ребрами . Это важная часть деревьев , потому что она управляет отношениями между узлами .

Листья являются последними узлами на дереве . Они являются узлами без детей. Как и настоящие деревья, у нас есть корень , ветви и, наконец, листья .

Другими важными понятиями для понимания являются высота и глубина .

Высота дерева - это длина самого длинного пути к листу .

Глубина узла - это длина пути к его корню .

Терминологическое резюме

• **Корень ** – это самый верхний узел дерева

• **Ребро ** – это связь между двумя узлами

• **Дочерний ** – это узел , который имеет родительский узел

• **Родитель ** – это узел , который имеет ребро к дочернему узлу

• **Лист ** – это узел , у которого нет дочернего узла в дереве

• **Высота ** – это длина самого длинного пути к листу

• **Глубина ** – это длина пути к его корню

Бинарные деревья

Теперь мы обсудим конкретный тип дерева . Мы называем его двоичным деревом .

“В информатике двоичное дерево — это древовидная структура данных, в которой каждый узел имеет не более двух дочерних элементов, которые называются левым дочерним элементом и правым дочерним элементом”. – Википедия

Итак, давайте рассмотрим пример двоичного дерева .

Давайте закодируем двоичное дерево

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

Как мы реализуем простое двоичное дерево , которое инициализируется этими тремя свойствами?

Давайте посмотрим.

class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left_child = None
        self.right_child = None

Вот он. Наш двоичное дерево класс.

Когда мы создаем экземпляр объекта, мы передаем значение | (данные узла) в качестве параметра. Посмотрите на left_child и right_child . Оба они имеют значение Нет .

Почему?

Потому что , когда мы создаем наш узел , у него нет детей. У нас есть только данные узла .

Давайте проверим это:

tree = BinaryTree('a')
print(tree.value) # a
print(tree.left_child) # None
print(tree.right_child) # None

Вот и все.

Мы можем передать строку ‘|/a ' в качестве значения в наш узел двоичного дерева . Если мы напечатаем значение , left_child и right_child , мы сможем увидеть значения.

Давайте перейдем к вставной части. Что нам нужно здесь делать?

Мы реализуем метод вставки нового узла в справа и слева .

Вот правила:

• Если у текущего узла нет левого дочернего элемента , мы просто создаем новый узел и устанавливаем его в left_child текущего узла .

• Если у него есть левый дочерний элемент , мы создаем новый узел и помещаем его в текущее левое дочернее место. Выделите этот левый дочерний узел новому узлу левый дочерний узел .

Давайте нарисуем его.

Вот код:

def insert_left(self, value):
    if self.left_child == None:
        self.left_child = BinaryTree(value)
    else:
        new_node = BinaryTree(value)
        new_node.left_child = self.left_child
        self.left_child = new_node

Опять же, если у текущего узла нет left child , мы просто создаем новый узел и устанавливаем его в left_child текущего узла . Или же мы создаем новый узел и помещаем его в текущее левое дочернее место. Выделите этот левый дочерний узел новому узлу левый дочерний узел .

И мы делаем то же самое, чтобы вставить правый дочерний узел .

def insert_right(self, value):
    if self.right_child == None:
        self.right_child = BinaryTree(value)
    else:
        new_node = BinaryTree(value)
        new_node.right_child = self.right_child
        self.right_child = new_node

Сделано.

Но не совсем. Нам все еще нужно это проверить.

Давайте построим следующее три :

Чтобы подвести итог иллюстрации этого дерева:

• / | узел будет корнем нашего двоичного дерева a

• левый дочерний is b |/узел a

• правый дочерний is c |/узел b правый дочерний элемент

• является d узлом ( b узел не имеет левого дочернего элемента ) c левый дочерний

• is e |/узел c правый дочерний is

• f |/узел оба e и f

• узлы не имеют потомков

Итак, вот код для дерева :

a_node = BinaryTree('a')
a_node.insert_left('b')
a_node.insert_right('c')

b_node = a_node.left_child
b_node.insert_right('d')

c_node = a_node.right_child
c_node.insert_left('e')
c_node.insert_right('f')

d_node = b_node.right_child
e_node = c_node.left_child
f_node = c_node.right_child

print(a_node.value) # a
print(b_node.value) # b
print(c_node.value) # c
print(d_node.value) # d
print(e_node.value) # e
print(f_node.value) # f

Вставка выполнена.

Теперь мы должны подумать о дереве обходе.

У нас есть два варианта здесь: Поиск по глубине (DFS) и Поиск по ширине (BFS) .

• Википедия

• Википедия

Итак, давайте погрузимся в каждый тип обхода дерева.

Поиск по глубине (DFS)

DFS исследует путь до самого листа, прежде чем вернуться назад и исследовать другой путь. Давайте рассмотрим пример с этим типом обхода.

Результатом для этого алгоритма будет 1-2-3-4-5-6-7.

Почему?

Давайте разберем это.

1. Перейдите к левому ребенку (2). Распечатайте его.

2. Затем перейдите к левому ребенку (3). Распечатайте его. (У этого узла нет детей)

3. Вернитесь назад и перейдите к правому ребенку (4). Распечатайте его. (У этого узла нет детей)

4. Вернитесь к корневому | узлу и перейдите к правому дочернему (5). Распечатайте его. Перейдите к

5. левому ребенку (6). Распечатайте его. (У этого узла нет детей) Вернитесь назад и перейдите к

6. правому ребенку (7). Распечатайте его. (У этого узла нет детей) Сделано.

Когда мы углубляемся в лист и возвращаемся назад, это называется алгоритмом DFS .

Теперь, когда мы знакомы с этим алгоритмом обхода, мы обсудим типы DFS : pre-order , in-order и post-order .

Предварительный заказ

Именно это мы и сделали в приведенном выше примере.

def pre_order(self):
    print(self.value)

    if self.left_child:
        self.left_child.pre_order()

    if self.right_child:
        self.right_child.pre_order()

По порядку

Результатом алгоритма по порядку для этого дерева примера является 3-2-4-1-6-5-7.

Левая первая, средняя вторая и правая последняя.

Теперь давайте закодируем его.

def in_order(self):
    if self.left_child:
        self.left_child.in_order()

    print(self.value)

    if self.right_child:
        self.right_child.in_order()

Пост-заказ

Результатом алгоритма post order для этого дерева примера является 3-4-2-6-7-5-1.

Сначала налево, потом направо и на Ближний Восток.

Давайте закодируем это.

def post_order(self):
    if self.left_child:
        self.left_child.post_order()

    if self.right_child:
        self.right_child.post_order()

    print(self.value)

Поиск по ширине (BFS)

Алгоритм BFS пересекает дерево уровень за уровнем и глубину за глубиной.

Вот пример, который помогает лучше объяснить этот алгоритм:

Итак, мы проходим уровень за уровнем. В этом примере результат 1-2-5-3-4-6-7.

• Уровень/Глубина 0: только узел со значением 1

• Уровень/Глубина 1: узлы со значениями 2 и 5

• Уровень/Глубина 2: узлы со значениями 3, 4, 6 и 7

Теперь давайте закодируем его.

def bfs(self):
    queue = Queue()
    queue.put(self)

    while not queue.empty():
        current_node = queue.get()
        print(current_node.value)

        if current_node.left_child:
            queue.put(current_node.left_child)

        if current_node.right_child:
            queue.put(current_node.right_child)

Для реализации алгоритма BFS мы используем структуру данных queue .

Как это работает?

Вот объяснение.

Бинарное дерево поиска

“Двоичное дерево поиска иногда называют упорядоченными или отсортированными двоичными деревьями, и оно сохраняет свои значения в отсортированном порядке, так что поиск и другие операции могут использовать принцип двоичного поиска” — Википедия

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

Вот разбивка приведенной выше иллюстрации:

• **A **перевернуто. Поддерево 7-5-8-6 должно быть справа, а поддерево 2-1-3-слева. **B ** - это единственно правильный вариант. Он удовлетворяет свойству Бинарного дерева поиска

• . **C **имеет одну проблему: узел

• со значением 4. Он должен быть слева от root , потому что он меньше 5.

Давайте закодируем Двоичное дерево поиска!

Теперь пришло время кодировать!

Что мы здесь увидим? Мы будем вставлять новые узлы, искать значение, удалять узлы и баланс дерева /.

Давайте начнем.

Вставка: добавление новых узлов в наше дерево

Представьте, что у нас есть пустое дерево , и мы хотим добавить новые узлы со следующими значениями в этом порядке: 50, 76, 21, 4, 32, 100, 64, 52.

Первое, что нам нужно знать, это то, является ли 50 корнем нашего дерева.

Теперь мы можем начать вставку node by node .

• 76 больше 50, поэтому вставьте 76 с правой стороны.

• 21 меньше 50, поэтому вставьте 21 с левой стороны.

• 4 меньше 50. Узел со значением 50 имеет левый дочерний элемент 21. Поскольку 4 меньше 21, вставьте его в левую часть этого узла .

• 32 меньше, чем 50. Узел со значением 50 имеет левый дочерний элемент 21. Поскольку 32 больше 21, вставьте 32 с правой стороны этого узла .

• 100 больше, чем 50. Узел со значением 50 имеет правого потомка 76. Поскольку 100 больше 76, вставьте 100 с правой стороны этого узла .

• 64 больше, чем 50. Узел со значением 50 имеет правого потомка 76. Поскольку 64 меньше 76, вставьте 64 с левой стороны этого узла .

• 52 больше, чем 50. Узел со значением 50 имеет правого потомка 76. Поскольку 52 меньше 76, узел со значением 76 имеет левый дочерний элемент 64. 52 меньше 64, поэтому вставьте 54 с левой стороны этого узла .

Вы заметили здесь закономерность?

Давайте разберем это.

Теперь давайте закодируем его.

class BinarySearchTree:
    def __init__(self, value):
        self.value = value
        self.left_child = None
        self.right_child = None

    def insert_node(self, value):
        if value <= self.value and self.left_child:
            self.left_child.insert_node(value)
        elif value <= self.value:
            self.left_child = BinarySearchTree(value)
        elif value > self.value and self.right_child:
            self.right_child.insert_node(value)
        else:
            self.right_child = BinarySearchTree(value)

Это кажется очень простым.

Мощной частью этого алгоритма является часть рекурсии, которая находится в строке 9 и строке 13. Обе строки кода вызывают метод insert_node и используют его для своих left и right детей соответственно. Линии 11 и 15 это те, которые делают вставку для каждого ребенка .

Давайте поищем значение узла… Или нет…

Алгоритм, который мы сейчас построим, заключается в выполнении поиска. Для заданного значения (целого числа) мы скажем, имеет ли наше Двоичное дерево поиска это значение или нет.

Важно отметить, как мы определили дерево алгоритм вставки . Сначала у нас есть наш корень |/узел . Все левые поддерева узлы будут иметь меньшие значения, чем корневой | узел . И все правильные поддерево узлы будут иметь значения, большие, чем корневой | узел .

Давайте рассмотрим пример.

Представьте, что у нас есть это дерево .

Теперь мы хотим знать, есть ли у нас узел, основанный на значении 52.

Давайте разберем это.

Теперь давайте закодируем его.

class BinarySearchTree:
    def __init__(self, value):
        self.value = value
        self.left_child = None
        self.right_child = None

    def find_node(self, value):
        if value < self.value and self.left_child:
            return self.left_child.find_node(value)
        if value > self.value and self.right_child:
            return self.right_child.find_node(value)

        return value == self.value

Давайте разберем код:

• Строки 8 и 9 подпадают под правило № 1.

• Строки 10 и 11 подпадают под правило № 2.

• Строка 13 подпадает под правило № 3.

Как мы это проверим?

Давайте создадим наше Двоичное дерево поиска , инициализировав корневой | узел со значением 15.

bst = BinarySearchTree(15)

А теперь мы вставим много новых узлов .

bst.insert_node(10)
bst.insert_node(8)
bst.insert_node(12)
bst.insert_node(20)
bst.insert_node(17)
bst.insert_node(25)
bst.insert_node(19)

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

print(bst.find_node(15)) # True
print(bst.find_node(10)) # True
print(bst.find_node(8)) # True
print(bst.find_node(12)) # True
print(bst.find_node(20)) # True
print(bst.find_node(17)) # True
print(bst.find_node(25)) # True
print(bst.find_node(19)) # True

Да, это работает для этих заданных значений! Давайте проверим значение, которого нет в нашем Двоичном дереве поиска .

print(bst.find_node(0)) # False

О да.

Наши поиски закончены.

Удаление: удаление и организация

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

• Сценарий № 1 : узел без дочерних элементов ( лист | узел ).

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 20) --->   |30|   |70|
#   /    \                                \
# |20|   |40|                             |40|

Если у узла , который мы хотим удалить, нет дочерних элементов, мы просто удаляем его. Алгоритму не нужно реорганизовывать дерево /.

• Сценарий № 2 : узел только с одним дочерним элементом ( левый или правый дочерний элемент).

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |20|   |70|
#   /
# |20|

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

• Сценарий № 3 : узел с двумя детьми.

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |40|   |70|
#   /    \                             /
# |20|   |40|                        |20|

Когда узел имеет 2 дочерних элемента, нам нужно найти узел с минимальным значением, начиная с узла ‘s правого дочернего элемента . Мы поместим этот узел с минимальным значением на место узла , который мы хотим удалить.

Пришло время кодировать.

def remove_node(self, value, parent):
    if value < self.value and self.left_child:
        return self.left_child.remove_node(value, self)
    elif value < self.value:
        return False
    elif value > self.value and self.right_child:
        return self.right_child.remove_node(value, self)
    elif value > self.value:
        return False
    else:
        if self.left_child is None and self.right_child is None and self == parent.left_child:
            parent.left_child = None
            self.clear_node()
        elif self.left_child is None and self.right_child is None and self == parent.right_child:
            parent.right_child = None
            self.clear_node()
        elif self.left_child and self.right_child is None and self == parent.left_child:
            parent.left_child = self.left_child
            self.clear_node()
        elif self.left_child and self.right_child is None and self == parent.right_child:
            parent.right_child = self.left_child
            self.clear_node()
        elif self.right_child and self.left_child is None and self == parent.left_child:
            parent.left_child = self.right_child
            self.clear_node()
        elif self.right_child and self.left_child is None and self == parent.right_child:
            parent.right_child = self.right_child
            self.clear_node()
        else:
            self.value = self.right_child.find_minimum_value()
            self.right_child.remove_node(self.value, self)

        return True

• Чтобы использовать метод clear_node : установите значение None для всех трех атрибутов — ( value , left_child и right_child )

def clear_node(self):
    self.value = None
    self.left_child = None
    self.right_child = None

• Чтобы использовать метод find_minimum_value : перейдите влево. Если мы не можем найти больше узлов, мы нашли самый маленький.

def find_minimum_value(self):
    if self.left_child:
        return self.left_child.find_minimum_value()
    else:
        return self.value

Теперь давайте проверим это.

Мы будем использовать это дерево для тестирования нашего алгоритма remove_node .

#        |15|
#      /      \
#    |10|     |20|
#   /    \    /    \
# |8|   |12| |17| |25|
#              \
#              |19|

Давайте удалим узел со значением | 8. Это узел без дочернего элемента.

print(bst.remove_node(8, None)) # True
bst.pre_order_traversal()

#     |15|
#   /      \
# |10|     |20|
#    \    /    \
#   |12| |17| |25|
#          \
#          |19|

Теперь давайте удалим узел со значением | 17. Это узел только с одним ребенком.

print(bst.remove_node(17, None)) # True
bst.pre_order_traversal()

#        |15|
#      /      \
#    |10|     |20|
#       \    /    \
#      |12| |19| |25|

Наконец, мы удалим узел с двумя дочерними элементами. Это корень нашего дерева .

print(bst.remove_node(15, None)) # True
bst.pre_order_traversal()

#        |19|
#      /      \
#    |10|     |20|
#        \        \
#        |12|     |25|

Теперь тесты закончены.

На данный момент это все!

Здесь мы многому научились.

Поздравляю с окончанием этого плотного контента. Очень трудно понять концепцию, которую мы не знаем. Но ты это сделал.

Это еще один шаг вперед на моем пути к изучению и освоению алгоритмов и структур данных. Вы можете ознакомиться с документацией о моем полном путешествии здесь, в моей публикации Renaissance Developer .

Получайте удовольствие, продолжайте учиться и кодировать.

Вот мои Medium , Twitter , GitHub и LinkedIn аккаунты. ☺

Дополнительные ресурсы

• Введение в древовидную структуру данных от mycodeschool

• Дерево по Википедии

• Как не быть Загнанным В Тупик Деревьями талантливым Вайдехи Джоши

• Вступление к деревьям, Лекция профессора Джонатана Коэна

• Вступление к деревьям, Лекция профессора Дэвида Шмидта

• Вступление к деревьям, Лекция профессора Виктора Адамчика

• Деревья с Гейл Лакманн Макдауэлл

• Реализация бинарного дерева и Тесты by TK

• Курс Coursera: Структуры данных Калифорнийского университета в Сан – Диего

• Курс Coursera: Структуры данных и производительность Калифорнийского университета в Сан – Диего

• Концепции и реализация бинарного дерева поиска по программированию Пола

• Реализация бинарного дерева поиска и Тесты by TK

• Обход дерева по Википедии

• Бинарное дерево поиска Алгоритм удаления узлов от GeeksforGeeks

• Бинарное дерево поиска R emove N ode A алгоритм Algolist

• Изучение Python От нуля до Героя