Pull to refresh
  • by relevance
  • by date
  • by rating

Эрик Липперт — Генерация всех бинарных деревьев

Algorithms
Translation
Раньше я описывал небольшой алгоритм, который делал небольшие операции на бинарными деревьями. Я хотел протестировать его. Я попробовал несколько небольших тестов и они прошли, но я не был доволен. Я был почти уверен, но возможно какая-то непонятная топология бинарного дерева могла привести к ошибке. Я сообразил, что существует конечное количество бинарных деревьев данного размера. Я решил попробовать их все.
Читать дальше →
Total votes 39: ↑32 and ↓7 +25
Views9.8K
Comments 8

Декартово дерево: Часть 1. Описание, операции, применения

Algorithms

Оглавление (на данный момент)


Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Декартово дерево (cartesian tree, treap) — красивая и легко реализующаяся структура данных, которая с минимальными усилиями позволит вам производить многие скоростные операции над массивами ваших данных. Что характерно, на Хабрахабре единственное его упоминание я нашел в обзорном посте многоуважаемого winger, но тогда продолжение тому циклу так и не последовало. Обидно, кстати.

Я постараюсь покрыть все, что мне известно по теме — несмотря на то, что известно мне сравнительно не так уж много, материала вполне хватит поста на два, а то и на три. Все алгоритмы иллюстрируются исходниками на C# (а так как я любитель функционального программирования, то где-нибудь в послесловии речь зайдет и о F# — но это читать не обязательно :). Итак, приступим.

Введение


В качестве введения рекомендую прочесть пост про двоичные деревья поиска того же winger, поскольку без понимания того, что такое дерево, дерево поиска, а так же без знания оценок сложности алгоритма многое из материала данной статьи останется для вас китайской грамотой. Обидно, правда?

Следующий пункт нашей обязательной программы — куча (heap). Думаю, также многим известная структура данных, однако краткий обзор я все же приведу.
Представьте себе двоичное дерево с какими-то данными (ключами) в вершинах. И для каждой вершины мы в обязательном порядке требуем следующее: ее ключ строго больше, чем ключи ее непосредственных сыновей. Вот небольшой пример корректной кучи:


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

Сейчас за кадром остается вопрос, каким образом в кучу можно добавлять и удалять из нее элементы. Во-первых, эти алгоритмы требуют отдельного места на осмотр, а во-вторых, нам они все равно не понадобятся.
А теперь собственно про декартово дерево
Total votes 166: ↑161 and ↓5 +156
Views121.7K
Comments 30

Декартово дерево: Часть 2. Ценная информация в дереве и множественные операции с ней

Algorithms

Оглавление (на данный момент)


Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Тема сегодняшней лекции


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

К счастью (или к сожалению?), реальная жизнь такими пустяковыми задачами не ограничивается. О чем сегодня и пойдет речь. Первый вопрос на повестке дня — это так называемая K-я порядковая статистика, или индекс в дереве, которая плавно подведет нас к хранению пользовательской информации в вершинах, и наконец — к бесчисленному множеству манипуляций, которые с этой информацией может потребоваться выполнять. Поехали.

Ищем индекс


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

Решение и вся статья - под катом
Total votes 76: ↑72 and ↓4 +68
Views32.5K
Comments 14

Декартово дерево: Часть 3. Декартово дерево по неявному ключу

Algorithms

Оглавление (на данный момент)


Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Очень сильное колдунство


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

Вспомним-ка еще раз структуру дерамиды. В ней есть ключ x, по которому дерамида есть дерево поиска, случайный ключ y, по которому дерамида есть куча, а также, возможно, какая-то пользовательская информация с (cost). Давайте совершим невозможное и рассмотрим дерамиду… без ключей x. То есть у нас будет дерево, в котором ключа x нет вообще, а ключи y — случайные. Соответственно, зачем оно нужно — вообще непонятно :)

