Обсуждение:Декартово дерево

☑ зачем-то tree + heap написано в техе.

По-моему, так лучше выглядит (мимокрокодил) SkudarnovYaroslav 19:52, 6 февраля 2012 (MSK)

☑ Убрать «описание», запихать его в шапку статьи. --Дмитрий Герасимов 14:04, 14 апреля 2012 (GST)

либо везде используй [math] X [/math], либо везде [math] x [/math]. Лучше маленькие буквы, имхо. Тут же написать, что x — ключ, а y — приоритет.

☑ Добавить интервики. Тут и бинарное дерево поиска, и куча, и на неявный ключ, и на случайную величину, и на линейность матожидания можно сослаться.

☑ написать, как строить декартово дерево за O(n), если заранее есть ключи в возрастающем порядке.

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

Ну а h у нас может быть O(n). Напиши сразу, что O(n^2) и все.

☑ «делаем шаг по склону вверх» — ээ, какая-то упоротая фраза.

☑ вообще ничего нет про кприоритет, как он выбирается и все такое.

☑ запилить доказательство логарифмической оценки высоты дерева.

☑ операции лучше объединить в один раздел, а виды опреаций сделать подразделами

☑ к split и merge неплохо бы небольшой псевдокод.

Почитай правила оформления псевдокода.--Дмитрий Герасимов 16:50, 21 апреля 2012 (GST)

☑ "Реализация №1:" -- зачем двоеточие в названии раздела?

☐ Написать, чем отличаются реализации 1 и 2 друг от друга.

Наверное, они отличаются не тем, что не используется merge или split, а в том, что просто их меньше во второй реализации?--Дмитрий Герасимов 16:40, 28 апреля 2012 (GST)

И писать «этот вариант отличается» надо либо после объявления реализации № 2, либо вообще после неет.

☑ А вообще почему-то реализация 1 расписана по пунктом, а во второй все сплошным текстом.

☑ добавить категории --Дмитрий Герасимов 19:11, 6 февраля 2012 (MSK)

☑ нет источников --Андрей Рыбак 12:36, 25 марта 2012 (GST)

☐ доказательство:

☐«являются незавимыми непрерывными случайными величинами с одинаковым вероятностным распределением» — непрерывные случайные величины? Гм, вроде этого не было в курсе дискретки, ну это еще интуитивно более-менее ясно. А вот что такое «одинаковое распределение»?

«с одного и того же распределения» — бред. возьмем для приортиетов нечестную монету (или что-то подобное), она может давать независимые случайные величины, но для приоритетов не подходит.

Все еще не исправлено --Дмитрий Герасимов 11:44, 26 апреля 2012 (GST)Вставьте сюда текст, который не нужно форматировать

НЕ ИСПРАВЛЕНО!!!!!1111 --Дмитрий Герасимов 16:40, 28 апреля 2012 (GST)

вот эта запись x_i — ancestor x_j — не очень. Во-первых, ancestor of, а во-вторых, «—» как-то неуместно. Лучше x_i is ancestor of x_j, в общем.

«использовали линейность математического ожидания E» — эм, просто линейность математического ожидания, зачем значок E тут?

В X_k,i у индексов тех поехал.

«минимальный приоритет в treap’е» — в treap'е -> в декартовом дереве

Как-то доказательство пошло сначала с индукционного перехода, а потом к базе. Надо бы наоборот.

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

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

И обозначай в тех логарифм не как ln, а как \ln.

☑ У тебя merge в техе в разных местах по-разному написан, то [math] Merge [/math], то [math]\operatorname{Merge}[/math].

☐ «Построение декартово дерева»

все еще не исправлено...--Дмитрий Герасимов 16:40, 28 апреля 2012 (GST)