每当我 运行 我的 AVLTree.java 代码时出现 StackOverFlowError

Question

目前我正在尝试创建一个 AVLTree 来存储数据，然后通过中序遍历打印数据。但是，我目前一直在尝试修复调用 height() 方法时似乎发生的 WhosebugError。

我很确定 WhosebugError 是由于对我的 height() 方法的错误递归调用导致的，但我不知道为什么会发生错误的递归调用。

public class AVLTree<K,V> implements AVLTreeI<K,V> {
    class Node<K,V> {
        K key;
        V value;
        Node<K,V> leftChild;
        Node<K,V> rightChild;
        Node<K,V> parent;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            leftChild = rightChild = parent = null;
        }
    }
    private Node<K,V> root;
    private int currentSize;

    public AVLTree() {
        root = null;
        currentSize = 0;
    }

    public void add(K key, V value) {
        Node<K,V> node = new Node<K,V>(key, value);

        if (root == null) {
            root = node;
            currentSize++;
        }

        add(root, node);
    }

    private void add(Node<K,V> parent, Node<K,V> newNode) {
        if (((Comparable<K>)newNode.key).compareTo(parent.key) > 0) {

            if (parent.rightChild == null) {
                parent.rightChild = newNode;
                newNode.parent = parent;
                currentSize++;
            }
            else
                add(parent.rightChild, newNode);
        }
        else {
            if (parent.leftChild == null) {
                parent.leftChild = newNode;
                newNode.parent = parent;
                currentSize++;
            }
            else
                add(parent.leftChild, newNode);
        }
        checkBalance(newNode);
    } 

    public int height() {
        if (root == null)
            return 0;
        return height(root) - 1;
    }

    private int height(Node<K,V> node) {
        if (node == null)
            return 0;
        int leftHeight = height(node.leftChild) + 1;
        int rightHeight = height(node.rightChild) + 1;

        if (leftHeight > rightHeight)
            return leftHeight;
        return rightHeight;
    }

    public void checkBalance(Node<K,V> node) {
        if ((height(node.leftChild) - height(node.rightChild) > 1) || 
               (height(node.leftChild) - height(node.rightChild) < -1)) { 
                   rotate(node);
        }
        if (node.parent == null)
            return;
        checkBalance(node.parent);
    }

    public void rotate (Node<K,V> node) {
        if (height(node.leftChild) - height(node.rightChild) > 1) { 
            if (height(node.leftChild.leftChild) > 
                   height(node.leftChild.rightChild)) {
                       node = rightRotate(node);
            }
            else
                node = leftRightRotate(node);
        }
        else {
            if (height(node.rightChild.rightChild) > 
                   height(node.rightChild.leftChild)) {
                       node = leftRotate(node);
            }
        else 
            node = rightLeftRotate(node);
        }
        if (node.parent == null)
            root = node;    
    }

    public Node<K,V> leftRotate(Node<K,V> node) {
        Node<K,V> tmp = node.rightChild;
        node.rightChild = tmp.leftChild;
        tmp.leftChild = node;
        node.rightChild = tmp.parent;
        tmp.parent = node.parent;
        tmp.leftChild.parent = tmp;
        return tmp;
    }

    public Node<K,V> rightRotate(Node<K,V> node) {
        Node<K,V> tmp = node.leftChild;
        node.leftChild = tmp.rightChild;
        tmp.rightChild = node;
        node.leftChild = tmp.parent;
        tmp.parent = node.parent;
        tmp.rightChild.parent = tmp;
        return tmp;
    }

    public Node<K,V> rightLeftRotate(Node<K,V> node) {
        node.rightChild = rightRotate(node.rightChild);
        return leftRotate(node);
    }

    public Node<K,V> leftRightRotate(Node<K,V> node) {
        node.leftChild = leftRotate(node.leftChild);
        return rightRotate(node);
    }

Answer 1

你的问题不是height()方法（好像有道理），而是add()方法：

public void add(K key, V value) {
    Node<K,V> node = new Node<K,V>(key, value);

    if (root == null) {
        root = node;
        currentSize++;
    }

    add(root, node);
}

您创建一个新的 Node，如果树为空，您将节点设置为根节点。

但是你继续添加相同的节点也作为根节点的子节点 - 这意味着该节点被添加为它自己的左子节点。正是这个导致了无限递归。

相反，您的 add 方法应该添加一个节点作为根节点或作为根节点的子节点：

public void add(K key, V value) {
    Node<K,V> node = new Node<K,V>(key, value);

    if (root == null) {
        root = node;
        currentSize++;
    } else {
        add(root, node);
    }
}