Java 二叉树 : How to balance a tree in the insert method?

Question

我正在尝试让二叉搜索树保持平衡，我知道为什么它不起作用，但我不知道如何修复它。我直接在insert方法中进行平衡。我加了一些斜杠来标记应该在哪里进行平衡。像这样，代码不起作用，我得到这个异常:

Exception in thread "main" java.lang.NullPointerException
at Baueme.Treee.insert(Treee.java:54)
at Baueme.Treee.insert(Treee.java:18)
at Baueme.TestTheTree.main(TestTheTree.java:12)

当我在没有平衡的情况下插入时，一切都很好。

public class Node {

public Node left, right, parent;
public int value;

public Node (Node parent, int i) {
    this.parent = parent;
    this.value = i;
}

public int height() {
    int l = 0;
    int r = 0;

    if (this.left  != null) {
        l = this.left.height() +1;
    }

    if (this.right  != null) {
        r = this.right.height() +1;
    }

    return Math.max(l,r);
}   
}
public class Tree {
Node root;

public Tree() {
    root = null;
}

public void insert (int value) {

    if (root == null) {
        root = new Node(null, value);
    }
    else {
        insert(root, value);
    }
}

private void insert (Node parent, int value) {

    if (parent.value >= value) {

        if (parent.left == null) {
            parent.left = new Node (parent, value);
        }
        else {
            insert(parent.left, value);

       /////////////////////////    
            if ( parent.left.height() - parent.right.height() == 2) {

                if (value - parent.left.value < 0) {
                    parent = rotateWithLeftChild(parent);
                }
                else {
                    parent = doubleRotateWithRightChild(parent);
                }
            }           
      /////////////////////////
        }
    }

    else {

        if (parent.right == null) {
            parent.right = new Node (parent, value);
        }
        else {
            insert(parent.right, value);
      /////////////////////////
            if ( parent.left.height() - parent.right.height() == -2) {

                if (value - parent.right.value > 0) {
                    parent = rotateWithRightChild(parent);
                }
                else {
                    parent = doubleRotateWithLeftChild(parent);
                }
            }
     /////////////////////////
    }
     }
     }
    public int quantity() {

if (root == null) {
    return 0;
}
else {
    return 1 + quantity(root.left) + quantity(root.right);          
}
 }
public int quantity (Node parent) {

if (parent == null) {
    return 0;
}
else {
    return 1 + quantity(parent.left) + quantity(parent.right);
}
}
public int height () {

int l = 0;
int r = 0;

if ( root.left != null) {
    l = height(root.left) + 1;
}

if (root.right != null) {
    r = height(root.right) +1;
}

return (Math.max(l,r));
}
private int height (Node parent) {

int l = 0;
int r = 0;

if ( parent.left != null) {
    l = height(parent.left) + 1;
}

if (parent.right != null)   {
    r = height(parent.right) +1;
}

return (Math.max(l,r));
}
public String toString () {

    if (root == null) {
        return "empty tree";
    }
    else {
        return toString(root.left) + " ; " + root.value + " ; " +  toString(root.right);
    }
}


private String toString (Node parent) {

    if (parent == null) {
        return "";
    }
    else {
        return toString(parent.left) + " ; " + parent.value
        + " ; " + toString(parent.right);
    }
}
private String toString (Node parent) {

if (parent == null) {
    return "";
}
else {
    return toString(parent.left) + " ; " + parent.value
    + " ; " +     toString(parent.right);
  }
 }
private Node rotateWithLeftChild (Node k2) {
Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;

return k1;
}
private Node rotateWithRightChild (Node k1) {
Node k2 = k1.right;
k1.right = k2.left;
k2.left = k1;

return k2;
}
private Node doubleRotateWithRightChild (Node k3) {
k3.left = rotateWithRightChild(k3.left);

return rotateWithLeftChild(k3);
}
private Node doubleRotateWithLeftChild (Node k1) {
k1.right = rotateWithLeftChild(k1.right);
return rotateWithRightChild(k1);
}

}
public class TestTheTree {
public static void main(String[] args) {


    Treee temp = new Treee();

    temp.insert(10);
    temp.insert(20);
    temp.insert(30);


    System.out.println(temp.toString());


  }
  }

Answer 1

