Обсуждение:Красно-чёрное дерево

Untitled

Не понятно что имеется ввиду под кратчайшим путём в данном контексте. Lizz 21:23, 11 декабря 2007 (UTC)

"Корень и листья окрашены в чёрный цвет (источник ?)" - здесь имеется ошибка. Это определение взято из книги "Алгоритмы", но там авторы специально оговорили, что под листьями подразумеваются NIL-элементы. Без этой оговорки вышеуказанная фраза вводит в заблуждение. -- Leonido, 12 мая 2008 г.

Господа, что-то странная ассимптотика? "Следовательно, при том же количестве листьев красно-чёрное дерево может быть выше АВЛ-дерева, но не более чем в ..." - Судя по ассимптотике как раз получается наоборот!!! 195.218.186.254 16:25, 16 июля 2010 (UTC)Alexei

"Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов." Одинаковое с чем, равное чему число?(Свойства К-Ч деревьев, пункт 5) --93.127.11.141 17:25, 3 октября 2011 (UTC)

Чему угодно может быть равно. Главное лишь, что это число одно и то же для всех путей и приведённые алгоритмы вставки и удаления гарантируют, что оно и останется одинаковым. -- X7q 18:42, 3 октября 2011 (UTC)

"В журнале были доступны две краски, красная и чёрная" - чушь какая-то. "Чёрное и Красное" - классическое противопоставление двоичных вариантов в азартных играх (картах, рулетке). 84.54.251.35 04:06, 8 июня 2012 (UTC)

Классическое оно или нет, но любое название когда-нибудь появляется в первый раз.  — Эта реплика добавлена участником 178.49.47.197 (о · в) 12 февраля 2013

Седжвик:

A lot of people ask why did we use the name

red-black. Well we invented this data structure, this way of looking at balanced trees, at Xerox PARC which was the home of the personal computer and many other innovations that we live with today [...] But one of the things that was invented there, was the laser printing and we were very excited to have nearby color laser printer that could print things out in color and out of the colors, the red looked the best. So, that's why we picked the color red to distinguish red links the types of links

in tree nodes.

[1], Red-Black BSTs, 31:55 --Anton Khorev 11:54, 12 апреля 2013 (UTC)

В разделе "удаление":

• Если M имеет не листового потомка, возьмем его за C. В противном случае за C возьмем любой из листовых потомков. Что значит "не имеет листового потомка", если выше написано, что листьями являются чёрные NIL-ноды?
• Если M является красным узлом, заменим его своим потомком C, который по определению должен быть чёрным. (Это может произойти только тогда, когда...
  • "своим потомком"? А если у меня нет потомков? Холостяк я и детей заводить не собираюсь.
  • Что "это"? Что может произойти только тогда? M окажется красным узлом? Или потомок окажется чёрным?
• кроме того, общее соображение, если уж хочется вырезать при переводе текст кусками, то надо вырезать скобки, содержащие по пол-абзаца текста.

Складывается ощущение, что с русским языком у переводчика ещё хуже, чем с пониманием описываемого алгоритма.

Не совсем хорошо, что нет алгоритмов левого и правого поворота.

Не описан толком такой момент: вот перекрасили дядю и родителя в чёрный, а дедушку в красный. Если дедушка - корень: либо его надо перекрасить в чёрный по правилу о корне, и тогда будут чёрные потомки у чёрного предка в нарушение чередования; либо надо перекрасить всё дерево, и тогда листья станут красными; либо оставить корень красным. Как-то этот надо более широко раскрыть. 31.204.174.104 16:35, 25 февраля 2016 (UTC)

Не рассмотрен случай, когда удаляемый узел чёрный, его предок красный, брат черный и имеет ДВУХ красных детей. Unegare (обс.) 08:07, 2 мая 2019 (UTC)

Недочёт в случае delete_case2

Попытался сам вывести случаи и обнаружил, что у меня не совсем совпадает случай №2, точнее в моём случае S красится черным, а S_L или S_R красится в красный. Затем происходит вращение. После проделанных манипуляций дерево будет соответствовать всем свойствам.

void delete_case2(struct node *n)
{
	struct node *s = sibling(n);

	if (s->color == RED){
	   s->color = BLACK;		
		if (n == n->parent->left){
			s->left->color = RED;
			rotate_left(n->parent);
		}
		else{
			s->right->color = RED;
			rotate_right(n->parent);
		}
	else
		delete_case3(n);
}

Посмотрел внимательно случай delete_case2 из статьи и обнаружил, что после случая 2 дерево восстанавливает свойства уже в случае delete_case4, т.е. меняет местами цвета P и S, т.е. приходит к такому же результату, к какому пришёл я. Получается код delete_case2 из статьи можно заменить кодом, который я привёл.

P.S. Статья слишком сложная, нет никаких взаимосвязей между описанными случаями. Её можно намного проще расписать так, что её поймёт даже первоклассник. 188.92.2.208 16:13, 3 октября 2016 (UTC)