Тема префиксных деревьев поиска уже неколько раз поднималась на хабре. Здесь, например, кратко описывается, что такое префиксное дерево и зачем оно нужно, и рассматриваются основные операции над такими деревьями (поиск, вставка, удаление). К сожалению, ничего при этом не говорится про реализацию. В этом недавнем посте рассматривается «питонья библиотека datrie», являющаяся Cython-оберткой библиотеки libdatrie. По последней ссылке имеется хорошее описание реализации частично сжатых префиксных деревьев в виде детерминированных конечных автоматов (с использованием массивов). Я решил внести свои пять копеек в эту тему, рассмотрев реализацию на языке С++ префиксных деревьев с помощью указателей. Кроме того, была и еще одна цель — сравнить между собой поиск строк с помощью сбалансированного двоичного дерева поиска (АВЛ-дерево) и сжатого префиксного дерева.

Если в одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска, придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например, тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще красно-черных деревьев, но глядя на прилагаемый к этому код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.

Так получилось, что за последние полгода мне удалось познакомиться с несколькими простыми (в смысле правил) и в чем-то схожими настольными играми. Первым в этом ряду был «Сет», потом «Барабашка», а уже летом мы играли в «Доббль». Сразу скажу, что все перечисленные игры весьма увлекательные, однако, речь в этом посте пойдет, конечно же, не об этом. Дело в том, что спустя некоторое время (другими словами, наигравшись) меня заинтересовали идеи, лежащие в основе этих игр, и которые оказались тесно связанными именно с комбинаторикой. В данном посте речь пойдет о самой простой (на мой взгляд) игре — «Барабашке», которая, кстати, в оригинальном варианте имеет более благозвучное название «Geistesblitz» (нем. — озарение).

Не знаю, как вы, уважаемый читатель, а я всегда поражался контрасту между изяществом базовой идеи, заложенной в концепцию двоичных деревьев поиска, и сложностью реализации сбалансированных двоичных деревьев поиска (красно-черные деревья, АВЛ-деревья, декартовы деревья). Недавно, перелистывая в очередной раз Седжвика [1], нашел описание рандомизированных деревьев поиска (нашлась и оригинальная работа [2]) — настолько простое, что занимает оно всего треть страницы (вставка узлов, еще страница — удаление узлов). Кроме того, при ближайшем рассмотрении обнаружился дополнительный бонус в виде очень красивой реализации операции удаления узлов из дерева поиска. Далее вы найдете описание (с цветными картинками) рандомизированных деревьев поиска, реализация на С++, а также результаты небольшого авторского исследования сбалансированности описываемых деревьев.

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

Листая страницы хаба «Алгоритмы», наткнулся на топик, посвященный решению задачи локализации точки в многоугольнике: задан многоугольник (замкнутая ломаная линия без самопересечений), требуется определить — находится ли заданная точка A внутри этого многоугольника или нет. В одном из последних комментариев к топику было высказано недоумение, какое отношение такая чисто математическая задача имеет к теории алгоритмов. Имеет-имеет, причем самое непосредственное. Задача локализации является классической задачей вычислительной геометрии (не путать с компьютерной графикой). В качестве разминки предлагается взглянуть на картинку справа, на которой изображен многоугольник типа кривой Пеано (источник [1]), и попытаться ответить на вопрос — красная точка ты видишь суслика? и я не вижу, а он есть! находится внутри или снаружи многоугольника? А ниже мы (исключительно в образовательных целях) рассмотрим простую вариацию данной задачи, когда заданный многоугольник является выпуклым.

Составление алгоритмов в рамках той или иной классической алгоритмической модели (машины Тьюринга и Поста, нормальные алгоритмы Маркова, счетчиковые машины Минского и т.д.) смело можно относить к ненормальному программированию в силу исключительной минимальности выразительных средств этих моделей. Не исключением из данного правила является и такая относительно новая алгоритмическая модель, как мембранные системы или P-системы, придуманная румынским ученым Георгием Пауном чуть более десяти лет назад. Целью этого нововведения было исследование вычислительных возможностей клеткоподобных структур (имеются в виду биологические клетки), а вообще вся эта деятельность была инспирирована знаменитым опытом Адлемана по решению задачи о поиске Гамильтонова пути с помощью ДНК-вычислений. Как это ни странно, но данный топик посвящен как раз решению (к сожалению, виртуальному) той же самой задачи, но уже с помощью простейшей мембранной системы. Итак, под катом читатель найдет 1) краткое описание того, что такое мембранные системы; 2) как «программировать» такое «железо»; 3) мембранный алгоритм решения задачи о гамильтоновом пути, обладающий полиномиальным временем выполнения.

Итак, как и обещал, продолжение темы о таблицах Юнга. Напомню, что под таблицей Юнга понимается числовая матрица, обладающая некоторыми специальными свойствами. Матрица – это двумерный массив. И вот тут должен возникнуть естественный вопрос – а почему, собственно, массив должен быть двумерным? А что, если мы попробуем реализовать на тех же принципах таблицу размерности три, или четыре, а лучше всего, конечно, пять звездочек! О том, куда приведет нас такое обобщение, можно прочитать под катом…

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