Красно-Черное дерево уточняющие вопросы

Question

Я читал о красно-черных деревьях, и у меня есть два вопроса, которые беспокоили меня. Я все еще узнаю о них, извините, если они очевидны для более опытного программиста.

1. Если вы вставляете узел в красно-черное дерево, уравновешиваете дерево, а затем удаляете узел, это приводит к тому же самому дереву? Всегда ли это? Мне кажется, что это так, но я не совсем уверен.

2. Если вы удаляете красный узел без дочерних элементов, балансируете дерево, а затем повторно вставляете тот же самый узел, всегда ли получается одно и то же дерево? Всегда, иногда или никогда?

Опять же, извините, если есть тривиальные, я все еще учусь и не нашел хорошего ответа на эти вопросы. Заранее спасибо!

Answer 1

Ответ на ваш первый вопрос: no it does not lead to the same treeниже я показал пример:

         5(B)                        5(B)                   5(B)
     /          \        Del(3)    /      \     Ins(3)    /      \
   3(B)          9(B)    =====>   4(B)    9(B)  =====>  4(B)     9(B)
      \                                                 /
       4(R)                                          3(R)

Как видите, дерево изменилось.

Ответ на второй вопрос yes it always result in the same treeпотому что когда вы удаляете red node that has no children тогда не происходит перебалансировки, потому что не нарушается никаких правил, как родитель red node всегда black node и когда мы снова добавляем красный узел, он занимает то же место.

Вот ссылка на инструмент визуализации, который может помочь устранить ваши сомнения: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html