40_алгоритмы - 2гл структуры данных.pdf

2 Структуры данных, используемые в алгоритмах https://t.me/it_boooks Во время работы алгоритму необходима структура данных, чтобы хранить вре­ менные данные в памяти. Выбор подходящей структуры имеет ключевое зна­ чение для эффективной реализации алгоритма. Определенные классы алгорит­ мов являют...

2 Структуры данных, используемые в алгоритмах https://t.me/it_boooks Во время работы алгоритму необходима структура данных, чтобы хранить вре­ менные данные в памяти. Выбор подходящей структуры имеет ключевое зна­ чение для эффективной реализации алгоритма. Определенные классы алгорит­ мов являются рекурсивными или итеративными по своей логике и нуждаются в специально разработанных структурах данных. Например, добиться хорошей производительности рекурсивного алгоритма проще, если использовать вло­ женные структуры. Поскольку в книге мы используем Python, эта глава будет посвящена структурам данных Python. Однако эти знания пригодятся и для работы с другими языками, такими как Java и C++. Прочтя эту главу, вы узнаете, как именно Python обрабатывает сложные струк­ туры данных и какие из них используются для определенного типа данных. В этой главе нас ждут: zz Структуры данных в Python. zz Абстрактные типы данных. zz Стеки и очереди. zz Деревья. Структуры данных в Python 51 СТРУКТУРЫ ДАННЫХ В PYTHON В любом языке программирования структуры данных используются для хранения и управления сложными данными. В Python структуры данных — это контейнеры, позволяющие эффективно управлять данными, организо­ вывать их и осуществлять поиск. Они организованы в коллекции — группы элементов данных, которые требуется хранить и обрабатывать совместно. В Python существуют пять различных структур данных для хранения кол­ лекций: zz Список (List). Упорядоченная изменяемая последовательность элементов. zz Кортеж (Tuple). Упорядоченная неизменяемая последовательность элемен­ тов. zz Множество (Set). Неупорядоченная последовательность элементов. zz Словарь (Dictionary). Неупорядоченная последовательность пар «ключ — значение». zz DataFrame. Двумерная структура для хранения двумерных данных. Давайте рассмотрим их более подробно. Список В Python список — это основная структура данных, используемая для хранения изменяемой последовательности элементов. Элементы данных в списке могут быть разных типов. Чтобы создать список, элементы нужно заключить в квадратные скобки [ ] и разделить запятыми. Ниже представлен пример кода, который создает список из четырех элементов данных разных типов: >>> aList = ["John", 33,"Toronto", True] >>> print(aList) ['John', 33, 'Toronto', True]Ex Список в Python — это удобный способ создания одномерных изменяемых структур данных, необходимых главным образом на различных внутренних этапах алгоритма. 52 Глава 2. Структуры данных, используемые в алгоритмах Использование списков При работе со списками мы получаем полезные инструменты для управления данными. Давайте посмотрим, что можно делать со списками. zz Индексация списка. Поскольку положение каждого элемента в списке детер­ минировано, к нему можно получить доступ с помощью индекса. Следующий код демонстрирует этот принцип: >>> bin_colors=['Red','Green','Blue','Yellow'] >>> bin_colors 'Green' Список из четырех элементов, созданный этим кодом, показан на рис. 2.1. Значения Индексы Рис. 2.1 Обратите внимание, что индексация начинается с 0, поэтому второй элемент Green извлекается с помощью индекса 1: bin_color. zz Срез списка. Извлечение подмножества элементов списка путем указания диапазона индексов называется срезом. Пример кода среза: >>> bin_colors=['Red','Green','Blue','Yellow'] >>> bin_colors[0:2] ['Red', 'Green'] Cписок — одна из самых популярных одномерных структур данных в Python. При срезе списка диапазон указывается следующим образом: первое число (включительно) и второе число (не включительно). Напри­ мер, bin_colors[0:2] будет включать bin_color и bin_color, но не bin_color. Следует учитывать это при использовании списков; не­ которые пользователи Python жалуются, что это не слишком очевидно. Структуры данных в Python 53 Рассмотрим следующий сниппет: >>> bin_colors=['Red','Green','Blue','Yellow'] >>> bin_colors[2:] ['Blue', 'Yellow'] >>> bin_colors[:2] ['Red', 'Green'] Если в квадратных скобках не указан первый индекс‚ это означает начало списка, а если пропущен второй — конец списка. Выше мы видим пример та­ кого кода. zz Отрицательная индексация. В Python имеются и отрицательные индек­ сы, которые отсчитываются от конца списка. Это показано в следующем коде: >>> bin_colors=['Red','Green','Blue','Yellow'] >>> bin_colors[:-1] ['Red', 'Green', 'Blue'] >>> bin_colors[:-2] ['Red', 'Green'] >>> bin_colors[-2:-1] ['Blue'] Отрицательные индексы особенно полезны, когда в качестве точки отсчета мы хотим использовать последний элемент вместо первого. zz Вложенность. Элемент списка может относиться к простому или сложному типу данных. Это позволяет создавать вложенные списки и дает возможность использовать потенциал итеративных и рекурсивных алгоритмов. Рассмотрим пример списка внутри списка (вложенность): >>> a = [1,2,[100,200,300],6] >>> max(a) 300 >>> a 200 zz Итерация. Python позволяет выполнять итерацию для каждого элемента в списке с помощью цикла for. Это показано в следующем примере: >>> bin_colors=['Red','Green','Blue','Yellow'] >>> for aColor in bin_colors: print(aColor + " Square") Red Square Green Square Blue Square Yellow Square 54 Глава 2. Структуры данных, используемые в алгоритмах Обратите внимание, что данный код выполняет итерацию по списку и ото­ бражает каждый элемент. Лямбда-функции Существует множество лямбда-функций, которые можно использовать в списках. Они особенно полезны в работе с алгоритмами и позволяют создавать функцию на лету. Иногда в литературе их также называют анонимными функциями. Рас­ смотрим их применение: zz Фильтрация данных. Для фильтрации данных мы должны определить пре­ дикат — функцию, которая тестирует каждый аргумент и возвращает логи­ ческое значение. Пример использования такой функции: >>> list(filter(lambda x: x > 100, [-5, 200, 300, -10, 10, 1000])) [200, 300, 1000] В данном коде мы фильтруем список с помощью лямбда-функции, которая задает критерии фильтрации. Функция filter() предназначена для отбора элементов из последовательности на основе определенного критерия и обыч­ но используется вместе с лямбда-функцией. Ее также можно применять для фильтрации элементов кортежей или наборов. В нашем примере заданным критерием является x > 100. Код проверяет все элементы списка и отсеивает те из них, которые не соответствуют этому критерию. zz Преобразование данных. Функция map() используется для преобразования данных с помощью лямбда-функции. Пример: >>> list(map(lambda x: x ** 2, [11, 22, 33, 44,55])) [121, 484, 1089, 1936, 3025] Использование функции map() вместе с лямбда-функцией открывает большие возможности. При этом лямбда-функция задает преобразователь, изменяющий каждый элемент последовательности. В приведенном примере преобразова­ телем выступает возведение во вторую степень. Таким образом, мы использу­ ем функцию map() для получения квадрата каждого элемента в списке. zz Агрегирование данных. Для агрегирования данных используется reduce(), которая рекурсивно применяет функцию к паре значений для каждого эле­ мента списка: from functools import reduce def doSum(x1,x2): return x1+x2 x = reduce(doSum, [100, 122, 33, 4, 5, 6]) Структуры данных в Python 55 Обратите внимание, что для reduce() необходимо определить функцию агрегирования данных. В приведенном примере кода такой функцией явля­ ется functools. Она определяет, как именно нужно агрегировать элементы данного списка. Агрегирование начинается с первых двух элементов, а его результат заменяет эти два элемента. Процесс сокращения будет происходить до тех пор, пока не останется одно агрегированное число. x1 и x2 в функции doSum() представляют собой пару чисел для каждой итерации; doSum() яв­ ляется критерием агрегирования. В результате мы получаем единое значение (равное 270). Функция range С помощью функции range() можно легко сгенерировать большой список чисел. Она используется для автоматического добавления последовательностей чисел в список. Функцию range() очень просто использовать — нужно только указать коли­ чество элементов, которые мы хотим видеть в списке. По умолчанию после­ довательность начинается с нуля и далее увеличивается с шагом, равным единице: >>> x = range(6) >>> x [0,1,2,3,4,5] Мы также можем указать конечное число и шаг, например: >>> oddNum = range(3,29,2) >>> oddNum [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27] В результате получим нечетные числа от 3 до 27. Временная сложность списков Временную сложность различных функций списка можно обобщить, используя нотацию «О-большое» (табл. 2.1). Чем больше список, тем больше времени требуется на выполнение операций, представленных в таблице. Это не касается только вставки элемента. По мере увеличения списка влияние на производительность становится все более вы­ раженным. 56 Глава 2. Структуры данных, используемые в алгоритмах Таблица 2.1 Операция Временная сложность Вставить элемент O(1) Удалить элемент O(n) (так как в худшем случае, возможно, придется перебрать весь список) Срез списка O(n) Извлечение O(n) элемента Копирование O(n) Кортеж Еще одна структура данных, которую можно использовать для хранения кол­ лекции, — кортеж. В отличие от списков, кортежи являются неизменяемыми (доступными только для чтения) структурами данных. Кортежи состоят из нескольких элементов, заключенных в круглые скобки ( ). Кортежи, как и списки, могут включать в себя элементы разных типов, в том числе сложные типы данных — внутри кортежа может быть еще один кортеж. Таким образом, мы можем создавать вложенные структуры. Это особенно по­ лезно для работы с итеративными и рекурсивными алгоритмами. В данном коде показано, как создавать кортежи: >>> bin_colors=('Red','Green','Blue','Yellow') >>> bin_colors 'Green' >>> bin_colors[2:] ('Blue', 'Yellow') >>> bin_colors[:-1] ('Red', 'Green', 'Blue') # Nested Tuple Data structure (вложенный кортеж) >>> a = (1,2,(100,200,300),6) >>> max(a) 300 >>> a 200 Обратите внимание, что в представленном выше коде а относится к третье­ му элементу, который является кортежем: (100,200,300); a относится ко второму элементу внутри этого кортежа, который является числом 200. Структуры данных в Python 57 По возможности старайтесь использовать неизменяемые структуры данных вместо изменяемых (например, кортежи вместо списков), так как это улучшит производительность. В особенности это касается обработки больших данных: неизменяемые структуры работают зна­ чительно быстрее, чем изменяемые. Мы платим определенную цену за возможность изменять элементы данных в списке. Нужно понять, действительно ли это необходимо или же можно использовать кортеж, что будет намного быстрее. Временная сложность кортежей Временную сложность различных функций кортежей можно обобщить с по­ мощью «O-большого» (табл. 2.2). Таблица 2.2 Функция Временная сложность Append() O(1) Append() — это функция, которая добавляет элемент в конец уже существую­ щего кортежа. Ее сложность равна O(1). Словарь Хранение данных в виде пар «ключ — значение» особенно полезно при работе с распределенными алгоритмами. В Python коллекция пар «ключ — значение» хранится в виде структуры данных, называемой словарем. Чтобы создать сло­ варь, в качестве атрибута следует выбрать ключ, лучше всего подходящий для идентификации данных во время обработки. Значением ключа может быть элемент любого типа, например число или строка. В Python в качестве значе­ ний также используются сложные типы данных, например списки. Если ис­ пользовать в качестве значения ключа словарь, можно создавать вложенные словари. Чтобы создать простой словарь, который присваивает цвета различным пере­ менным, пары «ключ — значение» должны быть заключены в фигурные скобки { }. Например, следующий код создает простой словарь, состоящий из трех пар «ключ — значение»: >>> bin_colors ={ "manual_color": "Yellow", 58 Глава 2. Структуры данных, используемые в алгоритмах "approved_color": "Green", "refused_color": "Red" } >>> print(bin_colors) {'manual_color': 'Yellow', 'approved_color': 'Green', 'refused_color': 'Red'} Три пары «ключ — значение», созданные предыдущим фрагментом кода, также проиллюстрированы на рис. 2.2. Ключи Значения Рис. 2.2 Теперь давайте посмотрим, как получить и обновить значение, связанное с ключом. 1. Чтобы получить значение, связанное с ключом, можно использовать либо функцию get(), либо ключ в качестве индекса: >>> bin_colors.get('approved_color') 'Green' >>> bin_colors['approved_color'] 'Green' 2. Чтобы обновить значение, связанное с ключом, используйте следующий код: >>> bin_colors['approved_color']="Purple" >>> print(bin_colors) {'manual_color': 'Yellow', 'approved_color': 'Purple', 'refused_color': 'Red'} Данный код показывает, как обновить значение, связанное с определенным ключом в словаре. Структуры данных в Python 59 Временная сложность словаря В табл. 2.3 приведена временная сложность словаря с использованием «O-большого». Таблица 2.3 Операция Временная сложность Получить значение или ключ O(1) Установить значение или ключ O(1) Скопировать словарь O(n) Из анализа сложности словаря следует важный вывод: время, необходимое для получения или установки значения ключа, никак не зависит от размера словаря. Это означает, что время, затраченное на добавление пары «ключ — значение» в словарь размером три (например), равно времени, затраченному на добавление пары «ключ — значение» в словарь размером один миллион. Множество Множество — это коллекция элементов одного или разных типов. Элементы заключены в фигурные скобки { }. Взгляните на следующий сниппет: >>> green = {'grass', 'leaves'} >>> print(green) {'grass', 'leaves'} Отличительной особенностью множества является то, что в нем хранится толь­ ко уникальное значение каждого элемента. Если мы попытаемся добавить дубль, он будет проигнорирован: >>> green = {'grass', 'leaves','leaves'} >>> print(green) {'grass', 'leaves'} Рассмотрим операции над множествами. Для этого возьмем два множества: zz множество с именем yellow, в котором содержатся вещи желтого цвета; zzмножество с именем red, в котором содержатся вещи красного цвета. 60 Глава 2. Структуры данных, используемые в алгоритмах Обратите внимание, что некоторые вещи содержатся в обоих множествах. Эти два множества и их взаимосвязь можно представить с помощью диаграммы Венна (рис. 2.3). Рис. 2.3 (dandelions — одуванчики, leaves — листья, fire hydrant — пожарный кран, rose — роза, blood — кровь) Реализация этих множеств в Python выглядит следующим образом: >>> yellow = {'dandelions', 'fire hydrant', 'leaves'} >>> red = {'fire hydrant', 'blood', 'rose', 'leaves'} Теперь рассмотрим код, который демонстрирует операции на множествах с ис­ пользованием Python: >>> yellow|red {'dandelions', 'fire hydrant', 'blood', 'rose', 'leaves'} >>> yellow&red {'fire hydrant'} В данном примере продемонстрированы две операции: объединение и пересе­ чение. Объединение совмещает все элементы обоих множеств, а пересечение дает набор общих элементов для двух множеств. Обратите внимание: zz yellow|red используется для объединения двух множеств; zz yellow&red используется для получения пересечения yellow и red. Анализ временной сложности множеств В табл. 2.4 приведен анализ временной сложности для множеств. Структуры данных в Python 61 Таблица 2.4 Операция Сложность Добавление элемента O(1) Удаление элемента O(1) Копирование O(n) На основании анализа сложности можно сделать вывод, что время, затраченное на добавление элемента, не зависит от размера конкретного множества. DataFrame DataFrame — табличная структура данных, доступная в библиотеке Python pandas. Это одна из наиболее важных структур данных для алгоритмов. Она используется для обработки классических структурированных данных. Рас­ смотрим таблицу (табл. 2.5). Таблица 2.5 id name (имя) age (возраст) decision (решение) 1 Fares 32 True 2 Elena 23 False 3 Steven 40 True Теперь представим эту таблицу с помощью DataFrame. Простейший DataFrame может быть создан с помощью следующего кода: >>> import pandas as pd >>> df = pd.DataFrame([... ['1', 'Fares', 32, True],... ['2', 'Elena', 23, False],... ['3', 'Steven', 40, True]]) >>> df.columns = ['id', 'name', 'age', 'decision'] >>> df id name age decision 0 1 Fares 32 True 1 2 Elena 23 False 2 3 Steven 40 True 62 Глава 2. Структуры данных, используемые в алгоритмах Обратите внимание, что в данном коде df.column — это список, в котором со­ держатся имена столбцов. DataFrame используются и в других популярных языках и фреймвор­ ках для реализации табличной структуры данных. Примерами могут служить язык программирования R и платформа Apache Spark. Терминология DataFrame Ознакомимся с терминологией, необходимой для работы с DataFrame: zz Ось. В документации pandas один столбец или строка DataFrame называется осью (axis). zz Метка. DataFrame позволяет отмечать как столбцы, так и строки так назы­ ваемой меткой (label). Создание подмножества DataFrame По сути, существуют два основных способа создания подмножества DataFrame (пусть это будет подмножество с именем myDF): zz выбор столбца; zzвыбор строки. Рассмотрим их по очереди. Выбор столбца При работе с алгоритмами машинного обучения важно использовать правиль­ ный набор признаков. Далеко не все доступные нам признаки могут понадо­ биться на разных этапах алгоритма. В Python отбор признаков происходит путем выбора столбцов. Получить доступ к столбцу можно с помощью его имени (атрибута name), как показано ниже: >>> df[['name','age']] name age 0 Fares 32 1 Elena 23 2 Steven 40 Позиция столбца является детерминированной. Доступ к нему по его располо­ жению можно получить следующим образом: Структуры данных в Python 63 >>> df.iloc[:,3] 0 True 1 False 2 True Обратите внимание, что в этом коде мы извлекаем первые три строки DataFrame. Выбор строки Каждая строка DataFrame соответствует точке данных в пространстве задачи. Чтобы создать подмножество из имеющихся элементов данных, необходимо выбрать строки. Существуют два метода создания подмножества: zz указать расположение строк; zzзадать критерии фильтра. Подмножество строк может быть получено по расположению следующим об­ разом: >>> df.iloc[1:3,:] id name age decision 1 2 Elena 23 False 2 3 Steven 40 True Данный код вернет первые две строки и все столбцы. Чтобы создать подмножество с помощью фильтра‚ мы должны указать критерии выбора в одном или нескольких столбцах. Это происходит следующим образом: >>> df[df.age>30] id name age decision 0 1 Fares 32 True 2 3 Steven 40 True >>> df[(df.age>> myMatrix = np.array([[11, 12, 13], [21, 22, 23], [31, 32, 33]]) >>> print(myMatrix) [[11 12 13] [21 22 23] [31 32 33]] >>> print(type(myMatrix)) Этот код создает матрицу, содержащую три строки и три столбца. Операции с матрицами Существует множество операций, доступных для матричных данных. Давай­ те транспонируем матрицу из предыдущего примера. Для этого использу­ ем функцию transpose(), которая преобразует столбцы в строки, а строки в столбцы: >>> myMatrix.transpose() array([[11, 21, 31], [12, 22, 32], [13, 23, 33]]) Отметим, что матричные операции часто используются при обработке мульти­ медийных данных. Теперь, когда мы узнали о структурах данных в Python, перейдем к абстрактным типам данных. АБСТРАКТНЫЕ ТИПЫ ДАННЫХ В широком смысле абстракция — принцип, используемый для определения сложных систем с точки зрения их общих базовых функций. Применение этой концепции при создании структур данных приводит к появлению абстракт- ных типов данных (AТД1). Используя АТД, мы получаем универсальную, независимую от реализации структуру данных. Это позволяет написать более простой и чистый код алгоритма, не углубляясь в детали разработки. АТД ­можно реализовать на любом языке программирования, например C++, Java и Scala. В этом разделе мы будем использовать АТД в Python. Начнем с вектора. 1 Или ADT (Abstract Data Type). — Примеч. ред. Абстрактные типы данных 65 Вектор Вектор — это одномерная структура для хранения данных‚ одна из самых по­ пулярных в Python. В Python имеются два способа создания векторов. zz Использование списка Python. Самый простой способ создания вектора — применить список Python следующим образом: >>> myVector = [22,33,44,55] >>> print(myVector) [22 33 44 55] >>> print(type(myVector)) Этот код создает список из четырех элементов. zz Использование массива numpy. Еще один популярный способ создания век­ тора — применение массивов NumPy, как показано ниже: >>> myVector = np.array([22,33,44,55]) >>> print(myVector) [22 33 44 55] >>> print(type(myVector)) Обратите внимание, что мы создали MyVector, используя np.array. В Python мы используем нижнее подчеркивание при написании це­ лых чисел, разделяя их на разряды. Это делает их удобочитаемыми и уменьшает вероятность ошибки‚ что особенно важно при работе с большими числами. Например, один миллиард можно представить так: a=1_000_000_000. Стек Стек — это линейная структура данных для хранения одномерного списка. Элементы в стеке могут обрабатываться по принципу LIFO (Last-In, First-Out: «последним пришел — первым ушел») либо по принципу FILO (First-In, Last-Out: «первым пришел — последним ушел». Порядок добавления и удаления элементов определяет характер стека. Новые элементы могут добавляться и удаляться только с одного конца списка. Ниже приведены операции со стеками: zz isEmpty. Возвращает true, если стек пуст; 66 Глава 2. Структуры данных, используемые в алгоритмах zz push. Добавляет новый элемент; zzpop. Возвращает элемент, добавленный последним, и удаляет его. На рис. 2.4 показано, как операции push() и pop() можно использовать для до­ бавления и удаления данных из стека. Cтек Рис. 2.4 В верхней части рис. 2.4 показано использование операции push() для добавле­ ния элементов в стек. На шагах 1.1, 1.2 и 1.3 операция push() используется три раза для добавления трех элементов в стек. В нижней части рисунка демонстри­ руется извлечение сохраненных значений из стека. На шагах 2.2 и 2.3 операция pop() используется для извлечения двух элементов из стека в формате LIFO. Давайте создадим класс с именем Stack‚ в котором опишем все операции, свя­ занные с классом stack. Код этого класса будет выглядеть следующим образом: class Stack: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): Абстрактные типы данных 67 return self.items[len(self.items)-1] def size(self): return len(self.items) Чтобы поместить четыре элемента в стек, можно использовать следующий код (рис. 2.5). Рис. 2.5 Этот код создает стек с четырьмя элементами данных. Временная сложность стеков Рассмотрим временную сложность стеков, используя «O-большое» (табл. 2.6). Таблица 2.6 Операция Временная сложность push O(1) pop O(1) size O(1) peek O(1) Видим, что производительность этих четырех операций не зависит от размера стека. 68 Глава 2. Структуры данных, используемые в алгоритмах Практический пример Стек часто применяется на практике в качестве структуры данных. Например, он используется для хранения истории веб-браузера. Другой пример — выпол­ нение операции Undo при работе с текстом. Очередь Как и стек, очередь хранит n элементов в одномерной структуре. Элементы до­ бавляются и удаляются по принципу FIFO (First-In, First-Out: «первым при- шел — первым ушел»). Каждая очередь имеет начало и конец. Когда элементы удаляются из начала, операция называется удалением из очереди — dequeue. Когда элементы добавляются в конец, операция называется постановкой в оче- редь — enqueue. На следующей диаграмме (рис. 2.6) в верхней части показана операция enqueue(). Шаги 1.1, 1.2 и 1.3 добавляют три элемента в очередь; итоговая очередь показа­ на на шаге 1.4. Обратите внимание, что Yellow — в конце, а Red — в начале. В нижней части диаграммы представлена операция dequeue(). Шаги 2.2, 2.3 и 2.4 удаляют элементы из начала очереди один за другим. Очередь Рис. 2.6 Абстрактные типы данных 69 Эта очередь может быть реализована с помощью следующего кода: class Queue(object): def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def enqueue(self, item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def size(self): return len(self.items) С помощью скриншота на рис. 2.7 выполним постановку и удаление элементов из очереди, как это показано на диаграмме выше. Рис. 2.7 Обратите внимание, что код сначала создает очередь, а затем помещает в нее четыре элемента. 70 Глава 2. Структуры данных, используемые в алгоритмах Базовый принцип использования стеков и очередей Рассмотрим базовый принцип использования стеков и очередей с помощью аналогии. Представьте, что мы получаем почтовую корреспонденцию и скла­ дываем ее на стол. Письма накапливаются в стопки, пока мы не находим время, чтобы открыть и просмотреть их одно за другим. Есть два способа сделать это: zz Мы складываем письма в стопку, и всякий раз, когда мы получаем новое письмо, мы кладем его наверх. Когда мы хотим прочитать письма, мы на­ чинаем с того, которое лежит сверху. Стопка — это то, что мы называем стеком. Обратите внимание, что последнее поступившее письмо находится сверху и будет обработано первым. Взять письмо из верхней части стопки означает выполнить операцию pop. Положить новое письмо сверху — вы­ полнить операцию push. Если в итоге у нас получится большая стопка‚ а письма продолжат приходить, то есть вероятность, что мы никогда не до­ беремся до очень важного письма в самом низу. zz Мы складываем письма в стопку, но сначала хотим открыть самое старое письмо: каждый раз, когда мы хотим просмотреть одно или несколько писем, мы начинаем с более старых. Это — очередь. Добавление письма в стопку — операция enqueue (постановка в очередь). Удаление письма из стопки — опе­ рация dequeue (удаление из очереди). Дерево Дерево — иерархическая структура данных, что делает ее особенно полезной при разработке алгоритмов. Мы используем деревья везде, где требуются иерархи­ ческие отношения между элементами данных. Давайте подробнее рассмотрим эту интересную и важную структуру. Каждое дерево имеет конечный набор узлов, так что в нем есть начальный эле­ мент данных, называемый корнем (root), и набор узлов, соединенных между собой ветвями (branches). Терминология Рассмотрим некоторые термины, связанные с древовидной структурой данных (табл. 2.7). Абстрактные типы данных 71 Таблица 2.7 Корневой узел Узел без родителя называется корневым узлом. Например, на (Root node) следующей диаграмме (рис. 2.8) корневым узлом служит A. В алгоритмах корневой узел, как правило, содержит наиболее важное значение во всей древовидной структуре Уровень узла Расстояние от корневого узла называется уровнем узла. (Level of a node) На следующей диаграмме уровень узлов D, E и F равен двум Узлы-братья Два узла в дереве называются братьями, если они расположены (Siblings nodes) на одном уровне. Например, если мы взглянем на диаграмму‚ то увидим‚ что узлы B и C являются братьями Дочерний Узел F является дочерним по отношению к узлу C, если они и родительский напрямую связаны и уровень узла C меньше уровня узла F. узлы И наоборот, узел C является родительским для узла F. Узлы C (Child and и F на следующей диаграмме демонстрируют отношения parent node) родительского и дочернего узлов Степень узла Степень узла — это количество его дочерних элементов. (Degree of Например, на рис. 2.8 узел B имеет степень 2 a node) Степень дерева Степень дерева равна максимальной степени составляющих его (Degree of узлов. Дерево, представленное на следующей диаграмме, имеет a tree) степень 2 Поддерево Поддерево — это часть дерева с выбранным узлом в качестве (Subtree) корневого‚ а все его дочерние элементы — это узлы дерева. На диаграмме поддерево от узла E состоит из узла E в качестве корневого и узлов G и H в качестве дочерних Концевой узел Узел в дереве без дочерних элементов называется концевым. (Leaf node) Например, на рис. 2.8 D, G, H и F — это четыре концевых узла Внутренний Любой узел, который не является ни корневым, ни концевым‚ узел (Internal называется внутренним. У внутреннего узла имеются node) по крайней мере один родительский и один дочерний узлы Обратите внимание, что деревья — это своего рода сети или графы, которые мы будем изучать в главе 5. При анализе графов и сетей вме­ сто ветвей мы используем термин «ребро». Большая часть остальной терминологии остается неизменной. 72 Глава 2. Структуры данных, используемые в алгоритмах Типы деревьев Существует несколько типов деревьев: zz Двоичное дерево (binary tree). Если степень дерева равна двум, оно называ­ ется двоичным. Например, дерево, показанное на следующей диаграмме, является двоичным, поскольку имеет степень 2 (рис. 2.8). Корневой узел А Уровень 0 C B Уровень 1 Внутренний узел Внутренний узел D E F Уровень 2 Концевой узел Внутренний узел Концевой узел G H Уровень 3 Концевой узел Концевой узел Рис. 2.8 Обратите внимание, что дерево на рис. 2.8 имеет четыре уровня и восемь узлов. zz Полное дерево (full tree). Это дерево, в котором все узлы имеют одинаковую степень, которая равна степени дерева. На диаграмме ниже представлены упомянутые типы деревьев (рис. 2.9). Обратите внимание, что двоичное дерево слева не является полным, так как узел C имеет степень 1, а все остальные узлы — степень 2. Деревья в центре и справа являются полными. zz Идеальное дерево (perfect tree). Это особый тип полного дерева, у которого все конечные узлы расположены на одном уровне. На рис. 2.9 двоичное де­ рево справа является идеальным полным деревом, поскольку все его конеч­ ные узлы находятся на уровне 2. Резюме 73 zz Упорядоченное дерево (ordered tree). Если дочерние элементы узла органи­ зованы в определенном порядке согласно установленным критериям, дерево называется упорядоченным. Дерево, например, может быть упорядочено слева направо в порядке возрастания. Таким образом, значение узлов одно­ го уровня будет увеличиваться при движении слева направо. Корневой узел Корневой узел Корневой узел А А А C C C B B B Внутренний узел Внутренний узел Внутренний узел Внутренний узел Внутренний узел Внутренний узел D E F D E F I D E F I Концевой узел Внутренний узел Концевой узел Концевой узел Внутренний Концевой Концевой Концевой Внутренний Концевой Концевой узел узел узел узел узел узел узел G H G H Концевой узел Концевой узел Концевой узел Концевой узел Неполное, неидеальное дерево Полное, неидеальное дерево Полное, идеальное дерево Рис. 2.9 Практические примеры Дерево — одна из основных структур данных, используемых при разработке деревьев решений. Их мы обсудим в главе 7. Благодаря своей иерархической структуре деревья используются в алгоритмах сетевого анализа (см. главу 5), а также в алгоритмах поиска и сортировки, где применяются стратегии типа «разделяй и властвуй». РЕЗЮМЕ В этой главе мы обсудили структуры данных, используемые для реализации различных типов алгоритмов. Теперь вы сможете подобрать подходящую струк­ туру данных для вашего алгоритма. Помните, что выбор той или иной структу­ ры влияет на производительность. Следующая глава посвящена алгоритмам сортировки и поиска. При работе с ними мы будем использовать изученные ранее структуры данных.