Arbre rouge-noir - comment faire pivoter si la racine est le grand-parent?

Question

Je travaille moi-même sur l'écriture de l'arbre rouge-noir. Mais quand je teste la rotation qui implique la rotation de la racine, elle perd quelque peu sa référence.

Structure arborescente:

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

La logique rotate dit: "Rotation 45 (racine) en haut, dans la direction qui soulève X (soit 40)"

Cela signifie donc tourner à droite et le résultat devrait ressembler à:

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

En supposant que le noeud 45 est un grand-parent et 7 est parent et 41 est en cours. (Je sais que l'ordre n'a pas de sens, mais s'il vous plaît ne pas tenir compte, c'est parce que je l'ai déjà fait pivoter une fois)

code:

//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 

Mais en quelque sorte ce code ne fonctionne pas. Quand je l'ai testé:

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

Je pense donc que le résultat est en fait:

45 
/\ 
39 70 
    /
    50 

Quelqu'un pourrait-il me donner des conseils ce qui ne va pas avec mon code de rotation?

Answer 1

étape pour faire une rotation à droite sur le noeud Q:

1. Soit P = enfant gauche de Q.
2. enfant gauche Q = enfant droit P
3. P remplace Q comme l'enfant de son parent
4. P de l'enfant droite = Q

vous manque l'étape gras dans votre code fourni. Je pense que votre problème est de traiter des rotations impliquant le nœud racine comme un cas particulier. Évidemment, vous ne pouvez pas faire cela si Q est la racine et que son parent est null. Essayez de créer un noeud "tête" dont le noeud droit est la racine. Cela permet aux rotations impliquant la racine de travailler en utilisant des algorithmes normaux.

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); 
} 

nœud qui setRight et setLeft garder la référence parent mise à jour ainsi que la mise à jour right et left. L'appel node.isRightNode() peut être simplement (node.parent.right == node).

Answer 2

Basé sur la réponse de Gunslinger47, j'ai testé la version de rotation gauche aussi. Le code fonctionne correctement. (S'il vous plaît ne laissez-moi savoir si pas ..)

également documenté sur mon site :)

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); 
}