Реализация метода splay() для дерева двоичного поиска

Question

Я пытаюсь реализовать метод splay (Node x) для двоичного дерева поиска. У меня есть методы leftRotation (Node x) и rightRotation (Node x), которые реализованы правильно (по крайней мере, я думаю, что они ...), но когда я пытаюсь реализовать их в методе splay (Node x), он вызывает себя в бесконечная петля. Теперь я знаю, почему это так, но не может понять, как это исправить.

Вот метод leftRotation (Node х):

public void leftRotation(Node<E> x) { 
    if (x.getRightChild() == null) { 
     return; 
    } 

    Node<E> y = x.getRightChild(); 
    x.setRightChild(y.getLeftChild()); 

    if (y.getLeftChild() != null) { 
     y.getLeftChild().setParent(x); 
    } 

    y.setParent(x.getParent()); 

    if (x.getParent() == null) { 
     root = y; 
    } else { 
     if (x == x.getParent().getLeftChild()) { 
      x.getParent().setLeftChild(y); 
     } else { 
      x.getParent().setRightChild(y); 
     } 
    } 

    y.setLeftChild(x); 
    x.setParent(y); 
} 

Вот метод rightRotation (Node х):

public void rightRotation(Node<E> x) { 
    if (x.getLeftChild() == null) { 
     return; 
    } 

    Node<E> y = x.getLeftChild(); 
    x.setRightChild(y.getRightChild()); 

    if (y.getRightChild() != null) { 
     y.getRightChild().setParent(x); 
    } 

    y.setParent(x.getParent()); 

    if (x.getParent() == null) { 
     root = y; 
    } else { 
     if (x == x.getParent().getRightChild()) { 
      x.getParent().setRightChild(y); 
     } else { 
      x.getParent().setLeftChild(y); 
     } 
    } 

    x.setRightChild(x); 
    x.setParent(y); 
} 

А вот метод расширяемого (Node х):

public void splay(Node<E> x) { 
    while (x.getParent() != null) { 
     if (x.isLeftChild && x.getParent().isLeftChild) { 
      this.rightRotation(x.getParent()); 
      this.rightRotation(x); 
     } else if (x.isRightChild && x.getParent().isRightChild) { 
      this.leftRotation(x.getParent()); 
      this.leftRotation(x); 
     } else if (x.isLeftChild && x.getParent().isRightChild) { 
      this.rightRotation(x); 
      this.leftRotation(x); 
     } else if (x.isRightChild() && x.getParent().isLeftChild()) { 
      this.leftRotation(x); 
      this.rightRotation(x); 
     } else if (x.isLeftChild && x.getParent() == root) { 
      this.rightRotation(x); 
     } else if (x.isRightChild && x.getParent() == root) { 
      this.leftRotation(x); 
     } 
    } 
} 

Любые идеи о том, как исправить бесконечный цикл? Кажется, что это связано с тем, что он не вырвался из инструкции while (x.getParent()! = Null) в методе splay (Node x), но когда я просмотрел код с помощью отладчика, свойства узел, казалось, менялся, поэтому я не знаю, где это происходит?

setLeftChild (Node LeftChild) метод:

public void setLeftChild(Node<E> leftChild) { 
     this.leftChild = leftChild; 

     if (leftChild != null) { 
      leftChild.setIsRightChild(true); 
      leftChild.setParent(this); 
     } 
    } 

Answer 1

Помимо всех ошибок/плохих вещей, которые я указал в своем коде, здесь является самым большим, в rightRotation:

x.setRightChild(x); 

Это создает цикл в вашем дереве, следовательно, бесконечный цикл. У вас должен быть модуль, проверенный вашими методами. Еще одна серьезная ошибка в вашем коде заключается в том, что в ваших инструкциях if - else if нет else, поэтому могут быть случаи, когда во время итерации ничего не происходит ... следовательно, бесконечный цикл. Это не так, потому что вы рассмотрели все случаи (на самом деле, вы считали, что еще больше, а два последних никогда не будут выполнены, поскольку четыре первых случая охватывают все возможные случаи), но, как общее замечание, это было действительно опасно для кода это так.

Вот код моей собственной реализации всех этих методов, которые я считаю более чистый:

public class BinaryTree<T extends Comparable<T>> { 
    private Node<T> root; 

    public void rebalance(Node<T> node) { 
     while (!node.isRoot()) rotation(node.getParent(), node.getChildKind().opposite()); 
    } 

    private void rotation(Node<T> node, Side side) { 
     if (node.getChild(side.opposite()) == null) return; 

     Node<T> sideChild = node.getChild(side.opposite()); 
     node.setChild(sideChild.getChild(side), side.opposite()); 

     if (node.getParent() == null) setRoot(sideChild); 
     else       node.getParent().setChild(sideChild, node.getChildKind()); 

     sideChild.setChild(node, side); 
    } 

    private void setRoot(Node<T> root) { 
     this.root = root; 
     if (root != null) root.setRoot(); 
    } 

    private static enum Side { 
     LEFT, RIGHT; 

     public Side opposite() { return this == LEFT ? RIGHT : LEFT; } 
    } 

    private static class Node<T extends Comparable<T>> { 
     private T value; 
     private Node<T> left, right, parent; 

     public Node(T value) { this(value, null, null, null); } 

     public Node(T value, Node<T> left, Node<T> right, Node<T> parent) { 
      setValue (value); 
      setLeft (left ); 
      setRight (right); 
      setParent(parent); 
     } 

     public Node<T> setLeft(Node<T> left) { 
      this.left = left; 
      if (left != null) left.parent = this; 
      return this; 
     } 

     public Node<T> setRight(Node<T> right) { 
      this.right = right; 
      if (right != null) right.parent = this; 
      return this; 
     } 

     public Node<T> setChild(Node<T> child, Side side) { return side == Side.LEFT ? setLeft(child) : setRight(child); } 

     public Node<T> setRoot() { return setParent(null); } 

     private Node<T> setParent(Node<T> parent) { 
      this.parent = parent; 
      return this; 
     } 

     public Node<T> setValue(T value) { 
      this.value = notNull(value); 
      return this; 
     } 

     public boolean isRoot() { return parent == null; } 

     public boolean isLeftChild() { return isRoot() || getParent().getValue().compareTo(getValue()) > 0; } 
     public boolean isRightChild() { return isRoot() || !isLeftChild()         ; } 

     public Node<T> getChild(Side side) { return side == Side.LEFT ? getLeft() : getRight(); } 

     public Side getChildKind() { 
      Check.isFalse(isRoot(), "This method is not defined on root nodes"); 
      return isLeftChild() ? Side.LEFT : Side.RIGHT; 
     } 

     public T  getValue() { return value ; } 
     public Node<T> getLeft () { return left ; } 
     public Node<T> getRight() { return right ; } 
     public Node<T> getParent() { return parent; } 
    } 
} 

Примечание: мое дерево не всегда оптимально сбалансированы. Я сделал это из головы, но я проверю в Википедии, чтобы увидеть, что они говорят, я, вероятно, не применял правильный алгоритм, но он работает очень хорошо, уже ожидая в патологических случаях.