На самом деле расценивать такую структуру стоит как декартово дерево, в котором ключи x все так же где-то имеются, но нам их не сообщили. Однако клянутся, что для них, как полагается, выполняется условие двоичного дерева поиска. Тогда можно представить, что эти неизвестные иксы суть числа от 0 до N-1 и неявно расставить их по структуре дерева:

Получается, что в дереве будто бы не ключи в вершинах проставлены, а сами вершины пронумерованы. Причем пронумерованы в уже знакомом с прошлой части порядке in-order обхода. Дерево с четко пронумерованными вершинами можно рассматривать как массив, в котором индекс — это тот самый неявный ключ, а содержимое — пользовательская информация c. Игреки нужны только для балансировки, это внутренние детали структуры данных, ненужные пользователю. Иксов на самом деле нет в принципе, их хранить не нужно.

В отличие от прошлой части, этот массив не приобретает автоматически никаких свойств, вроде отсортированности. Ведь на информацию-то у нас нет никаких структурных ограничений, и она может храниться в вершинах как попало.
Если интересно - под кат
Total votes 81: ↑77 and ↓4 +73
Views43.7K
Comments 17

AA-Tree или простое бинарное дерево

Website development
Тема бинарных деревьев уже обсуждалась на хабре (здесь и здесь).

Про AA-дерево было сказано, что «из-за дополнительного ограничения операции реализуются проще чем у красно-черного дерева (за счет уменьшения количества разбираемых случаев)».

Мне, однако, кажется, что AA-дерево заслуживает отдельной статьи.

Читать дальше →
Total votes 42: ↑39 and ↓3 +36
Views16.2K
Comments 10

Ход «Voronoi». Часть 2 — Бинарное дерево

Ruby

Введение


В этой статье хочется представить реализацию дерева бинарного поиска для задачи, изложенной в статье [1]. В описанной там задаче используется алгоритм «sweeping line», для которой нужно бинарное дерево с возможностью перемещения не только от корня дерева к дочерним узлам и листьям, но и по листьям в отдельности, начиная от крайнего листа (левого или правого). Задача показалась достаточно простой, потому не стал долго искать уже готовые реализации и решил сделать самостоятельно. При этом поставил дополнительную задачу — задание процедуры добавления нового листа в дерево снаружи.
Серия на пальцах продолжается...
Total votes 10: ↑8 and ↓2 +6
Views3.9K
Comments 0

Дерево отрезков

Algorithms
Sandbox
Я расскажу о структуре под названием дерево отрезков и приведу его простую реализацию на языке С++. Эта структура весьма полезна в случаях, когда необходимо часто искать значение какой-то функции на отрезках линейного массива и иметь возможность быстро изменять значения группы подряд идущих элементов.
Типичный пример задачи на дерево отрезков:
Есть линейный массив, изначально заполненный некоторыми данными. Далее приходят 2 типа запросов:
1й тип — найти значение максимального элемента на отрезке массива [a..b].
2й тип — заменить iй элемент массива на x.
Возможен запрос «добавить х ко всем элементам на отрезке [a..b]», но в данной статье я его не рассматриваю.
С помощью дерева отрезков можно искать не только максимум чисел, но и любую функцию, удовлетворяющую свойству ассоциативности.
image
Это ограничение связано с тем, что используется предпросчет значений для некоторых отрезков.
Читать дальше →
Total votes 23: ↑14 and ↓9 +5
Views35.6K
Comments 6

Использование бинарного поиска для оптимизации запроса на выборку данных

MySQL
Sandbox

Введение


Сейчас очень популярна тем оптимизации работы с различными СУБД. На многочисленных форумах ведутся дискуссии о «самой лучшей СУБД в мире», но часто все это перетекает в необоснованные выкрики о том, что «я познал смысл жизни и понял, что самое лучшее хранилище данных — Х».

