Что такое дерево в математике
Дерево в математике представляет собой графическую модель, используемую для описания и исследования взаимосвязей между объектами. Узлы дерева представляют собой объекты, а ребра — связи между этими объектами. Деревья широко используются в различных областях математики, включая теорию графов, теорию алгоритмов и вероятность. Понимание основных понятий и свойств деревьев позволяет решать множество задач и применять их в реальных ситуациях.
Дерево — это одна из основных абстрактных структур данных в математике, которая имеет широкое применение в различных областях, таких как информатика, графовая теория, теория вероятностей и другие. Оно представляет собой граф, состоящий из вершин и ребер, где каждая вершина имеет только одного родителя и ноль или более детей.
Важной особенностью дерева является то, что оно не содержит циклов, то есть путь от одной вершины к другой может быть только один и не может быть замкнут. Это делает дерево структурой иерархической организации данных, где каждая вершина представляет собой узел и может содержать информацию, а каждое ребро — связь между узлами.
Дерево имеет несколько свойств, которые делают его удобным для использования. Одно из них — это возможность эффективного поиска элементов. Благодаря особой структуре дерева, поиск элемента может быть выполнен за время, пропорциональное логарифму числа вершин. Еще одно свойство — это возможность добавления и удаления элементов. В силу того, что дерево представляет собой граф, оно может динамически изменяться, что делает его гибким инструментом для работы с данными.
Что такое дерево в математике?
Каждая вершина дерева может иметь произвольное количество дочерних вершин. Если вершина не имеет дочерних вершин, то она называется листом. Дерево может быть пустым, то есть не содержать ни одной вершины.
Деревья используются в различных областях математики и информатики для представления иерархических структур. Они являются основой для таких структур данных, как бинарные деревья, кучи, графы и др. Благодаря своей гибкости и универсальности, деревья широко применяются в алгоритмах и программировании.
Определение
Одна из вершин дерева называется корнем, остальные вершины называются потомками этого корня. Каждый узел имеет не более одного родительского узла, за исключением корня, который не имеет родителя.
Каждый потомок может иметь любое количество дочерних узлов, но каждый дочерний узел может иметь только одного родителя.
Как определяется дерево в математике?
В математике дерево представляет собой абстрактную структуру, состоящую из набора вершин и ребер, которые соединяют эти вершины. Вершины дерева образуют иерархическую структуру, где каждая вершина, кроме одной, имеет ровно одного родителя. Вершина без родителя называется корнем дерева.
Основная особенность дерева заключается в том, что не может быть циклов, то есть пути, в которых ребра образуют замкнутую последовательность. Кроме того, каждая вершина может иметь любое количество дочерних вершин, или не иметь их вовсе. Ветви, исходящие от одной вершины, называются поддеревьями.
Читать далее: Значение и применение arccos в математике
Вершины дерева могут быть помечены значением или меткой, которая представляет некоторую информацию. В зависимости от задачи, дерево может быть ориентированным, то есть иметь направленные ребра, или неориентированным.
Деревья широко применяются в различных областях математики и информатики. Они используются для моделирования иерархических структур, таких как семейные деревья, сетевые иерархии, деревья поиска и многое другое. Понимание основных свойств и примеров деревьев позволяет эффективно решать задачи с их использованием.
Свойства
Дерево в математике обладает рядом особых свойств, которые делают его полезным и удобным инструментом для анализа и моделирования различных явлений.
1. Иерархическая структура: Дерево представляет собой иерархическую структуру данных, где каждый элемент имеет родителя и может иметь один или несколько дочерних элементов. Это свойство позволяет организовывать данные и устанавливать взаимосвязи между ними.
2. Уникальность пути: В дереве существует только один путь от корня к любому узлу. Это гарантирует уникальность адресации каждого элемента и позволяет эффективно искать и обращаться к конкретным узлам.
3. Оптимальность поиска: Благодаря уникальности пути и иерархической структуре, дерево обладает оптимальностью поиска. Поиск элемента в дереве может быть выполнен за время O(log n), где n — количество элементов в дереве. Это свойство делает дерево эффективной структурой данных для поиска и сортировки.
4. Ветвление и расширяемость: Дерево позволяет гибко расширяться и изменяться, добавлять новые элементы и узлы. Это делает дерево удобным для организации сложных структур и моделей данных.
5. Отношения и подсчет: В дереве можно вычислять различные отношения между узлами и проводить подсчеты. Например, можно вычислять сумму всех элементов в поддереве или находить наибольший или наименьший элемент.
6. Графическое представление: Дерево может быть визуализировано в виде графа с узлами и ребрами. Это позволяет наглядно представить структуру дерева и взаимосвязи между его элементами.
Все эти свойства делают дерево мощным инструментом для решения различных задач в математике, программировании, искусственном интеллекте и других областях.
Какие свойства имеют деревья в математике?
1. Иерархическая структура: Дерево состоит из узлов, которые связаны между собой ребрами. Узлы делятся на два типа: корневой узел, который не имеет родителя, и листья, которые не имеют потомков. Каждый узел может иметь несколько потомков, но только одного родителя.
2. Отсутствие циклов: Дерево не содержит замкнутых цепей или циклов. Это означает, что нельзя пройти по ребрам от одного узла к другому и вернуться к исходному узлу без посещения других узлов.
3. Единственный путь: Между любыми двумя узлами в дереве существует единственный путь, который связывает их. Это позволяет эффективно находить и обрабатывать данные, хранящиеся в узлах дерева.
4. Графическое представление: Деревья можно представлять графически, где узлы отображаются в виде точек или кружков, а ребра — в виде линий, соединяющих узлы. Такое графическое представление позволяет наглядно исследовать и анализировать структуру дерева.
5. Рекурсивная структура: Дерево может быть определено рекурсивно, что означает, что каждый узел в дереве может быть рассмотрен как отдельное поддерево. Это позволяет использовать рекурсивные алгоритмы для манипуляций с деревом, таких как обход и поиск.
Читать далее: Как найти радиус закругления в математике: подробное объяснение и примеры
6. Использование в различных областях: Деревья имеют широкое применение в различных областях, включая информатику, биологию, искусственный интеллект, базы данных и многие другие. Они используются для организации данных, поиска, сортировки, оптимизации и других задач.
В итоге, деревья в математике обладают рядом уникальных свойств, которые делают их важным инструментом анализа и обработки данных.
Примеры
Деревья в математике широко используются для моделирования различных структур и процессов. Вот несколько примеров использования деревьев:
- Деревья решений: используются для принятия решений в искусственном интеллекте и машинном обучении. Каждый узел дерева представляет возможное решение или вариант действия, а ребра — возможные переходы между состояниями.
- Деревья поиска: используются для эффективного организации данных и поиска информации. Каждый узел дерева содержит ключ, который можно использовать для быстрого поиска нужного элемента.
- Деревья анализа: используются в лингвистике и компиляторах для анализа и разбора текстов и программ. Каждый узел дерева представляет синтаксическую структуру предложения или программы.
- Деревья семантического анализа: используются в компьютерных науках и искусственном интеллекте для представления семантической структуры текста или знаний. Каждый узел дерева содержит смысловую информацию о тексте или знаниях.
- Деревья генеалогических связей: используются в генеалогических исследованиях и родословных для представления связей между родственниками. Каждый узел дерева представляет отдельное лицо, а ребра — родственные связи.
Это лишь несколько примеров использования деревьев в математике. Деревья — мощный и универсальный инструмент, который может быть применен во многих областях.
Какие примеры деревьев существуют в математике?
Одним из примеров деревьев в математике является бинарное дерево. Бинарное дерево состоит из вершин и ребер, где каждая вершина имеет не более двух потомков. Бинарные деревья широко используются для построения алгоритмов поиска и сортировки, а также для моделирования бинарных отношений в различных областях математики.
Еще одним примером деревьев является дерево отрезков. Дерево отрезков используется в алгоритмах для решения задач на поиск минимума и максимума на отрезке, а также для выполнения операций суммирования и обновления значений на отрезке.
Графы также могут рассматриваться как примеры деревьев. Деревья являются частным случаем графов, где отсутствуют циклы. Графы являются основой для алгоритмов маршрутизации, анализа социальных сетей и многих других задач, и деревья в этом случае используются для организации и представления информации.
Также стоит упомянуть о деревьях решений. Деревья решений используются в машинном обучении и искусственном интеллекте для классификации и прогнозирования данных. Они представляют собой дерево, в котором каждая внутренняя вершина представляет тест на признак, а каждый листовой узел – классификацию или прогноз.
Видео по теме:
Отзывы
Екатерина Иванова
Очень интересная и познавательная статья! Я всегда думала, что дерево — это просто растение, но оказывается, в математике это также важное понятие. Определение дерева в математике, которое дано в статье, очень понятно объясняет эту концепцию. Мне понравилось, как автор описывает свойства деревьев, такие как отсутствие циклов и связность. Эти свойства делают деревья очень полезными в различных областях, включая информатику и теорию графов. Очень интересно было узнать о примерах деревьев, таких как дерево родословной и дерево выражения. Я оказалась совершенно неожиданно, что эти объекты могут быть представлены в виде деревьев. В целом, статья очень информативная и легкая для понимания. Спасибо автору за такое интересное чтение!
Читать далее: Как остановить цикл for в C: полезные советы и примеры
Александр Смирнов
Отличная статья! Математика всегда казалась мне сложной, но благодаря вашим подробным объяснениям, я наконец поняла, что такое дерево в математике. Очень интересно, как оно используется в решении задач. Теперь я понимаю, что дерево — это структура данных, которая помогает организовать информацию и представляет собой иерархическую систему ветвей и узлов. Мне понравилось, как вы привели примеры применения деревьев в реальной жизни, такие как семейное древо и дерево решений. Теперь я буду знать, что их можно использовать не только для рисования, но и для решения задач! Спасибо за простое и понятное объяснение! Я надеюсь, что вы продолжите делиться такими интересными темами.
Михаил Кузнецов
Статья очень понравилась! Я впервые узнала о таком понятии, как дерево в математике. Описанное определение помогло мне лучше понять, какие свойства обладает дерево и как оно используется в математике. Очень интересно, что дерево представляет собой граф без циклов, а каждая вершина связана с родительской и дочерней вершиной. Благодаря этим свойствам дерево находит свое применение в различных областях науки и информатики. Я бы хотела узнать больше о примерах использования деревьев в практических задачах и их решении. Надеюсь, что в будущем будет продолжение этой темы. Спасибо за информативную и понятную статью!
Дмитрий Смирнов
Статья очень интересная и познавательная! Я всегда задавался вопросом о том, как математика может быть связана с деревьями. Оказывается, дерево в математике — это не то, что растет на природе, а структура, состоящая из узлов и ребер. Мне нравится, как автор подробно объяснил определение и свойства деревьев, а также привел примеры их применения. Теперь я понимаю, что деревья используются в программировании, теории графов и других областях математики. Статья очень хорошо написана, просто и доступно. Я узнал много нового и теперь смогу лучше разбираться с деревьями в математике. Большое спасибо автору!
beautiful89
Очень интересная статья! Я всегда удивляюсь тому, как много мы можем узнать о математике, применяя ее к реальным предметам. Введение в дерево в математике было для меня открытием. Никогда не думала, что можно использовать деревья для описания и анализа различных ситуаций и структур. Сейчас я лучше понимаю, как деревья могут помочь нам в принятии решений и анализе данных. Понятие узлов, ветвей и листьев стало более понятным благодаря примерам, которые вы привели. Я узнала о таких важных свойствах деревьев, как высота, глубина и степень. Статья была очень информативной и понятной, и я надеюсь, что будет больше статей на эту тему. Спасибо!
Уроки 45 — 46
Деревья. Основные понятия
(§43. Деревья)
Как вы знаете из учебника 10 класса, дерево — это структура, отражающая иерархию (отношения подчинённости, многоуровневые связи). Напомним некоторые основные понятия, связанные с деревьями.
Дерево состоит из узлов и связей между ними (они называются дугами). Самый первый узел, расположенный на верхнем уровне (в него не входит ни одна стрелка-дуга), — это корень дерева. Конечные узлы, из которых не выходит ни одна дуга, называются листьями. Все остальные узлы, кроме корня и листьев, — это промежуточные узлы.
Из двух связанных узлов тот, который находится на более высоком уровне, называется родителем, а другой — сыном. Корень — это единственный узел, у которого нет родителя; у листьев нет сыновей.
Используются также понятия «предок» и «потомок». Потомок какого-то узла — это узел, в который можно перейти по стрелкам от узла-предка. Соответственно, предок какого-то узла — это узел, из которого можно перейти по стрелкам в данный узел.
В дереве на рис. 6.11 родитель узла Е — это узел В, а предки узла Е — это узлы А и В, для которых узел Е — потомок. Потомками узла А (корня дерева) являются все остальные узлы.
Высота дерева — это наибольшее расстояние (количество дуг) от корня до листа.
Высота дерева, приведённого на рис. 6.11, равна 2.
Рис. 6.11
Формально дерево можно определить следующим образом:
1) пустая структура — это дерево;
2) дерево — это корень и несколько связанных с ним отдельных (не связанных между собой) деревьев.
Здесь множество объектов (деревьев) определяется через само это множество на основе простого базового случая (пустого дерева). Такой приём называется рекурсией (см. главу 8 учебника для 10 класса). Согласно этому определению, дерево — это рекурсивная структура данных. Поэтому можно ожидать, что при работе с деревьями будут полезны рекурсивные алгоритмы.
Чаще всего в информатике используются двоичные (или бинарные) деревья, т. е. такие, в которых каждый узел имеет не более двух сыновей. Их также можно определить рекурсивно.
Двоичное дерево:
1) пустая структура — это двоичное дерево;
2) двоичное дерево — это корень и два связанных с ним отдельных двоичных дерева (левое и правое поддеревья).
Деревья широко применяются в следующих задачах:
• поиск в большом массиве неменяющихся данных;
• сортировка данных;
• вычисление арифметических выражений;
• оптимальное кодирование данных (метод сжатия Хаффмана).
Следующая страница Деревья поиска
Cкачать материалы урока
Дерево как структура данных
Какую выгоду можно извлечь из такой структуры данных, как дерево? В этой статье мы расскажем о данных в виде дерева, рассмотрим основные определения, которые следует знать, а также узнаем, как и зачем используется дерево в программировании. Спойлер: бинарные деревья часто применяют для поиска информации в базах данных, для сортировки данных, для проведения вычислений, для кодирования и в других случаях. Но давайте обо всем по порядку.
Основные термины
Дерево — это, по сути, один из частных случаев графа. Древовидная модель может быть весьма эффективна в случае представления динамических данных, особенно тогда, когда у разработчика стоит цель быстрого поиска информации, в тех же базах данных, к примеру. Еще древом называют структуру данных, которая представляет собой совокупность элементов, а также отношений между этими элементами, что вместе образует иерархическую древовидную структуру.
Каждый элемент — это вершина или узел дерева. Узлы, соединенные направленными дугами, называются ветвями. Начальный узел — это корень дерева (корневой узел). Листья — это узлы, в которые входит 1 ветвь, причем не выходит ни одной.
Общую терминологию можно посмотреть на левой и правой части картинки ниже:
Какие свойства есть у каждого древа:
— существует узел, в который не входит ни одна ветвь;
— в каждый узел, кроме корневого узла, входит 1 ветвь.
На практике деревья нередко применяют, изображая различные иерархии. Очень популярны, к примеру, генеалогические древа — они хорошо известны. Все узлы с ветвями, исходящими из единой общей вершины, являются потомками, а сама вершина называется предком (родительским узлом). Корневой узел не имеет предков, а листья не имеют потомков.
Также у дерева есть высота (глубина). Она определяется числом уровней, на которых располагаются узлы дерева. Глубина пустого древа равняется нулю, а если речь идет о дереве из одного корня, тогда единице. В данном случае на нулевом уровне может быть лишь одна вершина – корень, на 1-м – потомки корня, на 2-м – потомки потомков корня и т. д.
Ниже изображен графический вывод древа с 4-мя уровнями (дерево имеет глубину, равную четырем):
Следующий термин, который стоит рассмотреть, — это поддерево. Поддеревом называют часть древообразной структуры, которую можно представить в виде отдельного дерева.
Идем дальше. Древо может быть упорядоченным — в данном случае ветви, которые исходят из каждого узла, упорядочены по некоторому критерию.
Степень вершины в древе — это число ветвей (дуг), выходящих из этой вершины. Степень равняется максимальной степени вершины, которая входит в дерево. В этом случае листьями будут узлы, имеющие нулевую степень. По величине степени деревья бывают:
— двоичные (степень не больше двух);
— сильноветвящиеся (степень больше двух).
Деревья — это рекурсивные структуры, ведь каждое поддерево тоже является деревом. Каждый элемент такой рекурсивной структуры является или пустой структурой, или компонентом, с которым связано конечное количество поддеревьев.
Когда мы говорим о рекурсивных структурах, то действия с ними удобнее описывать посредством рекурсивных алгоритмов.
Обход древа
Чтобы выполнить конкретную операцию над всеми вершинами, надо все эти узлы просмотреть. Данную задачу называют обходом дерева. То есть обход представляет собой упорядоченную последовательность узлов, в которой каждый узел встречается лишь один раз.
В процессе обхода все узлы должны посещаться в некотором, заранее определенном порядке. Есть ряд способов обхода, вот три основные:
— прямой (префиксный, preorder);
— симметричный (инфиксный, inorder);
— обратный (постфиксный, postorder).
Существует много древовидных структур данных: двоичные (бинарные), красно-черные, В-деревья, матричные, смешанные и пр. Поговорим о бинарных.
Бинарные (двоичные) деревья
Бинарные имеют степень не более двух. То есть двоичным древом можно назвать динамическую структуру данных, где каждый узел имеет не большое 2-х потомков. В результате двоичное дерево состоит из элементов, где каждый из элементов содержит информационное поле, а также не больше 2-х ссылок на различные поддеревья. На каждый элемент древа есть только одна ссылка.
У бинарного древа каждый текущий узел — это структура, которая состоит из 4-х видов полей. Какие это поля:
— информационное (ключ вершины);
— служебное (включена вспомогательная информация, однако таких полей может быть несколько, а может и не быть вовсе);
— указатель на правое поддерево;
— указатель на левое поддерево.
Самый удобный вид бинарного древа — бинарное дерево поиска.
Что значит древо в контексте программирования?
Мы можем долго рассуждать о математическом определении древа, но это вряд ли поможет понять, какие именно выгоды можно извлечь из древовидной структуры данных. Тут важно отметить, что древо является способом организации данных в форме иерархической структуры.
В каких случаях древовидные структуры могут быть полезны при программировании:
- Когда данная иерархия существует в предметной области разрабатываемой программы. К примеру, программа должна обрабатывать генеалогическое древо либо работать со структурой каталогов. В таких ситуациях иногда есть смысл сохранять между объектами программы существующие иерархические отношения. В качестве примера можно вывести древо каталогов операционной системы UNIX:
- Когда между объектами, которые обрабатывает программа, отношения иерархии не заданы явно, но их можно задать, что сделает обработку данных удобнее. Как тут не вспомнить разработку парсеров либо трансляторов, где весьма полезным может быть древо синтаксического разбора?
- А сейчас очевидная вещь: поиск объектов более эффективен, когда объекты упорядочены, будь то те же базы данных. К примеру, поиск значения в неструктурированном наборе из тысячи элементов потребует до тысячи операций, тогда как в упорядоченном наборе может хватить всего дюжины. Вывод прост: раз иерархия — эффективный способ упорядочивания объектов, почему же не использовать древовидную иерархию для ускорения поиска узлов со значениями? Так и происходит: если вспомнить бинарные деревья, то на практике их можно применять в следующих целях:
— поиск данных в базах данных (специально построенных деревьях);
— сортировка и вывод данных;
— вычисления арифметических выражений;
— кодирование по методу Хаффмана и пр.
Все что нужно знать о древовидных структурах данных
Когда вы впервые учитесь кодировать, общепринято изучать массивы в качестве «основной структуры данных».
В конце концов, вы также изучаете хэш-таблицы. Для получения степени по «Компьютерным наукам» (Computer Science) вам придется походить на занятия по структурам данных, на которых вы узнаете о связанных списках, очередях и стеках. Эти структуры данных называются «линейными», поскольку они имеют логические начало и завершение.
Однако в самом начале изучения деревьев и графов мы можем оказаться слегка сбитыми с толку. Нам привычно хранить данные линейным способом, а эти две структуры хранят данные совершенно иначе.
Данная статья поможет вам лучше понять древовидные структуры данных и устранить все недоразумения на их счет.
Из этой статьи вы узнаете:
- Что такое деревья?
- Разберете примеры деревьев.
- Узнаете терминологию и разберете алгоритмы работы с этими структурами.
- Узнаете как реализовать древовидные структуры в программном коде.
Давайте начнем наше учебное путешествие 🙂
Определения
Когда вы только начинаете изучать программирование, обычно бывает проще понять, как строятся линейные структуры данных, чем более сложные структуры, такие как деревья и графы.
Деревья являются широко известными нелинейными структурами. Они хранят данные не линейным способом, а упорядочивают их иерархически.
Давайте вплотную займемся реальными примерами
Что я имею в виду, когда я говорю иерархически?
Представьте себе генеалогическое древо отношений между поколениями: бабушки и дедушки, родители, дети, братья и сестры и т.д. Мы обычно организуем семейные деревья иерархически.
Мое фамильное дерево
Приведенный рисунок — это мое фамильное древо. Тосико, Акикадзу, Хитоми и Такеми — мои дедушки и бабушки.
Тошиаки и Джулиана — мои родители.
ТК, Юдзи, Бруно и Кайо — дети моих родителей (я и мои братья).
Структура организации — еще один пример иерархии.
Структура компании является примером иерархии
В HTML, объектная модель документа (DOM) представляется в виде дерева.
Объектная модель документа (DOM)
HTML-тег содержит другие теги. У нас есть тег заголовка и тег тела. Эти теги содержат определенные элементы. Заголовок имеет мета теги и теги заголовка. Тег тела имеет элементы, которые отображаются в пользовательском интерфейсе, например, h1 , a , li и т.д.
Техническое определение
Дерево представляет собой набор объектов, называемых узлами. Узлы соединены ребрами. Каждый узел содержит значение или данные, и он может иметь или не иметь дочерний узел.
Первый узел дерева называется корнем. Если этот корневой узел соединен с другим узлом, тогда корень является родительским узлом, а связанный с ним узел — дочерним.
Все узлы дерева соединены линиями, называемыми ребрами. Это важная часть деревьев, потому что она управляет связью между узлами.
Листья — это последние узлы на дереве. Это узлы без потомков. Как и в реальных деревьях, здесь имеется корень, ветви и, наконец, листья.
Другими важными понятиями являются высота и глубина.
Высота дерева — это длина самого длинного пути к листу.
Глубина узла — это длина пути к его корню.
Справочник терминов
- Корень — самый верхний узел дерева.
- Ребро — связь между двумя узлами.
- Потомок — узел, имеющий родительский узел.
- Родитель — узел, имеющий ребро, соединяющее его с узлом-потомком.
- Лист — узел, не имеющий узлов-потомков на дереве.
- Высота — это длина самого дальнего пути к листу.
- Глубина — длина пути к корню.
Бинарные деревья
Теперь рассмотрим особый тип деревьев, называемых бинарными или двоичными деревьями.
“В информатике бинарным (двоичным) деревом называется иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.” — Wikipedia
Рассмотрим пример бинарного дерева.
Давайте закодируем бинарное дерево
Первое, что нам нужно иметь в виду, когда мы реализуем двоичное дерево, состоит в том, что это набор узлов. Каждый узел имеет три атрибута: value , left_child , и right_child.
Как мы реализуем простое двоичное дерево, которое инициализирует эти три свойства?
Вот программный код:
Подытоживая изображенное дерево, заметим:
- узел a будет корнем нашего бинарного дерева
- левым потомком a является узел b
- правым потомком a является узел c
- правым потомком b является узел d (узел b не имеет левого потомка)
- левым потомком c является узел e
- правым потомком c является узел f
- оба узла e и f не имеют потомков
Таким образом, вот код для нашего дерева следующий:
Результатом этого алгоритма будет: 1–2–3–4–5–6–7.
Давайте разъясним это подробно.
- Начать с корня (1). Записать.
- Перейти к левому потомку (2). Записать.
- Затем перейти к левому потомку (3). Записать. (Этот узел не имеет потомков)
- Возврат и переход к правому потомку (4). Записать. (Этот узел не имеет потомков)
- Возврат к корневому узлу и переход к правому потомку (5). Записать.
- Переход к левому потомку (6). Записать. (Этот узел не имеет никаких потоков)
- Возврат и переход к правому потомку (7). Записать. (Этот узел не имеет никаких потомков)
- Выполнено.
Проход в глубь дерева, а затем возврат к исходной точке называется алгоритмом DFS.
После знакомства с этим алгоритмом обхода, рассмотрим различные типы DFS-алгоритма: предварительный обход (pre-order), симметричный обход (in-order) и обход в обратном порядке (post-order).
Предварительный обход
Именно это мы и делали в вышеприведенном примере.
1. Записать значение узла.
2. Перейти к левому потомку и записать его. Это выполняется тогда и только тогда, когда имеется левый потомок.
3. Перейти к правому потомку и записать его. Это выполняется тогда и только тогда, когда имеется правый потомок.
Результатом алгоритма симметричного обхода для этого дерева tree в примере является 3–2–4–1–6–5–7.
Первый левый, средний второй и правый последний.
Теперь давайте напишем код.
Результатом алгоритма прохода в обратном порядке для этого примера дерева является 3–4–2–6–7–5–1.
Первое левое, правое второе и последнее посередине.
Давайте напишем для него код.
Вот пример, помогающий лучше объяснить этот алгоритм:
Таким образом мы обходим дерево уровень за уровнем. В этом примере результатом является 1–2–5–3–4–6–7.
- Уровень/Глубина 0: только узел со значением 1.
- Уровень/Глубина 1: узлы со значениями 2 и 5.
- Уровень/Глубина 2: узлы со значениями 3, 4, 6, и 7.
Теперь давайте напишем код.
- Сначала добавить root узел внутрь очереди с помощью метода put .
- Повторять до тех пор пока очередь не пуста.
- Получить первый узел в очереди, а затем записать ее значение.
- Добавить и левый и правый потомок в очередь (если текущий узел имеет потомка).
- Выполнено. Мы будет записывать значение каждого узла, уровень за уровнем с помощью нашей очереди.
Бинарное дерево поиска
“Бинарное (двоичное) дерево поиска иногда называют упорядоченными бинарными деревьями, оно хранит значения упорядоченно, таким образом поиск и другие операции могут строится на принципах бинарного поиска ” — Wikipedia
Важным свойством поиска на двоичном дереве является то, что величина узла Binary Search Tree больше, чем количество его потомков левого элемента-потомка, но меньшее, чем количество его потомков правого элемента-потомка.
Вот детальный разбор приведенной выше иллюстрации.
- A инвертировано. Поддерево subtree 7–5–8–6 должно быть с правой стороны, а поддерево subtree 2–1–3 должно быть слева.
- B является единственной корректной опцией. Оно удовлетворяет свойству Binary Search Tree .
- C имеет одну проблему: узел со значением 4. Он должен быть слева от root потому что меньше 5.
Давайте напишем код для поиска на бинарном дереве!
Наступило время писать код!
Что вы увидите? Мы вставим новые узлы, поищем значения, удалим узлы и сбалансируем дерево.
Вставка: добавление новых узлов на наше дерево
Представьте, что у нас есть пустое дерево, и мы хотим добавить новые узлы со следующими значениями в следующем порядке: 50, 76, 21, 4, 32, 100, 64, 52.
Первое, что нам нужно знать, это то, что 50 является корнем нашего дерева.
Теперь мы можем начать вставлять узел за узлом.
- 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 справа от этого узла node.
- 64 больше чем 50. Узел со значением 50 имеет правого потомка 76. Поскольку 64 меньше чем 76, вставим 64 слева от этого узла.
- 52 больше чем 50. Узел со значением 50 имеет правого потомка 76. Поскольку 52 меньше чем 76, узел со значением 76 имеет левого потомка 64. 52 меньше чем 64, поэтому вставим 54 слева от этого узла.
Вы заметили, что здесь присутствует некоторая структура (патттерн)?
Давайте рассмотрим еще раз более подробно.
- В новом узле значение больше или меньше чем значение текущего узла?
- Если значение нового узла больше чем значение текущего узла, следует перейти на правое поддерево. Если текущий узел не имеет потомка справа, вставить его справа, или в ином случае вернуться к шагу 1.
- Если значение нового узла меньше текущего узла — перейти на левое поддерево. Если текущий узел не имеет левого потомка, вставить его слева, или в ином случае вернуться к шагу 1.
- Мы не рассматривали здесь обработку особых ситуаций. Когда значение нового узла равно значению текущего узла, используется правило 3. Рассмотрим вставку равных значений слева в поддерево.
Давайте напишем код.
Теперь мы хотим узнать есть ли у нас узел со значением 52.
Давайте рассмотрим подробнее.
- Начинаем с корневого узла в качестве текущего. Является ли данная величина меньше текущей величины узла? Если да, будем искать ее на поддереве слева.
- Данное значение больше текущего значения для узла? Если да, будем искать ее справа на поддереве.
- Если правила №1 и №2 оба неверны, можем сравнить значение текущего узла и заданного узла на равенство. Если результат сравнения выдает значение true , можем сказать, «Да!» Наше дерево имеет заданное значение, иначе сказать – нет, оно не имеет.
Давайте напишем код.
Разберем код подробнее:
- Строки 8 и 9 попадают под правило №1.
- Строки 10 и 11 попадают под правило №2.
- Строки 13 попадают под правило №3.
Как нам это проверить?
Давайте создадим наше Binary Search Tree путем инициализации корневого узла значением 15.
А теперь мы вставим много новых узлов.
Для каждого вставленного узла мы проверим работает ли наш метод find_node .
Да, он работает для этих заданных значений! Давайте проверим для значения, отсутствующего в нашем бинарном дереве поиска.
Стирание: удаление и организация
Удаление — более сложный алгоритм, потому что нам нужно обрабатывать разные случаи. Для заданного значения нам нужно удалить узел с этим значением. Представьте себе следующие сценарии для данного узла: у него нет потомков, есть один потомок или есть два потомка.
- Сценарий №1: узел без потомков (листовой узел).
Если узел, который мы хотим удалить, не имеет дочерних элементов, мы просто удалим его. Алгоритм не требует реорганизации дерева.
- Сценарий №2: узел с одним потомком (левый или правый потомок).
В этом случае наш алгоритм должен заставить родительский узел указывать на узел-потомок. Если узел является левым дочерним элементом, мы делаем родительский элемент левого дочернего элемента дочерним. Если узел является правым дочерним по отношению к его родительскому, мы делаем родительский элемент правого дочернего дочерним.
- Сценарий №3: узел с двумя потомками.
Когда узел имеет 2 потомка, нужно найти узел с минимальным значением, начиная с дочернего узла. Мы поставим этот узел с минимальным значением на место узла, который мы хотим удалить.
Пришло время записать код.
- Во-первых: Обратите внимание на значение параметров и родительский. Мы хотим найти узел, который имеет это значение, а родительский узел имеет важное значение для удаления узла.
- Во-вторых: Обратите внимание на возвращаемое значение. Наш алгоритм вернет логическое значение. Он возвращает True, если находит узел и удаляет его. В противном случае он вернет False
- От строки 2 до строки 9: Мы начинаем искать узел, который имеет искомое значение. Если значение меньше текущего значения узла, мы переходим к левому поддереву, рекурсивно (если и только если текущий узел имеет левый дочерний элемент). Если значение больше ‑ перейти в правое поддерево, повторить.
- Строка 10: Начинаем продумывать алгоритм удаления.
- От строки 11 до строки 13: Мы покрываем узел без потомков, и это левый потомок его родителя. Мы удаляем узел, устанавливая левый дочерний элемент родителя в None .
- Строки 14 и 15: Мы покрываем узел без потомков, и это правый потомок его родителя. Мы удаляем узел, установив правый дочерний элемент родителя в None .
- Очистить метод узла: я покажу код clear_node ниже. Он устанавливает дочерние элементы слева, правый дочерний элемент и его значение в None .
- От строки 16 до строки 18: мы покрываем узел только одним потомком (левым дочерним), и это левый потомок его родителя. Мы заменяем левый дочерний элемент родителя на левый дочерний элемент узла (единственный его дочерний элемент).
- От строки 19 до строки 21: мы покрываем узел только одним потомком (левым дочерним), и это правый потомок его родителя. Мы устанавливаем правый дочерний элемент родителя в левый дочерний элемент узла (единственный его дочерний элемент).
- От строки 22 до строки 24: мы покрываем узел только одним потомком (правый ребенок), и это левый дочерний элемент его родителя. Мы устанавливаем левый дочерний элемент родителя правым дочерним элементом узла (единственный его дочерний элемент).
- От строки 25 до строки 27: Мы покрываем узел только одним дочерним элементом (правый дочерний элемент), и это правый потомок его родителя. Устанавливаем правый дочерний элемент родителя правым дочерним элементом узла (единственный его дочерний элемент).
- От строки 28 до строки 30: Мы покрываем узел как левыми, так и правыми потомками. Получаем узел с наименьшим значением (код показан ниже) и устанавливаем его на значение текущего узла. Завершите действия, удалив наименьший узел.
- Строка 32: если мы найдем узел, который ищем, ему нужно снова присвоить True . Код между строками 11 и 31 мы используем именно для этого случая. Так что просто верните значение True , этого будет достаточно.
- Чтобы использовать метод clear_node : установите значение None для всех трех атрибутов — (значения left_child и right_child )
- Чтобы использовать метод find_minimum_value : перейдите влево. Если мы больше не найдем узлов, мы найдем самый маленький.
Теперь давайте проверим.
Будем использовать это дерево для проверки нашего алгоритма remove_node .
Удалим узел со значением 8. Это узел без дочернего элемента.
Теперь давайте удалим узел со значением 17. Это узел с одним потомком.
Наконец, мы удалим узел с двумя потомками. Это корень нашего дерева.
Проверки успешно выполнены 🙂
Пока это все!
Мы с вами уже очень многое изучили.
Поздравляем с завершением чтения и разбора нашей насыщенной информацией и практикой статьи. Всегда довольно сложно понять новую, неизвестную еще концепцию. Но вы читатель, преодолели все трудности 🙂
Это еще один шаг в моем обзоре алгоритмов и моделировании и структур данных. Вы можете найти более полные сведения о моем обзоре в издании Renaissance Developer.
Получайте удовольствие, продолжайте учиться и кодировать.