Обсуждение:Splay-дерево - История изменений

Dgerasimov в 18:48, 3 мая 2012

2012-05-03T18:48:12Z

Dgerasimov в 12:25, 23 апреля 2012

2012-04-23T12:25:15Z

Dgerasimov в 11:44, 20 апреля 2012

2012-04-20T11:44:07Z

Dgerasimov в 10:39, 14 апреля 2012

2012-04-14T10:39:55Z

109.188.174.176 в 20:36, 11 апреля 2012

2012-04-11T20:36:22Z

Dgerasimov в 18:55, 8 апреля 2012

2012-04-08T18:55:50Z

Dgerasimov в 18:49, 8 апреля 2012

2012-04-08T18:49:59Z

Dgerasimov в 22:20, 6 апреля 2012

2012-04-06T22:20:30Z

Dgerasimov в 21:48, 6 апреля 2012

2012-04-06T21:48:36Z

Dgerasimov в 07:08, 31 марта 2012

2012-03-31T07:08:22Z

@@ Строка 28: / Строка 28: @@
 :{{tick | ticked=1}} какое-нибудь интервики. На бинарное дерево поиска(в операции Find, например).
 :: Почему ссылки внешние, а не внутренние? --[[Участник:Dgerasimov|Дмитрий Герасимов]] 15:44, 20 апреля 2012 (GST)
-: {{tick}} Кстати, из доказательства еще не очевидно, что splay работает за O(log n), там только в рангах выражено.
+: {{tick | tick }} Кстати, из доказательства еще не очевидно, что splay работает за O(log n), там только в рангах выражено.
 :: И что это, зачем ты вычитаешь O-величины? У тебя ранг равен ровно log N, а не O(log N).
 : {{tick | ticked=1}} Заголовки обычно обособляются как <nowiki>== Заголовок ==</nowiki>, а не <nowiki>= Заголовок =</nowiki>.

@@ Строка 26: / Строка 26: @@
 :{{tick | ticked=1}} еще пару слов сказать про сплей-деревья по неявному ключу.
 :: Надо просто объяснить, что также как в декартовом дереве по неявному ключу, можно поддерживать количество вершин в поддереве и легко его пересчитывать, а в остальном все операции делать аналогично ДД по неявному ключу.
-:{{tick}} какое-нибудь интервики. На бинарное дерево поиска(в операции Find, например).
+:{{tick | ticked=1}} какое-нибудь интервики. На бинарное дерево поиска(в операции Find, например).
 :: Почему ссылки внешние, а не внутренние? --[[Участник:Dgerasimov|Дмитрий Герасимов]] 15:44, 20 апреля 2012 (GST)
 : {{tick}} Кстати, из доказательства еще не очевидно, что splay работает за O(log n), там только в рангах выражено.
-: {{tick}} Заголовки обычно обособляются как <nowiki>== Заголовок ==</nowiki>, а не <nowiki>= Заголовок =</nowiki>.
+:: И что это, зачем ты вычитаешь O-величины? У тебя ранг равен ровно log N, а не O(log N).
 :{{tick|ticked=1}} «двоичное дерево поиска, позволяющее находить быстрее те данные, которые использовались недавно.». Гм, немного трешово, выглядит как определение. Лучше просто где-нибудь указать, что из преимуществ — быстрое обращение к частоиспользуемым данным.
 :{{tick|ticked=1}} Move to root — не операция, это одна из возможных эвристик, но которая не приводит ни к чему хорошему. Ее хорошо упомянуть, но не в операциях.
 :: Теперь она вообще внезапно появляется и неясно зачем. Почитай немного статью, которую я сказал и пойми, где тебе будет уместно упомянуть её и как.
 :: ок, подсказываю. Тебе нужно написать, что последний элемент, к которому обращались, перемещается в корень. Однако сделать это можно 2 способами. 1 — move to root. И вот тут пишешь что он не дает хорошей оценки времени работы. 2 — splay. и ссылаешься на уже описанный у тебя сплей. Для этого можно выделить подраздел перед операциями, можешь назвать его как-то вроде «Эвристики» ну или что-то подобное. Но в описании move to root нафиг не нужен.

@@ Строка 24: / Строка 24: @@
 :{{tick|ticked=1}}Ну в общем-то я ничего против википедии не имею, картинки там вроде адекватные.
 :{{tick | ticked=1}} Почему ничего нет про Find? Обязательно надо написать, что он тоже меняет дерево.
-:{{tick}} еще пару слов сказать про сплей-деревья по неявному ключу.
+:{{tick | ticked=1}} еще пару слов сказать про сплей-деревья по неявному ключу.
 :: Надо просто объяснить, что также как в декартовом дереве по неявному ключу, можно поддерживать количество вершин в поддереве и легко его пересчитывать, а в остальном все операции делать аналогично ДД по неявному ключу.
 :{{tick}} какое-нибудь интервики. На бинарное дерево поиска(в операции Find, например).