Да, несомненно, сейчас мы можем наблюдать активное развитие NoSQL решений, которые позволяют делать многое. Но данная статья не о них. Так вышло, что я сменил работу и в нагрузку мне достался один очень интересный проект на связке php+MySQL. В нем есть много хороших решений, но он писался без расчёта на большую аудиторию. За несколько лет существования количество активных пользователей начало приближаться к числам с 7 нулями. Так как проект представляет из себя подобие социальной сети с игровыми элементами, то таблица с пользователями оказалась не самой «тяжёлой» из всех. В наследство мне достались таблицы с десятками миллионов вещей пользователей, личных сообщений, биллинговыми записями и т. п. Проект начали рефакторить, разбивать на несколько серверов и достигли значительных результатов. Сейчас все стабильно.

Но недавно мне на почту прислали новую задачу. Суть заключалась в сборе статистики. Проанализировав требования я понял, что для выполнения достаточно написать один единственный запрос, выполняющий 3 INNER JOIN'а на таблицы, размеры которых впечатляли. Каждая таблица в среднем содержала 40 миллионов записей. Получается, что временная таблица состояла бы из 4*4*4*10^21 = 64*10^21 записей. Это колоссальная цифра. И загружать СУБД таким запросом для сбора статистики — непозволительная роскошь.

Далее, собственно, я и хочу представить решение данной абстрактной задачи, которое пришло мне в голову, когда я вспоминал занятия по информатике на первом курсе университета.

Читать дальше →
Total votes 17: ↑8 and ↓9 -1
Views5.7K
Comments 4

Обход бинарных деревьев: рекурсия, итерации и указатель на родителя

ProgrammingJavaAlgorithms
Sandbox
Основы о бинарных деревьях представлены, в том числе, здесь . Добавлю свои «5 копеек» и данным постом систематизирую материалы, связанные с обходом бинарных деревьев, а именно сравнений возможностей рекурсии и итераций, а также обсуждение возможностей использования указателя на родительский узел.
Читать дальше →
Total votes 23: ↑9 and ↓14 -5
Views145.6K
Comments 4

Приключения в математическом лесу фрактальных деревьев

Wolfram ResearchProgrammingMathematics
Translation


Перевод поста Bernat Espigulé Pons, «Adventures into the Mathematical Forest of Fractal Trees».
Скачать перевод в виде документа Mathematica, который содержит весь код использованный в статье, можно здесь.


Без сомнения, золотое сечение и в наше время представляется одним из самых таинственных, волшебных и поразительных чисел, которые известны людям: Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_1.png. (в языке Wolfram Language и системе Mathematica ему соответствует символ GoldenRatio). Как вы увидите из этого поста, это число действительно имеет множество интересных свойств, которые можно исследовать, причём некоторые из них рассматривались ещё в работах учёных Древней Греции, таких как Пифагор и Евклид, другие в работах итальянского математика Леонардо Пизанского, более известного под прозвищем Фибоначчи, или Иоганном Кеплером — астрономом эпохи Возрождения. Хотя это может прозвучать странно, в этом посте я расскажу вам о новых геометрических объектах, связанных с золотым сечением, которые осветили мне путь, когда я пытался отобразить неизвестную ранее область Математического Леса.
Читать дальше →
Total votes 61: ↑58 and ↓3 +55
Views33.8K
Comments 6

Scapegoat-деревья

Инфопульс УкраинаProgrammingAlgorithms
Tutorial
Сегодня мы посмотрим на структуру данных, называемую Scapegoat-деревом. «Scapegoat», кто не в курсе, переводится как «козёл отпущения», что делает дословный перевод названия структуры каким-то странным, поэтому будем использовать оригинальное название. Деревьев поиска, как вы, возможно, знаете есть очень много разных видов, и в основе всех их лежит одна и та же идея: "А хорошо бы при поиске элемента перебирать не весь набор данных подряд, а только какую-то часть, желательно размера порядка log(N)".

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

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

