Алгоритмы и структуры данных что это
Лекции Технопарка. 1 семестр. Алгоритмы и структуры данных
Очередной пост в рамках нашего цикла лекций Технопарка. В этот раз мы предлагаем вашему вниманию курс, посвящённый алгоритмам и структурам данных. Автор курса — Степан Мацкевич, сотрудник компании ABBYY.
Лекция 1. Основы
Начало первой лекции посвящено обсуждению основных понятий, на которых строится вся дальнейшая программа курса: что такое алгоритм и структура данных. Описаны базовые виды алгоритмов, их характеристики и методы анализа. Далее рассматриваются примеры создания алгоритмов для вычисления чисел Фибоначчи, проверки числа на простоту, быстрого возведения числа в целую степень. В конце лекции рассказывается об особенностях использования алгоритмов для работы с массивами: создание однопроходных алгоритмов, поиск минимального элемента, бинарный поиск.
Лекция 2. Элементарные структуры данных
Вторая лекция посвящена изучению элементарных структур данных. В начале даётся определение понятия «абстрактного типа данных». Далее лектор рассказывает о том, что такое амортизационный анализ и каковы его особенности.
Лекция 3. Сортировки (часть 1)
Лекция 4. Сортировки (часть 2)
Лекция 5. Хеш-таблицы
Из этой лекции вы сначала узнаете, что такое метод поиска хешированием, какие бывают хеш-функции (в том числе хеш-функции строк). Затем идёт подробное рассмотрение хеш-таблиц и способов их применения: что они собой представляют, каковы основные методы разрешения коллизий (метод цепочек и метод открытой адресации), а также методы вставки, удаления и поиска элементов. Напоследок проводится сравнение хеш-таблиц по затратам времени и памяти.
Лекция 6. Деревья
Последняя лекция в рамках курса АиСД посвящена таким структурам данных, как деревья. Разумеется, в начале лекции дается определение понятия «деревья», рассматриваются их характеристики и приводятся примеры. Затем вы узнаете, как деревья представлены в памяти, какие есть способы обхода дерева. Далее рассматриваются так называемые двоичные деревья поиска и группа самобалансирующихся деревьев: декартовы и АВЛ-деревья. И в завершение лекции рассказывается об абстрактном типе данных «ассоциативный массив».
Алгоритмы и структуры данных для начинающих: сложность алгоритмов
Вне зависимости от того, являетесь ли вы студентом или работающим программистом, и от того, в какой области вы работаете, знание алгоритмов и структур данных необходимо. Это важные строительные блоки для решения задач.
Конечно, вы наверняка пользовались списком или стеком, но знаете ли вы, как они работают? Если нет, то вы не можете быть уверены, что принимаете правильные решения относительно того, какой алгоритм использовать.
Понимание алгоритмов и структур данных начинается с умения определять и сравнивать их сложность.
27–29 декабря, Онлайн, Беcплатно
Если не хочется копаться и разбираться, но есть потребность быстро понять основы оценки сложности, идите сюда.
Асимптотический анализ
Когда мы говорим об измерении сложности алгоритмов, мы подразумеваем анализ времени, которое потребуется для обработки очень большого набора данных. Такой анализ называют асимптотическим. Сколько времени потребуется на обработку массива из десяти элементов? Тысячи? Десяти миллионов? Если алгоритм обрабатывает тысячу элементов за пять миллисекунд, что случится, если мы передадим в него миллион? Будет ли он выполняться пять минут или пять лет? Не стоит ли выяснить это раньше заказчика?
Порядок роста
Порядок роста описывает то, как сложность алгоритма растет с увеличением размера входных данных. Чаще всего он представлен в виде O-нотации (от нем. «Ordnung» — порядок) : O(f(x)), где f(x) — формула, выражающая сложность алгоритма. В формуле может присутствовать переменная n, представляющая размер входных данных. Ниже приводится список наиболее часто встречающихся порядков роста, но он ни в коем случае не полный.
Константный — O(1)
Порядок роста O(1) означает, что вычислительная сложность алгоритма не зависит от размера входных данных. Следует помнить, однако, что единица в формуле не значит, что алгоритм выполняется за одну операцию или требует очень мало времени. Он может потребовать и микросекунду, и год. Важно то, что это время не зависит от входных данных.
Линейный — O(n)
Порядок роста O(n) означает, что сложность алгоритма линейно растет с увеличением входного массива. Если линейный алгоритм обрабатывает один элемент пять миллисекунд, то мы можем ожидать, что тысячу элементов он обработает за пять секунд.
Такие алгоритмы легко узнать по наличию цикла по каждому элементу входного массива.
Логарифмический — O( log n)
Порядок роста O( log n) означает, что время выполнения алгоритма растет логарифмически с увеличением размера входного массива. (Прим. пер.: в анализе алгоритмов по умолчанию используется логарифм по основанию 2). Большинство алгоритмов, работающих по принципу «деления пополам», имеют логарифмическую сложность. Метод Contains бинарного дерева поиска (binary search tree) также имеет порядок роста O(log n).
Линеарифметический — O(n·log n)
Линеарифметический (или линейно-логарифмический) алгоритм имеет порядок роста O(n·log n). Некоторые алгоритмы типа «разделяй и властвуй» попадают в эту категорию. В следующих частях мы увидим два таких примера — сортировка слиянием и быстрая сортировка.
Квадратичный — O(n 2 )
Время работы алгоритма с порядком роста O(n 2 ) зависит от квадрата размера входного массива. Несмотря на то, что такой ситуации иногда не избежать, квадратичная сложность — повод пересмотреть используемые алгоритмы или структуры данных. Проблема в том, что они плохо масштабируются. Например, если массив из тысячи элементов потребует
1 000 000 операций, массив из миллиона элементов потребует 1 000 000 000 000 операций. Если одна операция требует миллисекунду для выполнения, квадратичный алгоритм будет обрабатывать миллион элементов 32 года. Даже если он будет в сто раз быстрее, работа займет 84 дня.
Мы увидим пример алгоритма с квадратичной сложностью, когда будем изучать пузырьковую сортировку.
Наилучший, средний и наихудший случаи
Что мы имеем в виду, когда говорим, что порядок роста сложности алгоритма — O(n)? Это усредненный случай? Или наихудший? А может быть, наилучший?
Обычно имеется в виду наихудший случай, за исключением тех случаев, когда наихудший и средний сильно отличаются. К примеру, мы увидим примеры алгоритмов, которые в среднем имеют порядок роста O(1), но периодически могут становиться O(n) (например, ArrayList.add ). В этом случае мы будем указывать, что алгоритм работает в среднем за константное время, и объяснять случаи, когда сложность возрастает.
Самое важное здесь то, что O(n) означает, что алгоритм потребует не более n шагов.
Что мы измеряем?
При измерении сложности алгоритмов и структур данных мы обычно говорим о двух вещах: количество операций, требуемых для завершения работы (вычислительная сложность), и объем ресурсов, в частности, памяти, который необходим алгоритму (пространственная сложность).
Алгоритм, который выполняется в десять раз быстрее, но использует в десять раз больше места, может вполне подходить для серверной машины с большим объемом памяти. Но на встроенных системах, где количество памяти ограничено, такой алгоритм использовать нельзя.
В этих статьях мы будем говорить о вычислительной сложности, но при рассмотрении алгоритмов сортировки затронем также вопрос ресурсов.
Операции, количество которых мы будем измерять, включают в себя:
То, какие операции мы учитываем, обычно ясно из контекста.
К примеру, при описании алгоритма поиска элемента в структуре данных мы почти наверняка имеем в виду операции сравнения. Поиск — это преимущественно процесс чтения, так что нет смысла делать присваивания или выделение памяти.
Когда мы говорим о сортировке, мы можем учитывать как сравнения, так и выделения и присваивания. В таких случаях мы будем явно указывать, какие операции мы рассматриваем.
Продолжение следует
На этом мы заканчиваем знакомство с анализом сложности алгоритмов. В следующий раз мы рассмотрим первую структуру данных — связный список.
Структуры данных для самых маленьких
James Kyle как-то раз взял и написал пост про структуры данных, добавив их реализацию на JavaScript. А я взял и перевёл.
Дисклеймер: в посте много ascii-графики. Не стоит его читать с мобильного устройства — вас разочарует форматирование текста.
Сегодня мы узнаем всё о структурах данных.
«Оооооой как интересно. », да?
Да уж, не самая сочная тема на сей день, однако крайне важная. Не для того, чтобы сдавать курсы наподобие CS101, а чтобы лучше разбираться в программировании.
Второй пункт тоже важен. Когда учитываются производительность или память программы, правильный выбор структуры данных значительно сказывается на работе.
Чтобы познакомиться со структурами данных, мы реализуем некоторые из них. Не беспокойтесь, код будет лаконичен. На самом деле, тут больше комментариев, а кода между ними — раз, два и обчёлся.
Что такое структуры данных?
По сути, это способы хранить и организовывать данные, чтобы эффективней решать различные задачи. Данные можно представить по-разному. В зависимости от того, что это за данные и что вы собираетесь с ними делать, одно представление подойдёт лучше других.
Чтобы понять, почему так происходит, сперва поговорим об алгоритмах.
Алгоритмы
Алгоритм — такое хитроумное название для последовательности совершаемых действий.
Структуры данных реализованы с помощью алгоритмов, алгоритмы — с помощью структур данных. Всё состоит из структур данных и алгоритмов, вплоть до уровня, на котором бегают микроскопические человечки с перфокартами и заставляют компьютер работать. (Ну да, у Интела в услужении микроскопические люди. Поднимайся, народ!)
Любая данная задача реализуется бесконечным количеством способов. Как следствие, для решения распространённых задач изобрели множество различных алгоритмов.
Например, для сортировки неупорядоченного множества элементов существует до смешного большое количество алгоритмов:
Сортировка вставками, Сортировка выбором, Сортировка слиянием, Сортировка пузырьком, Cортировка кучи, Быстрая сортировка, Сортировка Шелла, Сортировка Тима, Блочная сортировка, Поразрядная сортировка.
Некоторые из них значительно быстрее остальных. Другие занимают меньше памяти. Третьи легко реализовать. Четвёртые построены на допущениях относительно наборов данных.
Каждая из сортировок подходит лучше других для определённой задачи. Поэтому вам надо будет сперва решить, какие у вас потребности и критерии, чтобы понять, как сравнивать алгоритмы между собой.
Для сравнения производительности алгоритмов используется грубое измерение средней производительности и производительности в худшем случае, для обозначения которых используется термин «О» большое.
О большое
«О» большое — обозначение способа приблизительной оценки производительности алгоритмов для относительного сравнения.
О большое — заимствованное информатикой математические обозначение, определяющее, как алгоритмы соотносятся с передаваемым им некоторым количеством N данных.
О большое характеризует две основные величины:
Оценка времени выполнения — общее количество операций, которое алгоритм проведёт на данном множестве данных.
Оценка объёма — общее количество памяти, требующееся алгоритму для обработки данного множества данных.
Оценки делаются независимо друг от друга: одни алгоритмы могут производить меньше операций, чем другие, занимая при этом больше памяти. Определив свои требования, вы сможете выбрать соответствующий алгоритм.
Вот некоторые распространённые значения О большого:
Чтобы дать представление, о каких порядках чисел мы говорим, давайте взглянем, что это будут за значения в зависимости от N.
Как видите, даже при относительно небольших числах можно сделать *дофига* дополнительной работы.
Структуры данных позволяют производить 4 основных типа действий: доступ, поиск, вставку и удаление.
Замечу, что структуры данных могут быть хороши в одном из действий, но плохи в другом.
Кроме того, некоторые действия имеют разную «среднюю» производительность и производительность в «самом худшем случае».
Идеальной структуры данных не существует. Вы выбираете самую подходящую, основываясь на данных и на том, как они будут обрабатываться. Чтобы сделать правильный выбор, важно знать различные распространённые структуры данных.
Память
Компьютерная память — довольно скучная штука. Это группа упорядоченных слотов, в которых хранится информация. Чтобы получить к ней доступ, вы должны знать её адрес в памяти.
Фрагмент памяти можно представить так:
Если вы задумывались, почему в языках программирования отсчёт начинается с 0 — потому, что так работает память. Чтобы прочитать первый фрагмент памяти, вы читаете с 0 до 1, второй — с 1 до 2. Адреса этих фрагментов соответственно равны 0 и 1.
Конечно же, в компьютере больше памяти, чем показано в примере, однако её устройство продолжает принцип рассмотренного шаблона.
Просторы памяти — как Дикий Запад. Каждая работающая на компьютере программа хранится внутри одной и той же *физической* структуры данных. Использование памяти — сложная задача, и для удобной работы с ней существуют дополнительные уровни абстракции.
Абстракции имеют два дополнительных назначения:
— Сохраняют данные в памяти таким образом, чтобы с ними было эффективно и/или быстро работать.
— Сохраняют данные в памяти так, чтобы их было проще использовать.
Списки
Для начала реализуем список, чтобы показать сложности взаимодействия между памятью и структурой данных.
Список — представление пронумерованной последовательности значений, где одно и то же значение может присутствовать сколько угодно раз.
Начнём с пустого блока памяти, представленного обычным JavaScript-массивом. Также нам понадобится хранить значение длины списка.
Заметьте, что мы хотим хранить длину отдельно, поскольку в реальности у «памяти» нет значения length, которое можно было бы взять и прочитать.
Первым делом нужно получать данные из списка. Обычный список позволяет очень быстро получить доступ к памяти, поскольку вы уже знаете нужный адрес.
Сложность операции доступа в список — O(1) — «ОХРЕНЕННО!!»
У списков есть порядковые номера, поэтому можно вставлять значения в начало, середину и конец.
Это настолько же легко, как добавить значение в адрес, следующий за нашим списком. Поскольку мы храним длину, вычислить адрес — проще простого. Добавим значение и увеличим длину.
Добавление элемента в конец списка — константа O(1) — «ОХРЕНЕННО!!»
Комментарии хабра: poxu не согласен с автором и объясняет, что существует операция расширения памяти, увеличивающая сложность добавления элементов в список.
Далее, реализуем метод «pop», убирающий элемент из конца нашего списка. Аналогично push, всё, что нужно сделать — убрать значение из последнего адреса. Ну, и уменьшить длину.
Удаление элемента из конца списка — константа O(1) — «ОХРЕНЕННО!!»
«Push» и «pop» работают с концом списка, и в общем-то являются простыми операциями, поскольку не затрагивают весь остальной список.
Давайте посмотрим, что происходит, когда мы работаем с началом списка, с операциями «unshift» и «shift».
Чтобы добавить новый элемент в начало списка, нужно освободить пространство для этого значения, сдвинув на один все последующие значения.
Чтобы сделать такой сдвиг, нужно пройтись по каждому из элементов и поставить на его место предыдущий.
Поскольку мы вынуждены пройтись по каждому из элементов списка:
Добавление элемента в начало списка — линейно O(N) — «НОРМАС.»
Осталось написать функцию сдвига списка в противоположном направлении — shift.
Мы удаляем первое значение и затем сдвигаем каждый элемент списка на предшествующий адрес.
Удаление элемента из начала списка — линейно O(N) — «НОРМАС.»
Списки отлично справляются с быстрым доступом к элементам в своём конце и работой с ними. Однако, как мы увидели, для элементов из начала или середины они не слишком хороши, так как приходится вручную обрабатывать адреса памяти.
Давайте посмотрим на иную структуру данных и её методы по добавлению, доступу и удалению значений без необходимости знать адреса элементов.
Хеш-таблицы
Хеш-таблица — неупорядоченная структура данных. Вместо индексов мы работаем с «ключами» и «значениями», вычисляя адрес памяти по ключу.
Смысл в том, что ключи «хешируются» и позволяют эффективно работать с памятью — добавлять, получать, изменять и удалять значения.
Вновь используем обычный JavaScript-массив, представляющий память.
Чтобы сохранять пары ключ-значение из хеш-таблицы в память, нужно превращать ключи в адреса. Этим занимается операция «хеширования».
Она принимает на вход ключ и преобразовывает его в уникальное число, соответствующее этому ключу.
Такая операция требует осторожности. Если ключ слишком большой, он будет сопоставляться несуществующему адресу в памяти.
Следовательно, хеш-функция должна ограничивать размер ключей, т.е. ограничивать число доступных адресов памяти для неограниченного количества значений.
Любая реализация хеш-таблиц сталкивается с этой проблемой.
Однако, поскольку мы собираемся рассмотреть лишь устройство их работы, предположим, что коллизий не случится.
Давайте определим функцию «hashKey».
Не вдавайтесь во внутреннюю логику, просто поверьте, что она принимает на вход строку и возвращает (практически всегда) уникальный адрес, который мы будем использовать в остальных функциях.
Теперь определим функцию «get», получающую значение по ключу.
Сложность чтения значения из хеш-таблицы — константа O(1) — «ОХРЕНЕННО!!»
Перед тем, как получать данные, неплохо бы их сперва добавить. В этом нам поможет функция «set».
Сложность установки значения в хеш-таблицу — константа O(1) — «ОХРЕНЕННО!!»
Наконец, нужен способ удалять значения из хеш-таблицы. Сложность удаления значения из хеш-таблицы — константа O(1) — «ОХРЕНЕННО!!»
Теперь мы прекратим работать с памятью напрямую: все последующие структуры данных будут реализовываться через другие структуры данных.
Стеки
Стеки похожи на списки. Они также упорядочены, но ограничены в действиях: можно лишь добавлять и убирать значения из конца списка. Как мы увидели ранее, это происходит очень быстро, если обращаться к памяти напрямую.
Однако стеки могут быть реализованы через другие структуры данных, чтобы получить дополнительную функциональность.
Наиболее общий пример использования стеков — у вас есть один процесс, добавляющий элементы в стек и второй, удаляющий их из конца — приоритизируя недавно добавленные элементы.
Нам вновь понадобится JavaScript-массив, но на этот раз он символизирует не память, а список, вроде реализованного выше.
Нам понадобится реализовать два метода, функционально идентичных методам списка — «push» и «pop».
Push добавляет элементы на верхушку стека.
Pop удаляет элементы из верхушки.
Кроме того, добавим функцию peek, показывающую элемент на верхушке стека без его удаления. Прим. переводчика: peek – взглянуть.
Очереди
Теперь создадим очередь — структуру, комплементарную стеку. Разница в том, что элементы очереди удаляются из начала, а не из конца, т.е. сначала старые элементы, потом новые.
Как уже оговаривалось, поскольку функциональность ограничена, существуют разные реализации очереди. Хорошим способом будет использование связного списка, о котором мы поговорим чуть позже.
И вновь мы призываем на помощь JavaScript-массив! В случае с очередью мы опять рассматриваем его как список, а не как память.
Аналогично стекам мы определяем две функции для добавления и удаления элементов из очереди.
Первым будет «enqueue» — добавление элемента в конец списка.
Далее — «dequeue». Элемент удаляется не из конца списка, а из начала.
Аналогично стекам объявим функцию «peek», позволяющую получить значение в начале очереди без его удаления.
Важно заметить, что, поскольку для реализации очереди использовался список, она наследует линейную производительность метода shift (т.е. O(N) — «НОРМАС.»).
Как мы увидим позже, связные списки позволяют реализовать более быструю очередь.
С этого места и далее мы будем работать со структурами данных, где значения ссылаются друг на друга.
Элементы структуры данных становятся сами по себе министруктурами, содержащими значение и дополнительную информацию — ссылки на другие элементы родительской структуры.
Сейчас вы поймёте, что я имею ввиду.
Графы
На самом деле граф — совсем не то, о чём вы подумали, увидев ascii-график.
Граф — структура наподобие этой:
Эти вершины можно представить вот так:
А весь граф будет выглядеть вот так:
Представим список вершин JavaScript-массивом. Массив используется не с целью специально упорядочить вершины, а как место для хранения вершин.
Начнём добавлять значения в граф, создавая вершины без каких-либо линий.
Теперь нужен способ искать вершины в графе. Обычно для ускорения поиска делается ещё одна структура данных поверх графа.
Но в нашем случае мы просто переберём все вершины, чтобы найти соответствующую значению. Способ медленный, но работающий.
Теперь мы можем связать две вершины, проведя «линию» от одной до другой (прим. переводчика: дугу графа).
Полученный граф можно использовать вот так:
Кажется, что для такой мелкой задачи сделано слишком много работы, однако это мощный паттерн.
Он часто применяется для поддержания прозрачности в сложных программах. Это достигается оптимизацией взаимосвязей между данными, а не операций над самими данными. Если вы выберете одну вершину в графе, невероятно просто найти связанные с ней элементы.
Графами можно представлять уйму вещей: пользователей и их друзей, 800 зависимостей в папке node_modules, даже сам интернет, являющийся графом связанных друг с другом ссылками веб-страниц.
Связные списки
Давайте теперь посмотрим, как графоподобная структура может оптимизировать упорядоченный список данных.
Связные списки — распространённая структура данных, зачастую используемая для реализации других структур. Преимущество связного списка — эффективность добавления элементов в начало, середину и конец.
Связный список по своей сути похож на граф: вы работаете с вершинами, указывающими на другие вершины. Они расположены таким образом:
Если представить эту структуру в виде JSON, получится нечто такое:
В отличие от графа, связный список имеет единственную вершину, из которой начинается внутренняя цепочка. Её называют «головой», головным элементом или первым элементом связного списка.
Также мы собираемся отслеживать длину списка.
Первым делом нужен способ получать значение по данной позиции.
В отличие от обычных списков мы не можем перепрыгнуть на нужную позицию. Вместо этого мы должны перейти к ней через отдельные вершины.
Теперь необходим способ добавлять вершины в выбранную позицию.
Создадим метод add, принимающий значение и позицию.
Последний метод, который нам понадобится — remove. Найдём вершину по позиции и выкинем её из цепочки.
Две оставшиеся структуры данных относятся к семейству «деревьев».
Как и в жизни, существует множество различных древовидных структур данных.
Прим. переводчика: ну не-е-е-е, я пас…
Binary Trees:
AA Tree, AVL Tree, Binary Search Tree, Binary Tree, Cartesian Tree, left child/right sibling tree, order statistic tree, Pagoda,…
B Trees:
B Tree, B+ Tree, B* Tree, B Sharp Tree, Dancing Tree, 2-3 Tree,…
Heaps:
Heap, Binary Heap, Weak Heap, Binomial Heap, Fibonacci Heap, Leonardo Heap, 2-3 Heap, Soft Heap, Pairing Heap, Leftist Heap, Treap,…
Trees:
Trie, Radix Tree, Suffix Tree, Suffix Array, FM-index, B-trie,…
Multi-way Trees:
Ternary Tree, K-ary tree, And-or tree, (a,b)-tree, Link/Cut Tree,…
Space Partitioning Trees:
Segment Tree, Interval Tree, Range Tree, Bin, Kd Tree, Quadtree, Octree, Z-Order, UB-Tree, R-Tree, X-Tree, Metric Tree, Cover Tree,…
Application-Specific Trees:
Abstract Syntax Tree, Parse Tree, Decision Tree, Minimax Tree,…
Чего уж вы не ожидали, так это что будете изучать сегодня дендрологию… И это ещё не все деревья. Пусть они вас не смущают, большинство из них вообще не имеет смысла. Надо же было людям как-то защищать кандидатские степени и что-то для этого доказывать.
Деревья похожи на графы или связные списки, с той разницей, что они «однонаправленые». Это значит, что в них не может существовать циклических ссылок.
Если вы можете пройти круг по вершинам дерева… что ж, поздравляю, но это не дерево.
Деревья применяются во множестве задач. Они используются для оптимизации поиска или сортировки. Они могут лучше организовывать программу. Они могут создать представление, с которым проще работать.
Деревья
Начнём с простой древовидной структуры. В ней нет особых правил, и выглядит она примерно так:
Дерево должно начинаться с единственного родителя, «корня» дерева.
Нам нужен способ обходить наше дерево и вызывать определённую функцию в каждой его вершине.
Теперь нужен способ добавлять вершины в дерево.
Это простое дерево, возможно, полезное лишь в случае, когда отображаемые данные на него похожи.
Однако при наличии дополнительных правил деревья могут выполнять кучу различных задач.
Двоичные деревья поиска
Двоичные деревья поиска — распространённая форма деревьев. Они умеют эффективно читать, искать, вставлять и удалять значения, сохраняя при этом отсортированный порядок.
Представьте, что у вас есть последовательность чисел:
Развернём её в дерево, начинающееся из центра.
Это делает обход дерева при поиске значения очень эффективным. Например, попробуем найти число 5 в нашем дереве.
Заметьте, чтобы добраться до 5, потребовалось сделать лишь 3 проверки. А если бы дерево состояло из 1000 элементов, путь был бы таким:
Всего 10 проверок на 1000 элементов!
Ещё одной важной особенностью двоичных деревьев поиска является их схожесть со связными списками — при добавлении или удалении значения вам нужно обновлять лишь непосредственно окружающие элементы.
Как и в прошлой секции, сперва нужно установить “корень” двоичного дерева поиска.
Чтобы проверить, находится ли значение в дереве, нужно провести поиск по дереву.
Чтобы добавить элемент в дерево, нужно произвести такой же обход, как и раньше, перепрыгивая по левым и правым вершинам в зависимости от того, больше или меньше ли они по сравнению с добавляемым значением.
Однако теперь, когда мы доберёмся до левой или правой вершины, равной null,
мы добавим вершину в эту позицию.
Конец
Надеюсь, вы получили хорошую дозу знаний. Если вам понравилось,
ставьте звездочки в репозитории и подписывайтесь на меня в твиттере.
Также можете прочитать другую мою статью, «The Super Tiny Compiler» github.com/thejameskyle/the-super-tiny-compiler
Также эту статью можно прочитать на гитхабе.
Перевод: aalexeev, редактура: iamo0, Чайка Чурсина.