Обсуждение:АВЛ-дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
 
: {{tick | ticked=1}} оформи пункт «высота дерева» как теорему
 
: {{tick | ticked=1}} оформи пункт «высота дерева» как теорему
 
: {{tick}} переход m_{h+2} = m_h + m_{h + 1} + 1 к m_h = F_{h + 2} - 1 не очевиден, объяснить нормально. Последнее предложение в доказательстве надо тоже расписать попонятнее и поподробнее.
 
: {{tick}} переход m_{h+2} = m_h + m_{h + 1} + 1 к m_h = F_{h + 2} - 1 не очевиден, объяснить нормально. Последнее предложение в доказательстве надо тоже расписать попонятнее и поподробнее.
 +
:: {{tick}} Оформить это как лемму внутри доказательства теоремы, а то все намешано.
 
: {{tick | ticked=1}} Сделай пункт «Операции» и занеси в него их как подпункты
 
: {{tick | ticked=1}} Сделай пункт «Операции» и занеси в него их как подпункты
 
: {{tick | ticked=1}} ничего не написано про детали реализации, про то, что можно не хранить явно высоты, а использовать только -, =, +. Собственно, написать, что происходит с этими балансами при конкретных поворотах.
 
: {{tick | ticked=1}} ничего не написано про детали реализации, про то, что можно не хранить явно высоты, а использовать только -, =, +. Собственно, написать, что происходит с этими балансами при конкретных поворотах.
 
: {{tick}} Про удаление и добавление какая-то хрень, баланс надо изменять не всегда при подъеме.  Представь себе полное дерево глубины 3 (в нем 7 вершин). Удали любой лист, тогда ты изменишь баланс у какого-нибудь узла глубины 2, но у корня (узел глубины 1) баланс менять не надо, хотя мы в него придем. Собственно, из этого следует следующий пункт:  
 
: {{tick}} Про удаление и добавление какая-то хрень, баланс надо изменять не всегда при подъеме.  Представь себе полное дерево глубины 3 (в нем 7 вершин). Удали любой лист, тогда ты изменишь баланс у какого-нибудь узла глубины 2, но у корня (узел глубины 1) баланс менять не надо, хотя мы в него придем. Собственно, из этого следует следующий пункт:  
 
:: {{tick}} написать, в каких случаях в каждой операции можно остановиться и не продолжать балансировки.
 
:: {{tick}} написать, в каких случаях в каждой операции можно остановиться и не продолжать балансировки.
: {{tick}} вообще сейчас конспект представляет из себя наполовину копипасту википедии (еще от прошлого автора, видимо). Сделать так, чтобы он не был копипастой. Картинку, наверное, можно и оставить.
+
::: При удалении может произойти случай, что после поворота баланс остался равным 0, и тогда нужно дальше продолжать идти вверх. Почитай где-нибудь про это, в английской википедии, кажется, написано. --[[Служебная:Contributions/109.188.168.242|109.188.168.242]] 17:48, 27 марта 2012 (GST)
: {{tick}} написать про сливание авл-деревьев.
+
: {{tick | ticked=1}} вообще сейчас конспект представляет из себя наполовину копипасту википедии (еще от прошлого автора, видимо). Сделать так, чтобы он не был копипастой. Картинку, наверное, можно и оставить.
:: {{tick}} пункт про слияние надо в операции.
+
: {{tick | ticked=1}} написать про сливание авл-деревьев.
:: {{tick}} надо добавить картинки, поясняющие сливание.
+
:: {{tick | ticked=1}} пункт про слияние надо в операции.
: {{tick}} оформить нормально источники (длинное тире и надо писать Википедия, а не Wikipedia, так как статья русская)
+
:: {{tick | ticked=1} надо добавить картинки, поясняющие сливание.
 +
: {{tick | ticked=1}} оформить нормально источники (длинное тире и надо писать Википедия, а не Wikipedia, так как статья русская)
 +
: {{tick}} кажется, подписи к картинками сливания не соответствуют тексту.
 +
:: «Делаем новое дерево Q» — что, оно же у тебя уже подвешено
 +
:: «Корнем Q будет вершина d» — как она может быть корнем, если она подвешена к Q снизу.
 +
:: ну и тому подобное. Перечитай внимательно.

Версия 16:48, 27 марта 2012

надо сразу же писать что авл-дерево — сбалансированное
«Можно показать что высота» — надо показать, значит.
нужно больше интервики
ссылка в пункте «удаление вершины» должна быть внутренней.
сделай ссылку на наивную реализацию из поиска вершины, минимума/максимума/etc.
нормально оформить источники
добавить категории
а еще с авл-деревом было связано какое-то задание про несколько поворотов при удалении, как вспомню поточнее, напишу. --Дмитрий Герасимов 08:37, 6 февраля 2012 (MSK)


  • По-моему, в этом вики-конспекте лучше использовать слово "поворот", а не "вращение". Андрей Рыбак 05:50, 30 июня 2011 (UTC)
оформи пункт «высота дерева» как теорему
переход m_{h+2} = m_h + m_{h + 1} + 1 к m_h = F_{h + 2} - 1 не очевиден, объяснить нормально. Последнее предложение в доказательстве надо тоже расписать попонятнее и поподробнее.
Оформить это как лемму внутри доказательства теоремы, а то все намешано.
Сделай пункт «Операции» и занеси в него их как подпункты
ничего не написано про детали реализации, про то, что можно не хранить явно высоты, а использовать только -, =, +. Собственно, написать, что происходит с этими балансами при конкретных поворотах.
Про удаление и добавление какая-то хрень, баланс надо изменять не всегда при подъеме. Представь себе полное дерево глубины 3 (в нем 7 вершин). Удали любой лист, тогда ты изменишь баланс у какого-нибудь узла глубины 2, но у корня (узел глубины 1) баланс менять не надо, хотя мы в него придем. Собственно, из этого следует следующий пункт:
написать, в каких случаях в каждой операции можно остановиться и не продолжать балансировки.
При удалении может произойти случай, что после поворота баланс остался равным 0, и тогда нужно дальше продолжать идти вверх. Почитай где-нибудь про это, в английской википедии, кажется, написано. --109.188.168.242 17:48, 27 марта 2012 (GST)
вообще сейчас конспект представляет из себя наполовину копипасту википедии (еще от прошлого автора, видимо). Сделать так, чтобы он не был копипастой. Картинку, наверное, можно и оставить.
написать про сливание авл-деревьев.
пункт про слияние надо в операции.
{{tick | ticked=1} надо добавить картинки, поясняющие сливание.
оформить нормально источники (длинное тире и надо писать Википедия, а не Wikipedia, так как статья русская)
кажется, подписи к картинками сливания не соответствуют тексту.
«Делаем новое дерево Q» — что, оно же у тебя уже подвешено
«Корнем Q будет вершина d» — как она может быть корнем, если она подвешена к Q снизу.
ну и тому подобное. Перечитай внимательно.