Красно-черное дерево - как повернуть, если корень - это дедушка и бабушка?

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

Древовидная структура:

          45             
        /    \
      40x      70        
     /  \     /
    7   41   50           
   / \
  6  39

Логика поворота говорит: «Повернуть с 45 (корень) в качестве вершины в направлении, которое поднимает X (т.е. 40)».

Итак, это означает правое вращение, и результат должен выглядеть так:

     40x  
    /   \
   7     45
 / \     / \
 6  39  41  70
           /
          50

Предположим, что узел 45 является прародителем, узел 7 — родителем, а узел 41 — текущим. (Я знаю, что порядок не имеет смысла, но, пожалуйста, не обращайте внимания, потому что я уже менялся один раз)

Код:

  //current is node 45
    //parent is node 7
    //grandparent is node 45 (root)

    //first detach cross node (i.e. 41)
    Node crossNode2 = grandparent.left.right;
    grandparent.left.right = null; //detach


                   45             
                /     \
              40x      70        
             /  \      /
            7   null   50           
           / \
          6  39

    grandparent.left = null;




                   45             
                 /    \
               null   70        
                      /
                    50           

    current.right = grandparent;

          40
        /    \
      7        45
     /  \     /  \
   6    39   null 70
                  /
                 50

    grandparent.left = crossNode2; //attach


         40  
        /   \
       7     45
     / \     / \
     6  39  41  70
               /
              50

Но почему-то этот код не работает. Когда я тестировал:

preorder
45, 39, 70, 50
breadth-first
45, 39, 70, 50

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

  45
 /  \
39  70
     /
    50

Может ли кто-нибудь дать мне советы, что не так с моим кодом вращения?


java rotation red-black-tree
person Meow    schedule 26.07.2010    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Шаг, чтобы сделать правое вращение на узле Q:

  1. Пусть P = левый ребенок Q.
  2. Левый ребенок Q = правый ребенок P
  3. P заменяет Q в качестве дочернего элемента своего родителя
  4. Правый ребенок P = Q

Вы пропустили шаг, выделенный жирным шрифтом, в предоставленном коде. Я думаю, ваша проблема в том, что вы рассматриваете повороты с участием корневого узла как особый случай. Очевидно, вы не можете сделать это, если Q является корнем, а его родителем является null. Попробуйте создать «головной» узел, правый узел которого является корнем. Это позволяет вращениям с участием корня работать с использованием обычных алгоритмов.

public static void rotateRight(Node node) {
    assert(!node.isLeaf() && !node.left.isLeaf());
    final Node child = node.left;
    node.setLeft(child.right);
    if (node.isRightChild())
         node.parent.setRight(child);
    else node.parent.setLeft(child);
    child.setRight(node);
}

Узел, который setRight и setLeft обновляет ссылку parent, а также обновляет right и left. Вызов node.isRightNode() может быть просто (node.parent.right == node).

person Gunslinger47    schedule 27.07.2010

arrow_upward
0
arrow_downward

Основываясь на ответе Gunslinger47, я также протестировал версию с левым вращением. Код работает нормально. (пожалуйста, дайте мне знать, если нет..)

Также задокументировано на моем сайте :)

http://masatosan.com/btree.jsp

public static void rotateLeft(Node node) {
    assert(!node.isLeaf() && !node.right != null);
    final Node child = node.right;
    node.setRight(child.left);
    if(node.isLeftChild()) {
        node.parent.setLeft(child);
    }
    else {
        node.parent.setRight(child);
    }
    chlid.setLeft(node);
}
person Meow    schedule 27.07.2010