Бинарное дерево python что это
Перейти к содержимому

Бинарное дерево python что это

  • автор:

Python – Дерево поиска

Бинарное дерево поиска (BST) – это дерево, в котором все узлы следуют указанным ниже свойствам. Левое поддерево узла имеет ключ, меньший или равный ключу его родительского узла. Правое поддерево узла имеет ключ больше, чем ключ его родительского узла. Таким образом, BST делит все свои поддеревья на два сегмента; левое поддерево и правое поддерево и может быть определено как –

left_subtree (keys)  node (key)  right_subtree (keys)

Поиск значения в B-дереве

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

class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert method to create nodes def insert(self, data): if self.data: if data  self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) elif data > self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # findval method to compare the value with nodes def findval(self, lkpval): if lkpval  self.data: if self.left is None: return str(lkpval)+" Not Found" return self.left.findval(lkpval) elif lkpval > self.data: if self.right is None: return str(lkpval)+" Not Found" return self.right.findval(lkpval) else: print(str(self.data) + ' is found') # Print the tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() root = Node(12) root.insert(6) root.insert(14) root.insert(3) print(root.findval(7)) print(root.findval(14))

Когда приведенный выше код выполняется, он дает следующий результат –

Бинарные деревья поиска и рекурсия – это просто

Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.

Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями.

image

Рис. 1 Бинарное дерево

Бинарное дерево поиска — это бинарное дерево, обладающее дополнительными свойствами: значение левого потомка меньше значения родителя, а значение правого потомка больше значения родителя для каждого узла дерева. То есть, данные в бинарном дереве поиска хранятся в отсортированном виде. При каждой операции вставки нового или удаления существующего узла отсортированный порядок дерева сохраняется. При поиске элемента сравнивается искомое значение с корнем. Если искомое больше корня, то поиск продолжается в правом потомке корня, если меньше, то в левом, если равно, то значение найдено и поиск прекращается.

image

Рис. 2 Бинарное дерево поиска
Сбалансированное бинарное дерево поиска — это бинарное дерево поиска с логарифмической высотой. Данное определение скорее идейное, чем строгое. Строгое определение оперирует разницей глубины самого глубокого и самого неглубокого листа (в AVL-деревьях) или отношением глубины самого глубокого и самого неглубокого листа (в красно-черных деревьях). В сбалансированном бинарном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма). В вырожденном случае несбалансированного бинарного дерева поиска, например, когда в пустое дерево вставлялась отсортированная последовательность, дерево превратится в линейный список, и операции поиска, вставки и удаления будут выполняться за линейное время. Поэтому балансировка дерева крайне важна. Технически балансировка осуществляется поворотами частей дерева при вставке нового элемента, если вставка данного элемента нарушила условие сбалансированности.

image

Рис. 3 Сбалансированное бинарное дерево поиска

Сбалансированное бинарное дерево поиска применяется, когда необходимо осуществлять быстрый поиск элементов, чередующийся со вставками новых элементов и удалениями существующих. В случае, если набор элементов, хранящийся в структуре данных фиксирован и нет новых вставок и удалений, то массив предпочтительнее. Потому что поиск можно осуществлять алгоритмом бинарного поиска за то же логарифмическое время, но отсутствуют дополнительные издержки по хранению и использованию указателей. Например, в С++ ассоциативные контейнеры set и map представляют собой сбалансированное бинарное дерево поиска.

image

Рис. 4 Экстремально несбалансированное бинарное дерево поиска

Теперь кратко обсудим рекурсию. Рекурсия в программировании – это вызов функцией самой себя с другими аргументами. В принципе, рекурсивная функция может вызывать сама себя и с теми же самыми аргументами, но в этом случае будет бесконечный цикл рекурсии, который закончится переполнением стека. Внутри любой рекурсивной функции должен быть базовый случай, при котором происходит выход из функции, а также вызов или вызовы самой себя с другими аргументами. Аргументы не просто должны быть другими, а должны приближать вызов функции к базовому случаю. Например, вызов внутри рекурсивной функции расчета факториала должен идти с меньшим по значению аргументом, а вызовы внутри рекурсивной функции обхода дерева должны идти с узлами, находящимися дальше от корня, ближе к листьям. Рекурсия может быть не только прямой (вызов непосредственно себя), но и косвенной. Например А вызывает Б, а Б вызывает А. С помощью рекурсии можно эмулировать итеративный цикл, а также работу структуры данных стек (LIFO).

