Npk18.ru

Обучение новым специальностям
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Структуры данных в программировании

Структуры данных

Структуры данных

В 1976 году швейцарец Никлаус Вирт опубликовал книгу «Алгоритмы и структуры данных». Несмотря на то, что после публикации этой книги уже прошло более 40 лет, работа Вирта «Алгоритмы и структуры данных» до сих чрезвычайно актуальна. Это обусловлено тем, что любой разработчик ПО должен прекрасно теоретические основы структур данных. Косвенно это подтверждается тем, что практически на любом ИТ-собеседовании возникает вопрос на данную тематику.

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

Структура базы данных представляет собой контейнер для хранения информация в заданной форме. Такая «компоновка» позволяет этой информации быть эффективной при выполнении одних операций и абсолютно бесполезной для решения других заданий. Главной задачей разработчика считается выбор наилучшего варианта структуры данных для решения определенной задачи.

Назначение структур данных

В IT-разработке именно данные считаются важнейшей сущностью. Для хранения этих данных в максимально организованном виде принято использовать именно структуры. Формат хранения зависит от задач программиста и типа данных. Это может быть заработная плата сотрудников, телефонный справочник, список покупок и т.д. Перечисленные данные могут размещаться в одной из 8 нижеописанных структур.

Самые востребованные структуры данных

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

  • стек;
  • массив;
  • очередь;
  • связный список;
  • дерево;
  • граф;
  • префиксное дерево;
  • хеш-таблица.

Массивы

Массивы считаются самой простой и востребованной структурой. Ниже приведен пример одномерного массива, состоящего из четырех элементов (1, 2, 3, 4).

Каждый элемент массива имеет индекс, соответствующий его позиции. Стоит заметить, что индекс не может быть отрицательным. Также следует сказать, что практически все языки программирования предусматривают начало отчета индексов массива с нуля.

Выше указан одномерный массив, но также существует его многомерный аналог. Простыми словами его можно назвать массивы массивов.

Разработчики имеют возможность осуществлять с массивами самые разные операции, но все-таки чаще всего эта структура данных предусматривает выполнение:

  • вставки;
  • извлечения нужного элемента по индексу;
  • удаления;
  • определения количества элементов в массиве.

Сегодня на IT-собеседованиях вопрос о массивах может прозвучать в первую очередь. Это обусловлено тем, что массивы являются своеобразным фундаментом знаний разработчика. Поэтому при поиске новой работы следует быть готовым к таким вопросам:

  • Как найти минимальный элемент?
  • Как объединить 2 отсортированных массива?
  • Как поменять местами положительные и отрицательные значения?

Стеки

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

Принцип работы «Отменить» заключается в том, что программа поочередно сохраняет предыдущие состояния таким образом, чтобы последнее сохраненное появлялось первым. Массивы не наделены таким функционалом, а потому для реализации работы этой опции принято использовать структуру данных стек.

Для понимания работы стека стоит привести самый тривиальный пример. Предположим, на столе одна на одной лежит куча тетрадок. Чтобы взять тетрадку из середины, необходимо удалить тетрадки, которые лежат сверху. Таким образом работаем принцип «последним пришел – первым ушел. В среде разработчиков этот принцип называется LIFO (Last In First Out).

Ниже приведен пример стека.

Элемент со значением «3» находится в самом верху. Следовательно, он будет удален первым.

Если говорить об операциях со стеками, то прежде всего нужно отметить:

  • вставку элемента в топ;
  • извлечение и последующее удаление верхнего элемента;
  • проверку на пустоту стека;
  • извлечение первого элемента.

На ИТ-собеседованиях программисту стоит быть готовым к таким вопросам:

  • Как отсортировать стек?
  • Как проверить соответствие скобок в выражении?

Очереди

Очередь – линейная структура данных, хранящая элементы в определенной последовательности. В очереди используется принцип «первым пришел – первым ушел» (FIFO).

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

Ниже приведен пример очереди, состоящей из 4 элементов.

В этом примере элемент со значением «1» находится в начале очереди. Следовательно, именно этот элемент первым выйдет из очереди.

К основным действиям с queue стоит отнести:

  • вставку в конец;
  • удаление первого элемента;
  • проверку на пустоту очереди;
  • извлечение первого элемента.

На собеседовании разработчика могут попросить:

  • создать стек посредством очереди;
  • сгенерировать двоичные числа посредством очереди.

Связный список

Создание структуры базы данных также предусматривает использование связных списков. Эта структура очень схожа с массивом. Но все-таки она отличается:

  • организацией;
  • принципом распределения памяти;
  • принцип выполнения операций Insert и Delete.