您正在访问空节点。插入第三个节点(值为 30)时没有任何问题，但是此时树中仅存在右子节点(您添加了一个值为 10 的节点，它成为根，然后添加了一个具有值为 20，成为根的右子节点，然后添加一个值为 30 的节点，该节点成为值为 20 的节点的右子节点)。

因此，由于只有右 child ，当您尝试访问parent.left时，它将为空。所以，当你尝试平衡树时，你应该添加一些逻辑来确保parent.left和parent.right不为空。我向 Tree.java 文件添加了一些代码来帮助您入门。但是，看起来您可能还会遇到一些其他问题需要处理，因为在我粘贴在下面的代码的第 67 行中，您尝试访问“parent.right.value”，而不使用任何代码来确保“parent.right”不为空。我还留下了我用来调试代码的打印语句，以帮助您自己调试。

public class Tree {
    Node root;

    public Tree() {
        root = null;
    }

    public void insert (int value) {

        if (root == null) {
            root = new Node(null, value);
        }
        else {
            insert(root, value);
        }
    }

    private void insert (Node parent, int value) {

        if (parent.value >= value) {

            if (parent.left == null) {
                parent.left = new Node (parent, value);
            }
            else {
                insert(parent.left, value);

           /////////////////////////    
                if ( parent.left.height() - parent.right.height() == 2) {

                    if (value - parent.left.value < 0) {
                        parent = rotateWithLeftChild(parent);
                    }
                    else {
                        parent = doubleRotateWithRightChild(parent);
                    }
                }           
          /////////////////////////
            }
        }

        else {

            if (parent.right == null) {
                parent.right = new Node (parent, value);
                System.out.println("Node inserted as a right child.");
            }
            else {
                System.out.println("We are in the insert method, before the recursive call");
                insert(parent.right, value);
                System.out.println("We are in the insert method, after the recursive call");
          /////////////////////////
                System.out.println("parent" + parent);
                System.out.println("parent.value " + parent.value);
                System.out.println("parent.left " + parent.left);
                System.out.println("parent.right " + parent.right);
                int leftHeight = 0;
                int rightHeight = 0;
                if( parent.left != null )
                    leftHeight = parent.left.height();

                if( parent.right != null )
                    rightHeight = parent.right.height();

                if ( leftHeight - rightHeight == -2) {

                    if (value - parent.right.value > 0) {
                        parent = rotateWithRightChild(parent);
                    }
                    else {
                        parent = doubleRotateWithLeftChild(parent);
                    }
                }
         /////////////////////////
        }
         }
         }
        public int quantity() {

    if (root == null) {
        return 0;
    }
    else {
        return 1 + quantity(root.left) + quantity(root.right);          
    }
     }
    public int quantity (Node parent) {

    if (parent == null) {
        return 0;
    }
    else {
        return 1 + quantity(parent.left) + quantity(parent.right);
    }
    }
    public int height () {

    int l = 0;
    int r = 0;

    if ( root.left != null) {
        l = height(root.left) + 1;
    }

    if (root.right != null) {
        r = height(root.right) +1;
    }

    return (Math.max(l,r));
    }
    private int height (Node parent) {

    int l = 0;
    int r = 0;

    if ( parent.left != null) {
        l = height(parent.left) + 1;
    }

    if (parent.right != null)   {
        r = height(parent.right) +1;
    }

    return (Math.max(l,r));
    }
    public String toString () {

        if (root == null) {
            return "empty tree";
        }
        else {
            return toString(root.left) + " ; " + root.value + " ; " +  toString(root.right);
        }
    }

    private String toString (Node parent) {

    if (parent == null) {
        return "";
    }
    else {
        return toString(parent.left) + " ; " + parent.value
        + " ; " +     toString(parent.right);
      }
     }
    private Node rotateWithLeftChild (Node k2) {
    Node k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;

    return k1;
    }
    private Node rotateWithRightChild (Node k1) {
    Node k2 = k1.right;
    k1.right = k2.left;
    k2.left = k1;

    return k2;
    }
    private Node doubleRotateWithRightChild (Node k3) {
    k3.left = rotateWithRightChild(k3.left);

    return rotateWithLeftChild(k3);
    }
    private Node doubleRotateWithLeftChild (Node k1) {
    k1.right = rotateWithLeftChild(k1.right);
    return rotateWithRightChild(k1);
    }

}