Red Black Tree Rule Enforcement в Java

Question

Я пытаюсь реализовать Red-Black Tree в Java. Чтобы сделать это, я разрешаю каждой вставке, как если бы это был BST, а затем post-insert I pre-order пересекаю дерево и проверяю каждый Node (который я называю Word, поскольку я использую его для приложения словаря), что Красно-Черные правила выполнены. До сих пор это выглядит так

private void checkRedBlackRules(Word w) 
    { 

     //Checking for Red-Red sequence 
     Word leftChild = w.getLeft(); 
     Word rightChild = w.getRight(); 
     Word leftleftGC, leftrightGC, rightleftGC, rightrightGC; 
     if(leftChild != null) 
     { 
      leftleftGC = leftChild.getLeft(); 
      leftrightGC = leftChild.getRight(); 
     } 
     else 
     { 
      leftleftGC = null; 
      leftrightGC = null; 
     } 
     if(rightChild != null) 
     { 
      rightleftGC = rightChild.getLeft(); 
      rightrightGC = rightChild.getRight(); 
     } 
     else 
     { 
      rightleftGC = null; 
      rightrightGC = null; 
     } 
     try 
     { 
      if(leftChild.isRed() && leftleftGC.isRed()) 
      { 
       rotateRight(w, leftChild, leftleftGC); 
      } 
     } 
     catch(NullPointerException e) {} 
     try 
     { 
      if(leftChild.isRed() && leftrightGC.isRed()) 
      { 

      } 
     } 
     catch(NullPointerException e) {} 
     try 
     { 
      if(rightChild.isRed() && rightleftGC.isRed()) 
      { 

      } 
     } 
     catch(NullPointerException e) {} 
     try 
     { 
      if(rightChild.isRed() && rightrightGC.isRed()) 
      { 
       rotateLeft(w, leftChild, leftrightGC); 
      } 
     } 
     catch(NullPointerException e) {} 
     if(w.getLeft() != null) 
      checkRedBlackRules(w.getLeft()); 
     if(w.getRight() != null) 
      checkRedBlackRules(w.getRight()); 
    } 

    private void rotateLeft(Word parent, Word child, Word grandChild) 
    { 
     child = parent; 
     child.setLeft(parent); 
     child.setRight(grandChild); 
    } 
    private void rotateRight(Word parent, Word child, Word grandChild) 
    { 
     child = parent; 
     child.setLeft(grandChild); 
     child.setRight(parent); 
    } 

Однако, когда я пытаюсь добавить более двух элементов к дереву, она застревает в бесконечном цикле, пока не произойдет ошибка StackOverflow.

Answer 1

Не углубляясь через всю логику в деталях, Rotate функции выглядят неправильно меня:

private void rotateLeft(Word parent, Word child, Word grandChild) 
{ 
    child = parent; 
    child.setLeft(parent); 
    child.setRight(grandChild); 
} 

Параметр ребенок не используется, и вместо того, чтобы немедленно родителю. Это означает, что когда вы вызываете child.setLeft (parent), вы устанавливаете левый дочерний элемент исходного родителя себе, что, по моему мнению, вызывает бесконечный цикл (и, следовательно, переполнение стека).