Связный список представляет собой сеть узлов, содержащих данные и указатель на следующей узел. В связном списке есть указатель на первый элемент (head). Если список будет пуст, head получит значение null.

Главной задачей связных списков является систем хранения файлов. Ниже приведен пример этой структуры:

Связные списки могут быть как одно-, так и двунаправленными. Вне зависимости от типа данной динамической структуры данных, она предусматривает возможность выполнения таких действий:

  • вставка в начало или конец;
  • удаление первого или выбранного элемента;
  • поиск определенного элемента;
  • проверка на пустоту списка.

Во время собеседования разработчика могут попросить выполнить такие задания:

  • удалить дубликаты
  • развернуть список
  • получить заданный узел с конца списка.

Графы

Графы – это набор узлов, соединенных в виде сети. Пара узлов называется ребром, указывающим на то, что вершина одного узла соединена с вершиной другого.

Графы делятся на два типа – ориентированные и неориентированные. В программировании эта структура данных представлена в виде матрицы или списка смежности. Обход графов может осуществляться как в ширину, так и в длину.

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

  • реализация поиска;
  • определение количества ребер;
  • проверка на то является ли граф деревом.

Дерево

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

Именно эта структура используется для создания интеллектуальных машин.

Ниже приведен пример простого дерева:

Стоит добавить, что в программирование существует несколько видов деревьев:

  • N-арное;
  • сбалансированное;
  • бинарное;
  • AVL;
  • красно-черное;
  • 2-3;
  • бинарное дерево поиска.

К наиболее часто задаваемым вопросам по деревьям стоит отнести:

  • определение высоты дерева;
  • поиск максимального значения;
  • поиск предков определенного узла.

Префиксное дерево

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

Ниже приведен пример префиксного дерева.

Объекты поиска указываются сверху вниз. Зеленым цветом выделены элементы, которые показывают конец каждого объекта поиска.

На ИТ-собеседованиях разработчику могут задать такие задания, связанные с префиксными деревьями:

  • создание словаря Т9;
  • определение общего количества элементов;
  • сортировка массива.

Хэш-таблица

Под понятием «хеширование» подразумевается процесс, предназначенный для идентификации объектов и присваивания им уникального ключа. Коллекция объектов – это словарь, в котором можно найти необходимый элемент по ключу.

Производительность хэш-таблиц зависит от следующих нюансов:

  • хеширования;
  • размера;
  • способа обработки коллекций.

Ниже приведен пример, в котором хэш отображается в массиве:

На ИТ-собеседовании разработчику могут быть заданы такие задания:

  • поиск симметричных пар;
  • определение того является ли определенный массив подмножеством другого;
  • проверка массивов на пересекаемость.
Читать еще:  Управление проектами в программировании

Резюмируя, стоит сказать, что вышеописанные 8 структур данных должен знать любой разработчик, желающий успешно пройти IT-собеседование.

Структуры данных: общее понятие, реализация. Простейшие структуры данных: очередь, стек. Использование стека и обратная польская запись

Структуры данных

«Алгоритмы + структуры данных = программы». Это — название книги Никлауса Вирта, знаменитого швейцарского специалиста по программированию, автора языков Паскаль , Модула-2, Оберон. С именем Вирта связано развитие структурного подхода к программированию. Н.Вирт известен также как блестящий педагог и автор классических учебников.

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

Общее понятие структуры данных

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

Структуры данных удобнее всего реализовывать в объектно-ориентированных языках. В них структуре данных соответствует класс , сами данные хранятся в переменных-членах класса (или доступ к данным осуществляется через переменные-члены), системе предписаний соответствует набор методов класса. Как правило, в объектно-ориентированных языках структуры данных реализуются в виде библиотеки стандартных классов: это так называемые контейнерные классы языка C++, входящие в стандартную библиотеку классов STL, или классы, реализующие различные структуры данных из библиотеки Java Developer Kit языка Java .

Тем не менее, структуры данных столь же успешно можно реализовывать и в традиционных языках программирования, таких как Фортран или Си . При этом следует придерживаться объектно-ориентированного стиля программирования: четко выделить набор функций, которые осуществляют работу со структурой данных, и ограничить доступ к данным только этим набором функций. Сами данные реализуются как статические (не глобальные) переменные. При программировании на языке Си структуре данных соответствуют два файла с исходными текстами:

  1. заголовочный, или h-файл, который описывает интерфейс структуры данных, т.е. набор прототипов функций, соответствующий системе предписаний структуры данных;
  2. файл реализации, или Си-файл, в котором определяются статические переменные, осуществляющие хранение и доступ к данным, а также реализуются функции, соответствующие системе предписаний структуры данных

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