int factorial(int n) < if(n return n * factorial(n - 1); //рекурсивеый вызов с другим аргументом > // factorial(1): return 1 // factorial(2): return 2 * factorial(1) (return 2 * 1) // factorial(3): return 3 * factorial(2) (return 3 * 2 * 1) // factorial(4): return 4 * factorial(3) (return 4 * 3 * 2 * 1) // Вычисляет факториал числа n (n должно быть небольшим из-за типа int // возвращаемого значения. На практике можно сделать long long и вообще // заменить рекурсию циклом. Если важна скорость рассчетов и не жалко память, то // можно совсем избавиться от функции и использовать массив с предварительно // посчитанными факториалами). void reverseBinary(int n) < if (n == 0) // Базовый случай < return; >cout // Печатает бинарное представление числа в обратном порядке void forvardBinary(int n) < if (n == 0) // Базовый случай < return; >forvardBinary(n/2); //рекурсивеый вызов с другим аргументом cout // Поменяли местами две последние инструкции // Печатает бинарное представление числа в прямом порядке // Функция является примером эмуляции стека void ReverseForvardBinary(int n) < if (n == 0) // Базовый случай < return; >cout // Функция печатает сначала бинарное представление в обратном порядке, // а затем в прямом порядке int product(int x, int y) < if (y == 0) // Базовый случай < return 0; >return (x + product(x, y-1)); //рекурсивеый вызов с другим аргументом > // Функция вычисляет произведение x * y ( складывает x y раз) // Функция абсурдна с точки зрения практики, // приведена для лучшего понимания рекурсии 

Кратко обсудим деревья с точки зрения теории графов. Граф – это множество вершин и ребер. Ребро – это связь между двумя вершинами. Количество возможных ребер в графе квадратично зависит от количества вершин (для понимания можно представить турнирную таблицу сыгранных матчей). Дерево – это связный граф без циклов. Связность означает, что из любой вершины в любую другую существует путь по ребрам. Отсутствие циклов означает, что данный путь – единственный. Обход графа – это систематическое посещение всех его вершин по одному разу каждой. Существует два вида обхода графа: 1) поиск в глубину; 2) поиск в ширину.

Поиск в ширину (BFS) идет из начальной вершины, посещает сначала все вершины находящиеся на расстоянии одного ребра от начальной, потом посещает все вершины на расстоянии два ребра от начальной и так далее. Алгоритм поиска в ширину является по своей природе нерекурсивным (итеративным). Для его реализации применяется структура данных очередь (FIFO).

Поиск в глубину (DFS) идет из начальной вершины, посещая еще не посещенные вершины без оглядки на удаленность от начальной вершины. Алгоритм поиска в глубину по своей природе является рекурсивным. Для эмуляции рекурсии в итеративном варианте алгоритма применяется структура данных стек.

С формальной точки зрения можно сделать как рекурсивную, так и итеративную версию как поиска в ширину, так и поиска в глубину. Для обхода в ширину в обоих случаях необходима очередь. Рекурсия в рекурсивной реализации обхода в ширину всего лишь эмулирует цикл. Для обхода в глубину существует рекурсивная реализация без стека, рекурсивная реализация со стеком и итеративная реализация со стеком. Итеративная реализация обхода в глубину без стека невозможна.

Асимптотическая сложность обхода и в ширину и в глубину O(V + E), где V – количество вершин, E – количество ребер. То есть является линейной по количеству вершин и ребер. Записи O(V + E) с содержательной точки зрения эквивалентна запись O(max(V,E)), но последняя не принята. То есть, сложность будет определятся максимальным из двух значений. Несмотря на то, что количество ребер квадратично зависит от количества вершин, мы не можем записать сложность как O(E), так как если граф сильно разреженный, то это будет ошибкой.

DFS применяется в алгоритме нахождения компонентов сильной связности в ориентированном графе. BFS применяется для нахождения кратчайшего пути в графе, в алгоритмах рассылки сообщений по сети, в сборщиках мусора, в программе индексирования – пауке поискового движка. И DFS и BFS применяются в алгоритме поиска минимального покрывающего дерева, при проверке циклов в графе, для проверки двудольности.
Обходу в ширину в графе соответствует обход по уровням бинарного дерева. При данном обходе идет посещение узлов по принципу сверху вниз и слева направо. Обходу в глубину в графе соответствуют три вида обходов бинарного дерева: прямой (pre-order), симметричный (in-order) и обратный (post-order).