К достоинствам Scapegoat-дерева можно отнести:
  • Отсутствие необходимости хранить какие-либо дополнительные данные в вершинах (а значит мы выигрываем по памяти у красно-черных, АВЛ и декартовых деревьев)
  • Отсутствие необходимости перебалансировать дерево при операции поиска (а значит мы можем гарантировать максимальное время поиска O(log N), в отличии от Splay-деревьев, где гарантируется только амортизированное O(log N))
  • Амортизированная сложность операций вставки и удаления O(log N) — это в общем-то аналогично остальным типам деревьев
  • При построении дерева мы выбираем некоторый коэффициент «строгости» α, который позволяет «тюнинговать» дерево, делая операции поиска более быстрыми за счет замедления операций модификации или наоборот. Можно реализовать структуру данных, а дальше уже подбирать коэффициент по результатам тестов на реальных данных и специфики использования дерева.

К недостаткам можно отнести:
  • В худшем случае операции модификации дерева могут занять O(n) времени (амортизированна сложность у них по-прежнему O(log N), но защиты от «плохих» случаев нет).
  • Можно неправильно оценить частоту разных операций с деревом и ошибиться с выбором коэффициента α — в результате часто используемые операции будут работать долго, а редко используемые — быстро, что как-то не хорошо.

Читать дальше →
Total votes 23: ↑22 and ↓1 +21
Views9.9K
Comments 6

Реализация на Java хешированного бинарного дерева

High performanceJavaGame development
Sandbox
Один мой друг любит говорить (не знаю, его это слова или он их где-то взял), что в программисты идут по двум причинам: если ты хочешь стать хакером или если ты хочешь писать игры. Мой случай второй. Всегда интересовался разработкой игр, причём той частью, которая отвечает за искусственный интеллект в играх. Очень много времени я потратил на изучение алгоритмов поиска пути. Реализуя очередную версию алгоритма A* на Java, столкнулся с интересной ситуацией, связанной с коллекциями TreeSet и TreeMap.
Читать дальше →
Total votes 17: ↑14 and ↓3 +11
Views22.1K
Comments 22

Как получить по индексу элемент из бинарного дерева за приемлемое время?

ProgrammingAlgorithmsMathematics
Привет, Хабр!

Полгода назад я задумался, как можно было бы получить элемент из бинарного дерева за O(log(N)). Ответ пришёл довольно быстро — Lazy Propagation. Но реализовать это в коде я поленился. Сейчас надо сдавать дипломный проект в университете, поэтому я занимаюсь чем угодно, только не им. Именно так я и сел это реализовывать.
Читать дальше →
Total votes 11: ↑9 and ↓2 +7
Views3.7K
Comments 17

Понимаем красно-черное дерево. Часть 1. Введение

C++
Sandbox

Довольно долгое время я воевал с красно-черным деревом. Вся информация, которую я находил, была в духе "листья и корень дерева всегда черные, ПОТОМУ ЧТО", "топ 5 свойств красно-черного дерева" или "3 случая при балансировке и 12 случаев при удалении ноды". Такой расклад меня не устраивал.

Мне не хотелось заучивать свойства дерева, псевдокод и варианты балансировки, я хотел знать: почему. Каким образом цвета помогают при балансировке? Почему у красной ноды не может быть красного потомка? Почему глубину дерева измеряют "черной высотой"?

Ответы на эти вопросы я получил только тогда, когда мне дали ссылку на лекцию про два-три дерево, с которого мы и начнем.

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

Читать далее
Total votes 32: ↑31 and ↓1 +30
Views12.6K
Comments 6

Понимаем красно-черное дерево. Часть 2. Балансировка и вставка

C++
Tutorial

Это вторая часть из серии статей "Понимаем красно-черное дерево". Если вы пропустили первую часть, настоятельно рекомендую ознакомиться с ней здесь. Там мы разобрали причину появления кчд и расставили по полочкам некоторые его свойства.

В данной части мы разберем вставку и балансировку. Эти вещи идут бок о бок, без балансировки дерево будет терять свои свойства, и толка от него будет мало.

Читать далее
Total votes 18: ↑17 and ↓1 +16
Views4.9K
Comments 0