Структуры данных и оценка сложности алгоритмов

Тема этой статьи снова касается теории программирования, поэтому придется прибегнуть к различным классификациям и оперировать математическими терминами. Структуры данных – это практически первое, о чем рассказывают в ходе учебных курсов по программированию. Оценка сложности алгоритмов – второе. Может показаться, что эти два вопроса мало связаны, но это не так, и по ходу повествования станет ясно почему. Я не буду углубляться в детали, поскольку практика показывает, что в процессе приобретения опыта в прикладном программировании в голове остается только самое важное. По-моему, так происходит в любой сфере деятельности. Я постараюсь изложить то, что осталось по этим вопросам в голове у меня.

Классификация структур данных

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

  • Линейные
    • Массив
    • Список
    • Связанный список
    • Стек
    • Очередь
    • Хэш-таблица
  • Иерархические
    • Двоичные деревья
    • N-арные деревья
    • Иерархический список
  • Сетевые
    • Простой граф
    • Ориентированный граф
  • Табличные
    • Таблица реляционной базы данных
    • Двумерный массив
  • Другие

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

Линейные структуры данных

Элемент линейной структуры данных характеризуется порядковым номером или индексом в линейной последовательности элементов.

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


Линейный массив.
Адрес(элемент(index)) = размер_ячейки * index.

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

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


Связанный список.

Стек – это динамическая линейная структура данных, для которой определены всего две операции изменения набора элементов: добавление элемента в конец и удаление последнего элемента. Еще говорят, что стек реализует принцип LIFO (Last in, First Out) – последним пришел и первым ушел. Например, в ходе выполнения программного кода, вычислительная машина при необходимости вызвать процедуру или функцию сначала заносит указатель на место ее вызова в стек, чтобы при завершении выполнения ее кода корректно вернуться к следующей после точки вызова инструкции. Такая структура данных называется стеком вызовов подпрограмм.


Стек.

Очередь – очень похожая не стек, динамическая структура данных, с той лишь разницей, что она реализует принцип FIFO (First in, First out) – первым пришел и первым ушел. За примерами в реальной жизни, как понятно из названия, далеко ходить не надо. В программировании с помощью очередей, например, обрабатывают события пользовательского интерфейса, обращения клиентов к веб — сервисам и прочие информационные запросы.


Очередь.

Хэш-таблица – наиболее сложный из динамических линейных структур данных тип. Хэш-таблица оптимизирована для быстрого поиска элементов за счет вычисления адреса элемента, как значения хэш-функции. Аргументом хэш-функции является некий ассоциированный с элементом ключ, например, его порядковый номер. Чтобы гарантировать уникальные значения хэш-функции для уникальных значений ключа (исключить коллизии) хэш-таблица, помимо хитрых алгоритмов, также щедро использует оперативную память. Применение хэш-таблиц должно быть оправдано и тщательно продумано.

Читать еще:  Программирование для android

Иерархические структуры данных

Элемент в иерархической структуре данных характеризуется ссылкой на вышестоящий в иерархии элемент (или ссылками на нижестоящие элементы) и (необязательно) порядковым номером в линейной последовательности своего уровня (иерархические списки).

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

Чтобы вывести элементы в порядке их возрастания, дерево поиска следует обойти в симметричном порядке. Чтобы элементы оказались в обратном порядке, в процессе обхода необходимо поменять порядок посещения поддеревьев.


Двоичное (бинарное) дерево.

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


Иерархический список.

Сетевые структуры данных

Элемент в сетевой структуре данных характеризуется набором связей с другими — соседними элементами. В таких структурах данных ни начальный, ни корневой элементы явно не выделены.

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

Табличные структуры данных

Элемент в табличной структуре данных характеризуется двумерным индексом: индексом строки и индексом столбца, на пересечении которых он находится. Примерами табличных структур данных являются двумерные массивы и таблицы реляционной базы данных.


Табличные структуры данных.

Оценка сложности алгоритмов

