Структуры данных: деревья
Этот пост является третьим в серии о структурах данных. В этой серии статей рассматриваются 6 основных структур данных, которые будут обсуждаться на любом собеседовании по разработке программного обеспечения:
Что такое дерево?
Дерево - это нелинейная структура данных, которая упорядочивает данные иерархическим образом. Вы можете сравнить их с генеалогическим древом многих поколений; бабушки и дедушки, родители, дети и т. д. Семейные деревья организованы иерархически.
Древовидная структура данных представляет собой набор узлов. Эти узлы соединены друг с другом ребрами. Каждый узел содержит значение (данные) и может иметь или не иметь дочерний узел. В каждом (непустом) дереве первый узел дерева называется корнем.
Если этот корневой узел подключен к одному или нескольким узлам, он является родительским узлом, а подключенные узлы - его дочерними узлами. Узлы без дочерних узлов называются листьями или внешними узлами. Узлы, которые не являются листами, называются внутренними узлами. У внутренних узлов есть хотя бы один дочерний элемент. Узлы с одним и тем же родителем считаются братьями и сестрами.
В дереве выше:
- A является родительским для B и C.
- B называется дочерним по отношению к A.
- B и C - братья и сестры.
- E, F, H, I и J - листья.
Глубина узла - это количество ребер от корня до узла. (Длина пути к его корню). В дереве выше глубина узла I равна 3.
высота узла - это количество ребер от узла до самого глубокого листа. (Длина самого длинного пути к листу). Высота узла B равна 2.
Бинарные деревья
Узлы дерева могут иметь ноль или более дочерних элементов. Двоичное дерево - это дерево, узлы которого могут иметь не более двух дочерних узлов. Каждый узел может иметь левый и правый узел.
Узлы двоичного дерева обычно содержат три части данных:
- значение узла: целое число, строка, символ и т. Д.
- Указатель на левый дочерний элемент.
- Указатель на правого дочернего элемента.
Деревья двоичного поиска
Деревья двоичного поиска - это двоичные деревья, которые выполняют определенное свойство упорядочивания:
В любом поддереве левые узлы меньше корневого узла, который меньше, чем все правые узлы.
Это упорядочивающее свойство делает поиск определенного узла очень быстрым, потому что вы можете иметь хорошее представление о том, где искать в дереве в зависимости от значения, которое вы ищете.
Допустим, мы ищем узел, содержащий значение 4:
Сначала мы смотрим на корневой узел = 10. 4 меньше 10, поэтому узел должен находиться слева.
Затем мы смотрим на левый дочерний элемент = 5. 4 меньше 5, поэтому узел должен находиться слева.
Левый дочерний элемент = 3. 4 больше 3, поэтому узел должен быть справа.
Правильному ребенку 4 года! Мы достигли искомого узла. На каждом шаге игнорируем половину дерева.
Вставка в двоичные деревья поиска
Вернемся к нашему примеру с двоичным деревом поиска:
Допустим, мы хотели добавить значение 6.
- Смотрим на корневой узел = 10. 6 меньше 10, поэтому мы переходим к левому дочернему элементу.
- Левый дочерний элемент - 5. 6 больше 5, поэтому мы переходим к его правому дочернему элементу.
- Правильный ребенок - 9. 6 меньше 9, поэтому мы переходим к левому дочернему элементу.
- Левый дочерний элемент равен нулю. Мы можем разместить там наш узел.
Используя этот метод вставки, иногда мы можем получить несбалансированные деревья, в зависимости от того, как мы получаем узлы для вставки и как работает алгоритм построения дерева.
В худшем случае, если мы получим узлы: 1 → 2 → 3 → 4, мы можем получить такое дерево:
Не идеально. Это дерево выглядит как связанный список. Находки и вставки больше не будут такими быстрыми, как дерево. Сбалансированное двоичное дерево поиска можно найти за время O (log n), где n - количество узлов в дереве. Несбалансированное дерево, подобное приведенному выше, займет время O (n) (линейное время).
Обход дерева двоичного поиска
Есть три способа пройти через дерево:
- Обход по порядку: сначала посетите левый узел, затем корневой, а затем правый. A → B → C.
- Обход предварительного заказа: сначала посетите корень, затем его левый узел, а затем правый. B → A → C.
- Обход после заказа: сначала посетите левый узел, затем правый, а затем корневой. A → C → B.
В деревьях двоичного поиска мы обычно хотим использовать обход по порядку, потому что он позволяет нам печатать узлы по порядку.
Для обхода обычно используются два алгоритма: Поиск в глубину (DFS) и Поиск в ширину (BFS). При поиске в глубину мы начинаем с корня и исследуем как можно дальше вниз по каждой ветви перед тем, как вернуться. Порядок, предварительный заказ и обход после заказа подпадают под DFS. В поиске в ширину мы начинаем с корня и исследуем соседние узлы, прежде чем перейти к следующему уровню.
Реализация двоичного дерева поиска
Давайте создадим класс узла:
Наш узел состоит из трех частей: значение, левый указатель и правый указатель. Наши указатели изначально имеют значение null, потому что у нашего узла нет дочерних элементов (пока).
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
Вставка
Давайте создадим метод для вставки:
Если значение, которое мы хотим добавить, меньше или равно значению текущего узла, мы проверяем, осталось ли слева. Если левый дочерний элемент пуст, мы создаем новый узел с нашим значением и добавляем его туда. Если он не пустой, мы рекурсивно вызываем нашу функцию вставки в левой ветви нашего дерева.
Если значение, которое мы хотим добавить, больше, чем текущий узел, мы проверяем право. Если правый дочерний элемент пуст, мы создаем новый узел с нашим значением и добавляем его туда. Если он не пустой, мы рекурсивно вызываем нашу функцию вставки в правой ветви нашего дерева.
def insert(self, value):
if value <= self.value:
if self.left == None:
self.left = Node(value)
else:
self.left.insert(value)
else:
if self.right == None:
self.right = Node(value)
else:
self.right.insert(value)
Находить
Следующий метод, который мы хотим добавить, - это найти. Find также работает рекурсивно и в некотором смысле похож на вставку. find примет значение и вернет true, если найдет его, и false, если нет.
Начинаем с корня. Если значение корня равно искомому значению, мы возвращаем true. Если нет, мы проверяем, меньше ли значение, чем значение корневого узла. Если меньше, проверяем, пусто ли слева. Если слева пусто, это означает, что дерево не содержит искомого значения. Если left указывает на узел, мы рекурсивно вызываем наш метод find, чтобы проверить значение в левой части дерева.
Если значение, которое мы ищем, больше, чем значение в корневом узле, мы проверяем, пуст ли правый узел. Если это так, мы возвращаем false, потому что наше дерево не содержит этого значения. Если правая часть не пуста, мы рекурсивно вызываем наш метод поиска в правой части дерева.
def find(self, value):
if value == self.value:
return True
elif value < self.value:
if self.left == None:
return False
else:
return self.left.find(value)
else:
if self.right == None:
return False
else:
return self.right.find(value)
Печать (поиск в глубину)
Давайте напишем метод печати In-Order DFS для нашего класса Node. Как упоминалось выше, In-Order печатает левый узел, затем корень, затем правый узел.
В нашем методе мы сначала проверяем, не пуста ли левая часть дерева. Если у нас есть левая часть, мы рекурсивно вызываем наш метод для левой части дерева.
Когда мы достигаем точки, в которой левая сторона узла равна нулю, мы печатаем значение этого узла. Затем мы возвращаемся на шаг назад, чтобы распечатать корень. Затем мы проверяем, не пуста ли правая часть узла. Если справа есть узел, мы рекурсивно вызываем наш метод для этого правого узла.
def printInOrder(self):
if self.left != None:
self.left.printInOrder()
print(self.value)
if self.right != None:
self.right.printInOrder()
На этом пока все!
Если вы хотите узнать, как реализовать метод поиска в ширину, обычно это делается с использованием структуры данных Очередь в качестве вспомогательной. Я расскажу об очередях в следующем посте серии, так что следите за обновлениями!
Спасибо за прочтение!