Прямой обход идет в следующем порядке: корень, левый потомок, правый потомок. Симметричный — левый потомок, корень, правый потомок. Обратный – левый потомок, правый потомок, корень. В коде рекурсивной функции соответствующего обхода сохраняется соответствующий порядок вызовов (порядок строк кода), где вместо корня идет вызов данной рекурсивной функции.

Если нам дано изображение дерева, и нужно найти его обходы, то может помочь следующая техника (см. рис. 5). Обводим дерево огибающей замкнутой кривой (начинаем идти слева вниз и замыкаем справа вверх). Прямому обходу будет соответствовать порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами слева. Для симметричного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами снизу. Для обратного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами справа. В коде рекурсивного вызова прямого обхода идет: вызов, левый, правый. Симметричного – левый, вызов, правый. Обратного – левый правый, вызов.

image

Рис. 5 Вспомогательный рисунок для обходов

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

struct TreeNode < double data; // ключ/данные TreeNode *left; // указатель на левого потомка TreeNode *right; // указатель на правого потомка >; void levelOrderPrint(TreeNode *root) < if (root == NULL) < return; >queue q; // Создаем очередь q.push(root); // Вставляем корень в очередь while (!q.empty() ) // пока очередь не пуста < TreeNode* temp = q.front(); // Берем первый элемент в очереди q.pop(); // Удаляем первый элемент в очереди cout data left != NULL ) q.push(temp->left); // Вставляем в очередь левого потомка if ( temp->right != NULL ) q.push(temp->right); // Вставляем в очередь правого потомка > > void preorderPrint(TreeNode *root) < if (root == NULL) // Базовый случай < return; >cout data left); //рекурсивный вызов левого поддерева preorderPrint(root->right); //рекурсивный вызов правого поддерева > // Функция печатает значения бинарного дерева поиска в прямом порядке. // Вместо печати первой инструкцией функции может быть любое действие // с данным узлом void inorderPrint(TreeNode *root) < if (root == NULL) // Базовый случай < return; >preorderPrint(root->left); //рекурсивный вызов левого поддерева cout data right); //рекурсивный вызов правого поддерева > // Функция печатает значения бинарного дерева поиска в симметричном порядке. // То есть в отсортированном порядке void postorderPrint(TreeNode *root) < if (root == NULL) // Базовый случай < return; >preorderPrint(root->left); //рекурсивный вызов левого поддерева preorderPrint(root->right); //рекурсивный вызов правого поддерева cout data // Функция печатает значения бинарного дерева поиска в обратном порядке. // Не путайте обратный и обратноотсортированный (обратный симметричный). void reverseInorderPrint(TreeNode *root) < if (root == NULL) // Базовый случай < return; >preorderPrint(root->right); //рекурсивный вызов правого поддерева cout data left); //рекурсивный вызов левого поддерева > // Функция печатает значения бинарного дерева поиска в обратном симметричном порядке. // То есть в обратном отсортированном порядке void iterativePreorder(TreeNode *root) < if (root == NULL) < return; >stack s; // Создаем стек s.push(root); // Вставляем корень в стек /* Извлекаем из стека один за другим все элементы. Для каждого извлеченного делаем следующее 1) печатаем его 2) вставляем в стек правого! потомка (Внимание! стек поменяет порядок выполнения на противоположный!) 3) вставляем в стек левого! потомка */ while (s.empty() == false) < // Извлекаем вершину стека и печатаем TreeNode *temp = s.top(); s.pop(); cout data right) s.push(temp->right); // Вставляем в стек правого потомка if (temp->left) s.push(temp->left); // Вставляем в стек левого потомка > > // В симметричном и обратном итеративном обходах просто меняем инструкции // местами по аналогии с рекурсивными функциями. 

Python – двоичное дерево

Дерево представляет собой узлы, соединенные ребрами. Это нелинейная структура данных. Он имеет следующие свойства.

  • Один узел помечен как корневой узел.
  • Каждый узел, кроме корневого, связан с одним родительским узлом.
  • Каждый узел может иметь произвольный номер узла chid.

Мы создаем древовидную структуру данных в python, используя концептуальный узел os, обсуждавшийся ранее. Мы определяем один узел как корневой узел, а затем добавляем больше узлов как дочерние узлы. Ниже находится программа для создания корневого узла.

Создать Root

Мы просто создаем класс Node и добавляем присвоить значение узлу. Это становится деревом только с корневым узлом.

class Node: def __init__(self, data): self.left = None self.right = None self.data = data def PrintTree(self): print(self.data) root = Node(10) root.PrintTree()

Когда приведенный выше код выполняется, он дает следующий результат –

Вставка в дерево

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

class Node: def __init__(self, data): self.left = None self.right = None self.data = data def insert(self, data): # Compare the new value with the parent node if self.data: if data  self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) elif data > self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Use the insert method to add nodes root = Node(12) root.insert(6) root.insert(14) root.insert(3) root.PrintTree()

Когда приведенный выше код выполняется, он дает следующий результат –

3 6 12 14

Обход дерева

Дерево может быть пройдено путем выбора последовательности для посещения каждого узла. Как мы ясно видим, мы можем начать с узла, затем сначала посетить левое поддерево, а затем – правое поддерево. Или мы также можем посетить правое поддерево первым и левое поддерево следующим. Соответственно существуют разные имена для этих методов обхода дерева. Мы изучим их подробно в главе, реализующей алгоритмы обхода дерева здесь. Алгоритмы обхода дерева

Python алгоритмы

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

суббота, 30 июля 2011 г.

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

Бинарное дерево представляет собой структуру, в которой каждый узел (или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом. Бинарное дерево
с N узлами имеет не меньше [log2N + 1] уровней (при максимально плотной упаковке узлов).
Если уровни дерева занумеровать, считая что корень лежит на уровне 1, то на уровне с номером К лежит 2 К-1 узел. У полного бинарного дерева с j уровнями (занумерованными от 1 до j) все листья лежат на уровне с номером j, и у каждого узла на уровнях с первого по j — 1
в точности два непосредственных потомка. В полном бинарном дереве с j уровнями 2 j — 1 узел.
*-Нравится статья? Кликни по рекламе! 🙂

Бинарные деревья поиска обычно применяются для реализации множеств и ассоциативных массивов. И применяются для быстрого поиска информации. Например в статье Двоичный (бинарный) поиск элемента в массиве мы искали во встроенной в Python структуре данных, типа list, а могли реализовать бинарное дерево. Двоичные деревья, как и связные списки, являются рекурсивными структурами.
Различные реализации одного и того же бинарного дерева

  • полное(расширенное) бинарное дерево — каждый узел, за исключением листьев, имеет по 2 дочерних узла;
  • идеальное бинарное дерево — это полное бинарное дерево, в котором все листья находятся на одной высоте;
  • сбалансированное бинарное дерево — это бинарное дерево, в котором высота 2-х поддеревьев для каждого узла отличается не более чем на 1. Глубина такого дерева вычисляется как двоичный логарифм log(n), где n — общее число узлов;
  • вырожденное дерево — дерево, в котором каждый узел имеет всего один дочерний узел, фактически это связный список;
  • бинарное поисковое дерево (BST) — бинарное дерево, в котором для каждого узла выполняется условие: все узлы в левом поддереве меньше, и все узлы в правом поддереве больше данного узла.
S = N +1
E=3+3+2+3+4+4+3+3=25,
I=2+1+0+2+3+1+2=11.
E=I+2n, где n - число узлов.

  1. сконструировать бинарное дерево таким образом, чтобы сумма путей была минимальной, так как это сокращает время вычислений для различных алгоритмов.
  2. сконструировать полное расширенное бинарное дерево таким образом, чтобы сумма произведений путей от корневого узла до листьев на значение листового узла была минимальной.
2 3 5 7 11 13 17 19 23 29 31 37 41 5 5 7 11 13 17 19 23 29 31 37 41 10 7 11 13 17 19 23 29 31 37 41 17 24 17 19 23 29 31 37 41 24 34 19 23 29 31 37 41 24 34 42 29 31 37 41 42 53 65 37 41 42 53 65 78 95 65 78 95 143 238

Бинарное дерево, построенное по алгоритму Хаффмана

Более полную статью, по кодам Хаффмана читай в моей более ранней статье.

Реализация:
До этого, в своих статьях я показывал силу функционального программирования Python.
Теперь, пришло время, показать ООП в действии, создав новую структуру данных Tree, состоящую из других структур, типа Node.
Сразу скажу, что код взят с сайта IBM с минимальными изменениями и дополнениями. С моей точки зрения данный класс является недееспособным с точки зрения добавления элементов,по причине того, что мы сами должны строить дерево, помня структуру у себя в голове, а ведь мы можем и ошибиться. И позже я напишу так, как мне кажется верным, где добавление элемента является рекурсивным проходом по дереву и поиску подходящего места. А пока, разберем, что есть:

class node: def __init__(self, data = None, left = None, right = None): self.data = data self.left = left self.right = right def __str__(self): return 'Node ['+str(self.data)+']' #/* класс, описывающий само дерево */ class Tree: def __init__(self): self.root = None #корень дерева # /* функция для добавления узла в дерево */ def newNode(self, data): return node(data,None,None)

Дальше, все функции расширяют класс Tree.

Высота бинарного дерева
Для определения высоты дерева потребуется пройти от корня сначала по левому поддереву, потом по правому, сравнить две этих высоты и выбрать максимальное значение. И не забыть к получившемуся значению прибавить единицу (корневой элемент). Мы реализуем её в привычном уже нам рекурсивном виде.

# /* функция для вычисления высоты дерева */ def height(self,node): if node==None: return 0 else: lheight = self.height(node.left) rheight = self.height(node.right) if lheight > rheight: return(lheight+1) else: return(rheight+1)

«Зеркальное» отражение бинарного дерева
Когда два дерева являются зеркальным отражением друг друга, то говорится, что они симметричны. Для получения «зеркальной» копии дерева сначала выполняется проверка на наличие у корня дерева дочерних узлов, и если эти узлы есть, то они меняются местами. Потом эти же действия рекурсивно повторяются для левого и правого дочерних узлов. Если существует только один дочерний узел, тогда можно переходить на один уровень ниже по дереву и продолжать.

# /* функция для зеркального отражения дерева */ def mirrorTree(self, node): if node.left and node.right: node.left,node.right=node.right,node.left self.mirrorTree(node.right) self.mirrorTree(node.left) else: if node.left==None and node.right: return self.mirrorTree(node.right) if node.right==None and node.left: return self.mirrorTree(node.left)

Проверка наличия узла в бинарном дереве
Нужно только учесть, что данная функция не работает для зеркального отображения дерева!

# /* функция для проверки наличия узла */ def lookup(self, node, target): if node == None:return 0 else: if target == node.data: return 1 else: if target < node.data: return self.lookup(node.left, target) else: return self.lookup(node.right, target)

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

# /* функция для вычисления ширины дерева */ def getMaxWidth(self,root): maxWdth = 0 i = 1 width = 0 ; h = self.height(root) while( i < h): width = self.getWidth(root, i) if(width >maxWdth): maxWdth = width; i +=1 return maxWdth; def getWidth(self, root, level): if root == None: return 0 if level == 1: return 1 elif level > 1: return self.getWidth(root.left, level-1) + self.getWidth(root.right, level-1)

Распечатка дерева:

# /* функция для распечатки элементов на определенном уровне дерева */ def printGivenLevel(self, root, level): if root == None: return if level == 1: print ("%d " % root.data) elif level > 1: self.printGivenLevel(root.left, level-1); self.printGivenLevel(root.right, level-1); # /* функция для распечатки дерева */ def printLevelOrder(self, root): h = self.height(self.root) i=1 while(i<=h): self.printGivenLevel(self.root, i) i +=1

Сравнение бинарных деревьев
Вынесите её за пределы класса только)

def sameTree(a, b): if a==None and b==None: return 1 elif a and b: return( a.data == b.data and sameTree(a.left, b.left) and sameTree(a.right, b.right) ) return 0

Количество узлов в бинарном дереве
Вычислить количество узлов в бинарном дереве также можно с помощью рекурсии.
Хотя с точки зрения производительности и принципов ООП, правильнее встроить счетчик в сам объект.

def size(node): if node==None:return 0; return(size(node.left) + 1 + size(node.right));

Немножко о производительности
Я протестировал наш класс на поиск. К сожалению, данная его реализация проиграла бинарному поиску по списку, описанному ранее. Я тестировал, запуская в 100000 цикле поиска элемента со значением 5 и результат нашего класса
400003 function calls (100003 primitive calls) in 3.481 seconds
против
200003 function calls in 1.791 seconds
Я считаю, что причина в рекурсивном исполнении данного метода + реализации на Python, а не Си)

  1. Дж. Макконнелл - Основы современных алгоритмов.
  2. Структуры данных: бинарные деревья. Часть 1
  3. Работа со структурами данных в языках Си и Python: Часть 6. Двоичные деревья
  4. Может быть полезным Обходы бинарных деревьев

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

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