-:{{tick}} «двоичное дерево поиска, позволяющее находить быстрее те данные, которые использовались недавно.». Гм, немного трешово, выглядит как определение. Лучше просто где-нибудь указать, что из преимуществ — быстрое обращение к частоиспользуемым данным.
+:: Почему ссылки внешние, а не внутренние? --[[Участник:Dgerasimov|Дмитрий Герасимов]] 15:44, 20 апреля 2012 (GST)
-:{{tick}} Move to root — не операция, это одна из возможных эвристик, но которая не приводит ни к чему хорошему. Ее хорошо упомянуть, но не в операциях.
+: {{tick}} Кстати, из доказательства еще не очевидно, что splay работает за O(log n), там только в рангах выражено.
 :: Теперь она вообще внезапно появляется и неясно зачем. Почитай немного статью, которую я сказал и пойми, где тебе будет уместно упомянуть её и как.
 :: ок, подсказываю. Тебе нужно написать, что последний элемент, к которому обращались, перемещается в корень. Однако сделать это можно 2 способами. 1 — move to root. И вот тут пишешь что он не дает хорошей оценки времени работы. 2 — splay. и ссылаешься на уже описанный у тебя сплей. Для этого можно выделить подраздел перед операциями, можешь назвать его как-то вроде «Эвристики» ну или что-то подобное. Но в описании move to root нафиг не нужен.

@@ Строка 4: / Строка 4: @@
 : {{tick | ticked=1}} добавить категории
 : {{tick | ticked=1}} названия вершин в конспекте и на картинках совпадают чуть менее чем никак. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 19:23, 6 февраля 2012 (MSK)
-: {{tick}} нормально офромить источники
+: {{tick | ticked=1}} нормально офромить источники
 :: Ссылку на статью надо оформлять как
 :: Автор1, Автор2. Название статьи.
@@ Строка 14: / Строка 14: @@
 : {{tick | ticked=1}} раздел «определение» убрать, из него все запихать в шапку.
 : {{tick | ticked=1}} сплей-дерево — не самобалансируещееся, почитай определение сбалансированного дерева поиска. Баланс в нем не сохраняется.
-: {{tick}} про операции
+: {{tick | ticked=1}} про операции
 :: Как-то бредово выглядит в начале каждого подпункта название операции с ее аргументами. Либо напиши аргументы в заголовке, либо придумай что-то другое. Еще плохо выглядит написаение аргументов в техе, а остального - плейнтекстом. Либо все плейнтекстом, либо все в техе и заюзать \operatorname
 ::: Сначала пишут структуру, потом — аргументы (Split(Tree, key) и т.п.). Ну и либо пиши Tree везде(в Find) тоже, либо там где не надо, не пиши.
 :::: Все еще не исправлено. И про нее написан полнейший бред, почитай уже статью Тарьяна. --[[Служебная:Contributions/109.188.174.176|109.188.174.176]] 00:36, 12 апреля 2012 (GST)
-{{tick}}В Splay нумерации списка нет, пункты 1, 1 и 1. Там же надо написать, что удаляешь вершину b, потому что сначала неясно. А вообще вершинам на картинках лучше бы чуть более осмысленные имена, например, x, p(parent) и g(grandparent). --[[Участник:Dgerasimov|Дмитрий Герасимов]] 01:48, 7 апреля 2012 (GST)
+:{{tick | ticked=1}}В Splay нумерации списка нет, пункты 1, 1 и 1. Там же надо написать, что удаляешь вершину b, потому что сначала неясно. А вообще вершинам на картинках лучше бы чуть более осмысленные имена, например, x, p(parent) и g(grandparent). --[[Участник:Dgerasimov|Дмитрий Герасимов]] 01:48, 7 апреля 2012 (GST)
 : Да, в лемме тоже неплохо бы переименовать. И в тех в статье выделить x, p и g, да.--[[Служебная:Contributions/109.188.174.176|109.188.174.176]] 00:36, 12 апреля 2012 (GST)
-{{tick|ticked=1}}Я имею в виду, что из картинки не сразу ясно, какой вершине мы делаем splay, а в тексте этого явно не написано.
+:{{tick|ticked=1}}Я имею в виду, что из картинки не сразу ясно, какой вершине мы делаем splay, а в тексте этого явно не написано.
-{{tick|ticked=1}} А сделай Zig, Zig-Zig и Zig-Zag подпунктами Splay, тогда нормально смотреться будет. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 22:49, 8 апреля 2012 (GST)
+:{{tick|ticked=1}} А сделай Zig, Zig-Zig и Zig-Zag подпунктами Splay, тогда нормально смотреться будет. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 22:49, 8 апреля 2012 (GST)
-{{tick|ticked=1}}Ну в общем-то я ничего против википедии не имею, картинки там вроде адекватные.
+:{{tick|ticked=1}}Ну в общем-то я ничего против википедии не имею, картинки там вроде адекватные.
-{{tick | ticked=1}} Почему ничего нет про Find? Обязательно надо написать, что он тоже меняет дерево.
+:{{tick | ticked=1}} Почему ничего нет про Find? Обязательно надо написать, что он тоже меняет дерево.
-{{tick}} еще пару слов сказать про сплей-деревья по неявному ключу.
+:{{tick}} еще пару слов сказать про сплей-деревья по неявному ключу.

