Red Black Tree Insertion Вопросы, зачем вращать?

Итак, у меня есть красное черное дерево следующим образом:

2 = Root Black
Children = 1 (Black/Left), 4 (Red/Right)
Children of 1 = NIL & NIL => Height of Black Subtree is then 2 
Children of 4 = 3 (Black/Left), 5 (Black/Right)
Children of 3 = NIL & NIL, Height of Black Subtree is then 2 
Children of 5 = 7 (Red/Right)& NIL, Height is still then of course 2.

Итак, когда я вставляю 6 (конечно, цвет красный), и он становится левым дочерним элементом 7. В этом веб-приложении, за которым я следую, он выполняет вращение 6 с 7. Почему? Насколько я вижу, это не нарушает никаких свойств RBT.

Примечание. Исходное веб-приложение — это веб-приложение Java, для которого требуется версия 1.7. Источник: http://gauss.ececs.uc.edu/RedBlackTester/redblack.html


red-black-tree
person pmac89    schedule 08.05.2013    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Свойства RBT таковы.

  1. Каждый узел либо красный, либо черный.
  2. Корень и листья (NIL) черные.
  3. Если узел красный, то его родитель черный.
  4. Все простые пути от любого узла x к дочернему листу имеют одинаковое количество черных узлов = высота черного (x).

Итак, если 7 красный, а когда добавляется 6, он также красный, это нарушает 3-е свойство, следовательно, вращение и изменения для устранения нарушений.

person pulasthi    schedule 08.05.2013
comment
Да, я понял это ... ха-ха, мой плохой. Я чувствовал себя идиотом. Вот ссылка на ютуб с ответом. youtube.com/watch?v=uI4smUPz-Yw - person pmac89; 08.05.2013