Объясните, почему вставка (и различные случаи) не изменяет высоту черного цвета у красных черных деревьев

Question

Объясните, почему вставка (и различные случаи) не изменяет высоту черного цвета у красных черных деревьев

красное черное дерево - вставка - дядя з красный

Почему черная высота узла γ(гамма, самый верхний узел) не меняется после операции?

Я знаю, как объяснить, почему высота черного T1 - T4 одинакова после операции. Но что касается гаммы, я понятия не имею.

У кого-нибудь есть идеи?

1

algorithm binary-tree binary-search-tree red-black-tree red-black-tree-insertion

Источник

user1925052 13 окт '18 в 19:34

1 ответ

Решение

Другие вопросы по тегам algorithm binary-tree binary-search-tree red-black-tree red-black-tree-insertion

user4271966 13 окт '18 в 19:48 2018-10-13 19:48 · Accepted Answer · 2018-10-13 19:48

Итак, вставка Alpha была сделана, и она была закодирована красным. Теперь после вставки код вставки дерева RB проверит дисбаланс между красным и черным цветами, чтобы определить, должно ли происходить вращение. После проверки, что бета-узел стал черным, Y-узел стал красным, а гамма-узел стал черным, что позволило сбалансировать дерево RB без необходимости вращения.

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

см. выше ссылку на вики, чтобы получить полное объяснение того, как происходит переключение цвета и почему и как оно помогает определить необходимый поворот / с.