1
Есть ли простой способ запомнить методы вращения для красно-черных деревьев?Есть ли простой способ запомнить методы вращения для красно-черных деревьев?
A
ответ
1
Нет. Невозможно запомнить! (Ну, не совсем, но это самый подходящий ответ в отношении использования вами собственного времени).
Знаете что? Никому не нужен, чтобы читать точную механику поворота. Даже не многие люди, необходимые для их реализации, должны помнить о них! См. Java's implementation of TreeMap, который является красно-черным деревом, и найдите «От CLR». Они в основном скопировали код, , который точно соответствует правильному курсу здесь.
+0
ну на самом деле есть: если вы ищете 2-3-4 дерева и btree – zinking
2
Возможно, они ищут эквивалентность 2-3-4 деревьев (B-деревья степени 2) и красно-черных деревьев?
Я всегда находил вставку в B-Trees легче понять, чем вставка в красно-черных деревьях.
Смотрите страницу здесь: http://www.eli.sdsu.edu/courses/fall95/cs660/notes/RedBlackTree/RedBlack.html
В любом случае, вы, вероятно, можете просто вывести обороты, необходимые на месте, это на самом деле не так сложно, как только вы были знакомы с ними.
Я не вижу смысла заставлять себя помнить о них. Если вы будете использовать красно-черные деревья, то вы в конце концов узнаете их наизусть. Если вы этого не сделаете, зачем заставлять себя помнить их? Просто посмотрите их, когда вам это нужно. Кроме того, я предлагаю заглянуть в treaps. Они очень эффективны и имеют только два типа вращения. – IVlad
Это использовалось как вопрос для интервью. – zooropa
Перейдите к следующему собеседованию. Никто не попросит вас снова. –