Под оценкой сложности алгоритмов подразумевают не интеллектуальные усилия, которые затратили авторы при их разработке, а зависимость количества элементарных операций, выполняемых вычислительной машиной от объема обрабатываемой информации. Например, как будет зависеть число сравнений двух чисел от длины исходной последовательности в процессе работы алгоритма сортировки. Я намеренно немного сузил определение, поскольку в дальнейшем речь будет идти только о количестве элементарных операций. На самом деле сложность алгоритма определяется не только количеством операций, но и объемом привлеченных для решения задачи вычислительных ресурсов, и в первую очередь, оперативной памяти. Чем проще алгоритм, тем он, скорее всего, дольше работает. Сложные и быстрые алгоритмы зачастую используют вспомогательные структуры данных, и, как следствие, расходуют дополнительную память. Закон сохранения энергии или “за все надо платить”. Один из примеров “предельной оптимизации” был рассмотрен ранее – это хэш-таблица. Я лично не знаю, как устроена хэш-таблица и как выглядят хэш-функции (догадываюсь, что не просто), но зато время поиска элементов по ключу практически не зависит от размера таблицы. Далее немного теории.

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

Асимптотическая оценка сложности обозначается греческой буквой Θ (тета).

f(n) = Θ(g(n)), если существуют c1, c2>0 и n0 такие, что c1*g(n) n0.

Функция g(n) является асимптотически точной оценкой сложности алгоритма — функции f(n), приведенное неравенство называется асимптотическим равенством, а само обозначение Θ символизирует множество функций, которые растут “так же быстро”, как и функция g(n) – т.е. с точностью до умножения на константу. Как следует из приведенного неравенства, оценка Θ являет собой одновременно и верхнюю и нижнюю оценки сложности. Не всегда есть возможность получить оценку в таком виде, поэтому верхнюю и нижнюю оценки иногда определяют отдельно.

Верхняя оценка сложности обозначается греческой буквой Ο (омикрон), и является множеством функций, которые растут не быстрее, чем g(n).

f(n)= Ο(g(n)), если существует c>0 и n0 такие, что 0 n0.

Нижняя оценка сложности обозначается греческой буквой Ω (омега), и является множеством функций, которые растут не медленнее, чем g(n).

f(n)= Ω(g(n)), если существует c>0 и n0 такие, что 0 n0.

Как следствие: асимптотическая оценка существует только в том случае, если совпадают нижняя и верхняя оценки сложности алгоритма. В практике анализа алгоритмов чаще всего под оценкой сложности понимают верхнюю оценку сложности. Это вполне логично, поскольку наиболее важна оценка времени, за которое алгоритм гарантировано закончит работу, а не время, в пределах которого он точно не завершится.

Работа с линейными структурами данных

Ну и в заключении я приведу оценки сложности основных операций с линейными структурами данных, а именно добавление, удаление и поиск элемента по индексу или ключу. Элементарными операциями, в данном случае, являются операции сравнения, перебора, вычисления адреса или перестановки элементов набора структуры данных. В сводной таблице, помимо верхней оценки сложности, также приведены соответствующие перечисленным структурам данных компоненты библиотеки BCL. Таким образом, основные линейные структуры данных уже есть в готовом виде и доступны всем разработчикам программного обеспечения на платформе Microsoft .NET Framework.

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

Деревья прекрасны. Вот рисунок, который я сделал ребенком

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

В конце концов, вы также изучаете хэш-таблицы. Для получения степени по «Компьютерным наукам» (Computer Science) вам придется походить на занятия по структурам данных, на которых вы узнаете о связанных списках, очередях и стеках. Эти структуры данных называются «линейными», поскольку они имеют логические начало и завершение.

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

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

Из этой статьи вы узнаете:

  • Что такое деревья?
  • Разберете примеры деревьев.
  • Узнаете терминологию и разберете алгоритмы работы с этими структурами.
  • Узнаете как реализовать древовидные структуры в программном коде.

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

Определения

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

Читать еще:  Сайты по программированию

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

Давайте вплотную займемся реальными примерами

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

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

Мое фамильное дерево

Приведенный рисунок — это мое фамильное древо. Тосико, Акикадзу, Хитоми и Такеми — мои дедушки и бабушки.

Тошиаки и Джулиана — мои родители.

ТК, Юдзи, Бруно и Кайо — дети моих родителей (я и мои братья).

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

Структура компании является примером иерархии

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

Объектная модель документа (DOM)

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

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

Дерево представляет собой набор объектов, называемых узлами. Узлы соединены ребрами. Каждый узел содержит значение или данные, и он может иметь или не иметь дочерний узел.

Первый узел дерева называется корнем. Если этот корневой узел соединен с другим узлом, тогда корень является родительским узлом, а связанный с ним узел — дочерним.

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

