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

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

В конце концов, вы узнаете о hash tables слишком. Если вы хотите получить степень в области компьютерных наук, вы должны пройти курс по структуре данных. Вы также узнаете о linked lists, queuesа также stacks. Эти структуры данных называются «линейными» структурами данных, потому что все они имеют логическое начало и логический конец.

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

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

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

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

Определение

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

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

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

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

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

Вышеприведенный рисунок — это мое генеалогическое древо. Tossico, Akikazu, Hitomi, а также Takemi мои бабушка и дедушка.

Toshiaki а также Julianaмои родители.

TK, Yuji, Brunoа также Kaio дети моих родителей (я и мои братья).

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

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

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

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

А tree представляет собой совокупность сущностей, называемых nodes. Узлы связаны edges. Каждый node содержит value или же dataи он может иметь или не иметь child node .

first node принадлежащий tree называется root. Если это root node связано с другим node, root тогда является parent node и связанный node это child.

ВсеTree nodes соединены связями, называемыми edges. Это важная часть treesпотому что он управляет отношениями между nodes.

Leaves последние nodes на tree. Это узлы без потомков. Как настоящие деревья, у нас есть root, branchesи, наконец, leaves.

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

height из tree это длина самого длинного пути к leaf.

depth из node это длина пути к его root.

Резюме терминологии

  • **Корень ** является самым верхним node принадлежащий tree

  • **Край **является связующим звеном между двумя nodes

  • **ребенок **является node у которого есть parent node

  • **Родитель ** является node который имеет edge к child node

  • **Лист **является node у которого нет child node в tree

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

  • **Глубина **длина пути к root

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

Теперь поговорим о конкретном типе tree. Мы называем этоbinary tree.

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

Итак, давайте рассмотрим пример binary tree.

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

Первое, что нам нужно иметь в виду, когда мы внедряем binary tree что это сборник nodes. Каждый node имеет три атрибута: value, left_childа также right_child.

Как реализовать простой binary tree который инициализируется этими тремя свойствами?

Давайте взглянем.

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

Вот. Наш binary tree учебный класс.

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

Почему?

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

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

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

Вот и все.

Мы можем пройти string ‘aкак value нашим Binary Tree node. Если мы напечатаем value, left_childа также right_childмы можем видеть значения.

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

Мы реализуем метод для вставки нового node к right и к left.

Вот правила:

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

  • Если у него есть left childмы создаем новый узел и помещаем его в текущий left childместо. Выделить это left child node к новому узлу 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. Или же мы создаем новый узел и помещаем его в текущий left childместо. Выделить это left child node к новому узлу left child.

И мы делаем то же самое, чтобы вставить right child node.

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

Сделанный. 😃

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

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

Подводя итог иллюстрации этого дерева:

  • a node будет root из нашего binary Tree

  • a left child является b node

  • a right child является c node

  • b right child является d node (b node не имеет left child)

  • c left child является e node

  • c right child является f node

  • оба e а также f nodes не иметь детей

Итак, вот код для tree:

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) 
print(b_node.value) 
print(c_node.value) 
print(d_node.value) 
print(e_node.value) 
print(f_node.value)

Вставка сделана.

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

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

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

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

ДФС исследует путь до листа до отступление и исследовать другой путь. Давайте рассмотрим пример с этим типом обхода.

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

Почему?

Давайте сломаем это.

  1. Перейти к left child (2). Распечатайте это.

  2. Затем перейдите к left child (3). Распечатайте это. (Этот node не имеет детей)

  3. Вернитесь назад и идите right child (4). Распечатайте это. (Этот node не имеет детей)

  4. Вернитесь к root node и иди в right child (5). Распечатайте это.

  5. Перейти к left child (6). Распечатайте это. (Этот node не имеет детей)

  6. Вернитесь и идите к right child (7). Распечатайте это. (Этот node не имеет детей)

  7. Сделанный.

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

Теперь, когда мы знакомы с этим алгоритмом обхода, мы обсудим типы ДФС: 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()

В целях

Результат алгоритма по порядку для этого tree пример: 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 алгоритм этого tree пример: 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)

БФС алгоритм проходит через tree уровень за уровнем и глубину за глубиной.

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

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

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

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

  • Уровень/Глубина 2: nodes со значениями 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)

Для реализации БФС Алгоритм, мы используем queue структура данных в помощь.

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

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

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

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

Важное свойство а Binary Search Tree заключается в том, что значение Binary Search Tree nodeбольше, чем стоимость потомства его left childно меньше, чем стоимость потомка его right child.”

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

  • **A ** перевернуто. subtree 7–5–8–6 должны быть справа, а subtree 2–1–3 должны быть слева.

  • **В** — единственный правильный вариант. Он удовлетворяет Binary Search Tree имущество.

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

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

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

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

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

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

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

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

Теперь мы можем начать вставлять node по node.

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

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

  • 4 меньше 50. Node со значением 50 имеет left child 21. Поскольку 4 меньше 21, вставьте его слева от этого node.

  • 32 меньше 50. Node со значением 50 имеет left child 21. Поскольку 32 больше 21, вставьте 32 справа от этого node.

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

  • 64 больше 50. Node со значением 50 имеет right child76. Поскольку 64 меньше 76, вставьте 64 слева от этого числа. node.

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

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

Давайте сломаем это.

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

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 children, соответственно. Линии 11 а также 15 те, которые выполняют вставку для каждого child.

Ищем значение узла… Или нет…

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

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

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

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

Теперь мы хотим знать, есть ли у нас узел, основанный на значении 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.

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

Давайте создадим наш Binary Search Treeпутем инициализации root node со значением 15.

bst = BinarySearchTree(15)

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

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)

За каждую вставленную node мы проверим, если наш find_node метод действительно работает.

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

Да, это работает для этих значений! Давайте проверим значение, которое не существует в нашем Binary Search Tree.

print(bst.find_node(0))

Ах, да.

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

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

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

  • Сценарий №1: А node без children (leaf node).

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

  • Сценарий №2: А node с одним ребенком(left или же right ребенок).

В этом случае наш алгоритм должен сделать родителя node указать на child узел. Если node это left childмы делаем родителем left child указать на child. Если node это right child его родителя, мы делаем родителем right child указать на child.

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

Когда node имеет 2 детей, нам нужно найти node с минимальным значением, начиная с nodeхright child. мы положим это node с минимальным значением вместо node мы хотим удалить.

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

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

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

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

Давайте удалим node с value 8. Это node без ребенка.

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

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

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

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

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

Теперь испытания завершены. 😃

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

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

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

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

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

Вот мои Середина, Твиттер, Гитхаба также LinkedIn счета.☺

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

Похожие записи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *