Python алгоритмы
Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.
Дай 10 !)
суббота, 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) — бинарное дерево, в котором для каждого узла выполняется условие: все узлы в левом поддереве меньше, и все узлы в правом поддереве больше данного узла.
- сконструировать бинарное дерево таким образом, чтобы сумма путей была минимальной, так как это сокращает время вычислений для различных алгоритмов.
- сконструировать полное расширенное бинарное дерево таким образом, чтобы сумма произведений путей от корневого узла до листьев на значение листового узла была минимальной.
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
- Работа со структурами данных в языках Си и Python: Часть 6. Двоичные деревья
- Может быть полезным Обходы бинарных деревьев
Источник
Бинарное дерево: посчитать количество листьев
Нужно построить бинарное дерево типа *char. В этом бинарном дереве найти количество листьев (листья, как я понимаю, это элементы, которые не содержат потомков). Попробовал написать, но выводится какая-то каша-малаша. Не совсем понимаю принцип работы этого дерева. Был бы очень благодарен за помощь
С односвязными и двусвязными списками было как-то проще.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
#include #include using namespace std; struct point { char *key;//информационное поле point *left;//адрес левого поддерева point *right;//адрес правого поддерева }; //добавление элемента d в дерево поиска Корень Левое поддерево Правое поддерево //построение идеально сбалансированного дерева point* Tree(int n, point* beg) { point*r; int nl, nr; if (n == 0) { beg = NULL; return beg; } nl = n / 2; nr = n - nl - 1; r = new point; char s[50]; cout "Слово: "; cin >> s; r->key = new char[strlen(s) + 1]; r->left = Tree(nl, r->left); r->right = Tree(nr, r->right); beg = r; return beg; } void treeprint(point *beg) { if (beg != NULL) { treeprint(beg->left); cout beg->key endl; treeprint(beg->right); } } int main() { setlocale(LC_ALL, "russian"); srand(time(NULL)); int n = 0, k = 0; point *beg = nullptr; do { cout "1. Создать бинарное дерево\n"; cout "2. Показать бинарное дерево\n"; cout "3. Выход\n"; cin >> k; switch (k) { case 1: cout "Введите количество элементов" endl; cin >> n; beg = Tree(n, beg); cout endl; break; case 2: treeprint(beg); cout endl; break; } } while (k != 3); system("pause"); return 0; } Источник
Как найти количество листьев в бинарном дереве поиска
Иногда мне приходится находить количество листьев в поисковом двоичном дереве. Решил ( в первую очередь для себя ) написать эту заметку-шпаргалку, чтобы при необходимости быстро вспомнить алгоритм.
Хочу рассмотреть следующее анонимное двоичное дерево поиска:
Рисунок — стандартное анонимное бинарное дерево поиска
➡ Очевидно, чтобы найти количество листьев в бинарном дереве, необходимо знать определения термина «лист», чтобы понимать, а что, собственно, ищем-то.
Лист — узел поискового двоичного дерева, который не имеет потомков.
Тогда я отмечу все листовые узлы на рассматриваемом анонимном дереве красным цветом:
Рисунок — двоичное дерево поиска, у которого листовые вершины закрашены красным цветом
Моя задача — понять, каким образом найти все эти «красные» вершины, являющиеся листьями. То есть мне нужна функция, которая в качестве результата вернет количество листьев двоичного дерева.
Я хочу посмотреть на это анонимное поисковое бинарное дерево со всеми связями, на котором выделены красным цветом все листовые узлы с их связями:
Рисунок — бинарное дерево поиска со всеми связями его вершин
Внимательно изучив топологию этого дерева стало понятно, что листовые узлы прекращают порождение новых узлов, так как у них нет потомков ( кстати, в соответствии с их определением ). Следовательно, если встретился лист, то сразу можно делать возврат. Нет никакого смысла спускаться ниже, доходя до NULL-указателей.
Поскольку искомая программная функция должна в качестве результата возвращать количество листьев в бинарном дереве поиска, то я буду возвращать «$+1$», когда встретится лист. Понятно, что мне потребуется запустить обход вершин всего поискового дерева.
В итоге я написал следующую мощную функцию, которая считает количество листов:
Также напомню, что собой представляет пользовательский тип данных Node_status:
Функция Get_leafs_count является максимально универсальной. Даже, если на вход этой функции передать пустое дерево, то она корректно обработает такую ситуацию и в качестве ответа вернет $0$. При этом данная функция является достаточно сложной для понимания, так как использует каскадную рекурсию.
➡ Думаю, что теперь я легко смогу брать алгоритм и программную функцию для своих проектов, связанных с обработкой бинарного дерева поиска.
В комментариях пишите, что непонятно в рамках этой функции. Если непонятно, что это за функция Get_status_node, которая вызывается внутри функции Get_leafs_count, то попробуйте реализовать ее самостоятельно. Цель этой функции — определение статуса узла поискового дерева. Кстати, в одной из своих заметок, я детально рассказываю об этой функции и привожу ее программную реализацию.
| ВНИМАНИЕ | Для заказа программы на двоичное дерево поиска пишите на мой электронный адрес proglabs@mail.ru |
Источник