Листья — это последние узлы на дереве. Это узлы без потомков. Как и в реальных деревьях, здесь имеется корень, ветви и, наконец, листья.

Другими важными понятиями являются высота и глубина.

Высота дерева — это длина самого длинного пути к листу.

Глубина узла — это длина пути к его корню.

Справочник терминов

  • Корень — самый верхний узел дерева.
  • Ребро — связь между двумя узлами.
  • Потомок — узел, имеющий родительский узел.
  • Родитель — узел, имеющий ребро, соединяющее его с узлом-потомком.
  • Лист — узел, не имеющий узлов-потомков на дереве.
  • Высота — это длина самого дальнего пути к листу.
  • Глубина — длина пути к корню.

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

Теперь рассмотрим особый тип деревьев, называемых бинарными или двоичными деревьями.

“В информатике бинарным (двоичным) деревом называется иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.” — Wikipedia

Рассмотрим пример бинарного дерева.

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

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

Как мы реализуем простое двоичное дерево, которое инициализирует эти три свойства?

Вот наш двоичный класс дерева.

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

Когда мы создаем наш узел, он не имеет потомков. Просто есть данные узла.

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

Это выглядит так.

Мы можем передать строку ‘ a ’ в качестве значения нашему узлу бинарного дерева. Если мы напечатаем значение, left_child и right_child , мы увидим значения.

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

Мы реализуем метод вставки нового узла справа и слева.

  • Если у текущего узла нет левого дочернего элемента, мы просто создаем новый узел и устанавливаем его в left_child текущего узла.
  • Если у него есть левый дочерний потомок, мы создаем новый узел и помещаем его вместо текущего левого потомка. Назначьте этот левый дочерний узел новым левым дочерним новым узлом.

Давайте это нарисуем 🙂

Вот программный код:

Еще раз, если текущий узел не имеет левого дочернего элемента, мы просто создаем новый узел и устанавливаем его в качестве left_child текущего узла. Или мы создаем новый узел и помещаем его вместо текущего левого потомка. Назначим этот левый дочерний узел в качестве левого дочернего элемента нового узла.

И мы делаем то же самое, чтобы вставить правый дочерний узел.

Но не полностью. Осталось протестировать.

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

Подытоживая изображенное дерево, заметим:

  • узел a будет корнем нашего бинарного дерева
  • левым потомком a является узел b
  • правым потомком a является узел c
  • правым потомком b является узел d (узел b не имеет левого потомка)
  • левым потомком c является узел e
  • правым потомком c является узел f
  • оба узла e и f не имеют потомков

Таким образом, вот код для нашего дерева следующий:

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

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

Поиск в глубину (Depth-first search, DFS) — один из методов обхода дерева. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» дерева, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в не рассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из не рассмотренных вершин.

Поиск в ширину (breadth-first search, BFS) — метод обхода дерева и поиска пути. Поиск в ширину является одним из неинформированных алгоритмов поиска. Поиск в ширину работает путём последовательного просмотра отдельных уровней дерева, начиная с узла-источника. Рассмотрим все рёбра, выходящие из узла. Если очередной узел является целевым узлом, то поиск завершается; в противном случае узел добавляется в очередь. После того, как будут проверены все рёбра, выходящие из узла, из очереди извлекается следующий узел, и процесс повторяется.

Давайте подробно рассмотрим каждый из алгоритмов обхода.

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

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

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

Давайте разъясним это подробно.

  1. Начать с корня (1). Записать.
  2. Перейти к левому потомку (2). Записать.
  3. Затем перейти к левому потомку (3). Записать. (Этот узел не имеет потомков)
  4. Возврат и переход к правому потомку (4). Записать. (Этот узел не имеет потомков)
  5. Возврат к корневому узлу и переход к правому потомку (5). Записать.
  6. Переход к левому потомку (6). Записать. (Этот узел не имеет никаких потоков)
  7. Возврат и переход к правому потомку (7). Записать. (Этот узел не имеет никаких потомков)
  8. Выполнено.

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

После знакомства с этим алгоритмом обхода, рассмотрим различные типы DFS-алгоритма: предварительный обход (pre-order), симметричный обход (in-order) и обход в обратном порядке (post-order).

Предварительный обход

Именно это мы и делали в вышеприведенном примере.

1. Записать значение узла.

2. Перейти к левому потомку и записать его. Это выполняется тогда и только тогда, когда имеется левый потомок.

3. Перейти к правому потомку и записать его. Это выполняется тогда и только тогда, когда имеется правый потомок.

Ссылка на основную публикацию
Adblock
detector