Часть 2. Связанные списки, деревья и деревья двоичного поиска

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

Связанные списки

Цепочка элементов, каждый со ссылкой на следующий, плюс назначенные начало и конец

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

Цифровой пример: список объектов для визуализации

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

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

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

Допустим, вы добрались до первого тайника и нашли водонепроницаемый конверт с координатами следующего места. Вы хотите совершить этот поход в одиночку, поэтому решаете взять с собой конверт, эффективно удаляя этот тайник с головой из цепочки. Это эквивалент метода удаления головки. Поскольку мы всегда сохраняем прямую ссылку на начало нашего связанного списка, это операция с постоянным временем O(1).

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

Через несколько часов вы доберетесь до последнего тайника (хвоста). В этом кэше нет координат, потому что он последний. Вы чувствуете себя немного виноватым из-за удаления тайника с головами, поэтому решаете компенсировать это, добавив еще одно место в конце путешествия. Вы заменяете координаты в конверте координатами ближайшего водопада и добавляете его в тайник, который раньше был хвостом. Затем вы идете к водопаду и оставляете одну из жеод, которые вы взяли вместе с поздравительным сообщением, в контейнере с тайником возле водопада. Вы только что применили метод «добавить в хвост». Это операция с постоянным временем O(1), потому что вы спросили своего друга, где находится хвост, прежде чем начать. Вы могли бы пойти туда прямо, чтобы добавить свои новые координаты.

Что делать, если вы хотите вставить новый кеш в середину цепочки кешей? Можно ли это сделать за постоянное время, как это было при добавлении к хвосту? (Попробуйте ответить на этот вопрос самостоятельно, а затем проверьте свои мысли ниже.)

ОТВЕЧАТЬ:

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

Деревья

Иерархическая коллекция узлов и их потомков

Пример IRL: генеалогическое древо, организационная структура

Цифровой пример: DOM, вложенные представления в MVC

Общие методы: добавить дочерний элемент, содержит, удалить ветку.

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

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

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

Бинарные деревья поиска

Иерархическая коллекция отсортированных значений

Цифровой пример: может использоваться для простых алгоритмов сортировки.

Распространенные методы: вставка, содержание, удаление.

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

Поскольку бинарные деревья поиска сортируются, большинство методов их методов могут быть выполнены за логарифмическое время O(log n). Представьте, что мы хотим увидеть, содержит ли наше бинарное дерево поиска значение 6. Нам не нужно искать каждый узел дерева, чтобы найти нашу цель. Вместо этого мы начинаем с 8 и спрашиваем себя: «6 больше или меньше 8?» Это меньше чем, поэтому мы переходим к левому дочернему узлу и задаем себе тот же вопрос, на этот раз сравнивая 6 со значением нового узла 3. На этот раз наша цель больше, чем текущий узел, поэтому мы переходим к правому дочернему узлу. и находим нашу цель 6. Каждый раз, когда мы переходим к следующему узлу, мы исключаем половину оставшихся вариантов, которые не соответствуют нашей цели. Это дает нам преимущество логарифмической временной сложности.

Вставка и удаление узлов также может выполняться за логарифмическое время, но вносит некоторую дополнительную сложность. Если узел не имеет потомков, вставка и удаление выполняются просто. Если у узла есть один дочерний элемент, этот метод может потребовать балансировки результирующей триады узел/дочерние элементы, но не повлияет на структуру дерева за пределами этих трех узлов. Если узел имеет двух дочерних элементов, может потребоваться повторная балансировка всего дерева. Существует ряд алгоритмов балансировки бинарных деревьев поиска, одним из которых является алгоритм Дэя-Стаута-Уоррена, который выполняет эту задачу за линейное время.

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