@@ Строка 10: / Строка 10: @@
 ::: Треш-статья все еще не убрана. Ссылку на английскую википедию добавь, да. Нужная тебе статья — первая ссылка по запросу «Tarjan splay tree» и первый референс в английской вики. Это Sleator, Daniel D.; Tarjan, Robert E. (1985), "Self-Adjusting Binary Search Trees". --[[Участник:Dgerasimov|Дмитрий Герасимов]] 22:49, 8 апреля 2012 (GST)
 ::: И вообще, почитай эту статью, в ней ни слова по сплей-деревья. Тебе другая статья нужна.
-: {{tick | ticked=}} раздел «определение» убрать, из него все запихать в шапку.
+: {{tick | ticked=1}} раздел «определение» убрать, из него все запихать в шапку.
 : {{tick | ticked=1}} сплей-дерево — не самобалансируещееся, почитай определение сбалансированного дерева поиска. Баланс в нем не сохраняется.
 : {{tick}} про операции
 :: Как-то бредово выглядит в начале каждого подпункта название операции с ее аргументами. Либо напиши аргументы в заголовке, либо придумай что-то другое. Еще плохо выглядит написаение аргументов в техе, а остального - плейнтекстом. Либо все плейнтекстом, либо все в техе и заюзать \operatorname
 :: Move to root — не операция, это одна из возможных эвристик, но которая не приводит ни к чему хорошему. Ее хорошо упомянуть, но не в операциях.
 ::: Теперь она вообще внезапно появляется и неясно зачем. Почитай немного статью, которую я сказал и пойми, где тебе будет уместно упомянуть её и как.
-:: В Splay нумерации списка нет, пункты 1, 1 и 1. Там же надо написать, что удаляешь вершину b, потому что сначала неясно. А вообще вершинам на картинках лучше бы чуть более осмысленные имена, например, x, p(parent) и g(grandparent). --[[Участник:Dgerasimov|Дмитрий Герасимов]] 01:48, 7 апреля 2012 (GST)
+:::: Все еще не исправлено. И про нее написан полнейший бред, почитай уже статью Тарьяна. --[[Служебная:Contributions/109.188.174.176|109.188.174.176]] 00:36, 12 апреля 2012 (GST)
-::: Я имею в виду, что из картинки не сразу ясно, какой вершине мы делаем splay, а в тексте этого явно не написано.
+{{tick}}В Splay нумерации списка нет, пункты 1, 1 и 1. Там же надо написать, что удаляешь вершину b, потому что сначала неясно. А вообще вершинам на картинках лучше бы чуть более осмысленные имена, например, x, p(parent) и g(grandparent). --[[Участник:Dgerasimov|Дмитрий Герасимов]] 01:48, 7 апреля 2012 (GST)
-::: А сделай Zig, Zig-Zig и Zig-Zag подпунктами Splay, тогда нормально смотреться будет. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 22:49, 8 апреля 2012 (GST)
+: Да, в лемме тоже неплохо бы переименовать. И в тех в статье выделить x, p и g, да.--[[Служебная:Contributions/109.188.174.176|109.188.174.176]] 00:36, 12 апреля 2012 (GST)
-::: Ну в общем-то я ничего против википедии не имею, картинки там вроде адекватные.
+{{tick|ticked=1}}Я имею в виду, что из картинки не сразу ясно, какой вершине мы делаем splay, а в тексте этого явно не написано.
 {{tick | ticked=1}} Почему ничего нет про Find? Обязательно надо написать, что он тоже меняет дерево.

@@ Строка 1: / Строка 1: @@
-: {{tick}} саморегулирующееся? o_O
+: {{tick | ticked=1}} саморегулирующееся? o_O
-: {{tick}} "Основной идей для сохранение "
+: {{tick | ticked=1}} "Основной идей для сохранение "
-: {{tick}} Сделать отдельный раздел "опреации", в него их запихать как подразделы
+: {{tick | ticked=1}} Сделать отдельный раздел "опреации", в него их запихать как подразделы
-: {{tick}} добавить категории
+: {{tick | ticked=1}} добавить категории
-: {{tick}} названия вершин в конспекте и на картинках совпадают чуть менее чем никак. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 19:23, 6 февраля 2012 (MSK)
+: {{tick | ticked=1}} названия вершин в конспекте и на картинках совпадают чуть менее чем никак. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 19:23, 6 февраля 2012 (MSK)
 : {{tick}} нормально офромить источники

← Предыдущая		Версия 07:08, 31 марта 2012
Строка 4:		Строка 4:
	: {{tick}} добавить категории		: {{tick}} добавить категории
	: {{tick}} названия вершин в конспекте и на картинках совпадают чуть менее чем никак. --[[Участник:Dgerasimov\|Дмитрий Герасимов]] 19:23, 6 февраля 2012 (MSK)		: {{tick}} названия вершин в конспекте и на картинках совпадают чуть менее чем никак. --[[Участник:Dgerasimov\|Дмитрий Герасимов]] 19:23, 6 февраля 2012 (MSK)
		+	: {{tick}} нормально офромить источники