Как легко запомнить вставку и удаление красно-черного дерева?
Довольно легко полностью понять стандартное дерево двоичного поиска и его операции. Благодаря такому пониманию мне даже не нужно запоминать реализации этих операций вставки, удаления и поиска.
Сейчас я изучаю Красно-Черное дерево, и я понимаю его свойства для поддержания баланса дерева. Однако мне очень трудно понять его процедуры вставки и удаления.
Я понимаю, что при вставке нового узла мы отмечаем этот узел как красный (потому что красный - это лучшее, что мы можем сделать, чтобы избежать нарушения меньшего количества законов красно-черного дерева). Новый красный узел все еще может нарушать «закон отсутствия непрерывных красных узлов». Затем мы исправляем это с помощью:
проверяем цвет его дяди, если он красный, затем отмечаем его родителя и дядю как черных и переходим к бабушке и дедушке.
если это правый дочерний элемент, повернуть его влево
пометить его родительский элемент черным, а его прародителя красным, затем повернуть вправо его прародителя.
сделано (в основном, как указано выше).
Многие места описывают вставку красно-черного дерева, как указано выше. Они просто говорят вам, как это сделать. Но почему эти шаги могут исправить дерево? Почему сначала повернуть влево, а затем повернуть вправо?
Может ли кто-нибудь объяснить, почему мне более ясно, даже более ясно, чем CLRS? В чем заключается магия вращения?
Я действительно хочу понять, поэтому через год я могу реализовать Красно-Черное дерево самостоятельно, не просматривая книгу.
Спасибо