Что такое серия «Назад к основам»?

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

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

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

Теперь, когда это не так, добро пожаловать в первую тему «Назад к основам»! Первая тема для этого - это очень широко известная структура данных, которую я, к моему удивлению, не видел достаточно используемой, и это дерево двоичного поиска. Я думаю, что это отличная тема для начала, потому что она является основой для нескольких тем, таких как деревья RB, деревья AVL, и они также участвуют в нескольких алгоритмах, о которых я буду писать.

Что такое структуры данных?

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

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

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

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

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

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

Чтобы понять двоичное дерево, мы должны понять некоторые термины. Первый узел, который у нас есть наверху, называется корнем. В этом случае корень имеет значение 8. Все, на что указывает узел, называется дочерним элементом. Если у этих дочерних узлов нет собственных дочерних узлов или, другими словами, они находятся в конце дерева, например 4, 7 и 13, они называются листьями . Высота дерева - это максимальное расстояние от корня до листьев. В этом случае корень начинается на высоте 0. Назовем его h = 0. Узлы 3 и 10 имеют h = 1. Следующие узлы 1, 6 и 14 имеют h = 2. И, наконец, листья 4, 7 и 13 равны h = 3. Это означает, что это дерево имеет высоту 3. Высота используется для вычисления максимального количества узлов, которое может иметь дерево, среди других вычислений, но это тема для другого дня.

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

Все дочерние элементы справа от корневого узла должны быть больше 8, а все слева - меньше 8. И так далее и тому подобное для каждого узла и его дочерних узлов. Но мы действительно видим кое-что интересное в дереве. Если мы перейдем к h = 3, мы заметим, что лист со значением 7 находится справа от своего родительского узла со значением 6, что соответствует правилам. Однако стоит отметить кое-что интересное, что если мы посмотрим на верхушку корня, мы заметим, что даже на три высоты ниже лист по-прежнему подчиняется правилу, согласно которому все слева меньше, как 7 ‹8. Обычно, когда я визуально вставляю что-то в двоичное дерево, я иду сверху вниз, спрашивая себя: «Больше или меньше», а затем иду соответственно вправо или влево!

Всегда ли это полезно?

Если не позаботиться о дереве должным образом, оно может стать списком. Посмотрите на пример ниже:

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

Примеры использования двоичных деревьев поиска

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

Бинарное дерево поиска может быть прекрасной заменой списку. Причина в том, что при правильной реализации двоичного дерева поиска средняя временная сложность поиска, удаления и вставки узлов составляет O (log n). и это быстрее, чем временная сложность этих операций для массива, который имеет временную сложность O (n). Если вы не знакомы с временной сложностью, это действительно стоящая тема для чтения.

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

Что дальше?

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

Сказав это, я хотел бы услышать о том, о чем, по вашему мнению, было бы интересно поговорить. Какие структуры данных вам интересны? Какие-нибудь алгоритмы? Дайте мне знать! Это всегда хорошее время, чтобы вернуться к основам!