Красно-чёрное дерево - как вращать, если корень у прародителя? - PullRequest
Новая
       18

Красно-чёрное дерево - как вращать, если корень у прародителя?

3 голосов
/ 27 июля 2010

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

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

          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

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

Ответы [ 2 ]

3 голосов
/ 27 июля 2010

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

  1. Пусть P = Q левого ребенка.
  2. левый ребенок Q = правый ребенок P
  3. P заменяет Q как дочерний элемент своего родителя
  4. Правый ребенок Р = 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).

0 голосов
/ 27 июля 2010

Основываясь на ответе 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);
}
...