Утверждение в начале этой статьи о том, что «каждый узел в дереве козла отпущения отслеживает размер и высоту поддерева, корнем которого является этот узел, а также то, был ли этот узел удален», просто неверно. В первом предложении второго абзаца Аннотация оригинальной статьи Гальперина и Ривеста говорится: «Деревья козла отпущения, в отличие от большинства схем сбалансированного дерева, не требуют хранения дополнительных данных (например, «цветов» или «весов») в дереве. узлы».
Согласен, я это заметил. Поэтому я решил набраться смелости и потерять свою первую статью, переписанную для деревьев козлов отпущения =) обратная связь приветствуется... и любая помощь, чтобы довести ее до номинала, приветствуется. Темания 18:59, 16 февраля 2007 г. (UTC)
В описании операции удаления предполагается альфа 0,5. Действительно, правило должно быть написано «NodeCount <= MaxNodeCount * alpa». Себарбер ( обсуждение ) 17:03, 16 августа 2009 г. (UTC)
«Как только «козёл отпущения» найден, выполняется стандартная операция по перебалансировке двоичного дерева поиска». Либо статью BST следует отредактировать, чтобы объяснить, что такое «стандартная» операция, либо статья должна разъяснять больше. Это неоднозначно, потому что неясно, хотите ли вы выполнить только один поворот (как в случае с деревьями, которые остаются строго сбалансированными) или несколько поворотов, потому что дерево остается только «слабо» сбалансированным. На самом деле, затем сравниваются красно-черные деревья, и кажется, что красно-черные деревья используют вращения *в отличие* от того, что делают деревья-козлы отпущения. Глядя на оригинальную статью, это тоже не объясняет. —Предыдущий неподписанный комментарий добавлен пользователем 192.160.124.68 ( обсуждение ) 16:23, 12 мая 2010 г. (UTC)
Эй, похоже, кто-то обновил это. Теперь ситуация немного лучше, но все еще не объясняет, как работает операция ребалансировки. Он объясняет, как выбрать узел для ребалансировки, но не объясняет, что вы на самом деле с ним делаете. «Выполняется стандартная операция ребалансировки». Глядя на статью еще раз, кажется, что он по сути предлагает перестроить все поддерево (перебрать его по порядку, скопировать в массив, затем разделить и покорить массив, чтобы создать новое дерево). Но в статье более подробно рассматривается способ сделать это на месте (без дополнительного использования памяти), который кажется специфичным для козлиных деревьев; в других статьях о типах деревьев обычно есть псевдокод для всех шагов и/или объяснение операций, специфичных для конкретного типа дерева, поэтому я не думаю, что это было бы здесь неуместно. —Предыдущий неподписанный комментарий добавлен пользователем 192.160.124.68 ( обсуждение ) 14:59, 13 мая 2010 г. (UTC)
Привет, похоже, что идея дерева козла отпущения основана на "BST ограниченного баланса", они даже цитируют в своей работе Дж.Нивергельта. BB-деревья очень легко реализовать и обладают множеством полезных свойств, особенно для функциональных языков. Есть ли статья об этом в википедии? Дополнительная информация: http://groups.csail.mit.edu/mac/users/adams/BB/index.html , статья на польской вики: http://pl.wikipedia.org/wiki/Drzewo_o_ograniczonym_zrównoważeniu-- 149.156.82.207 ( обсуждение ) 19:42, 2 августа 2010 г. (UTC)