java - 每当我运行 AVLTree.java 代码时都会出现 StackOverFlowError

Question

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

我很确定 StackOverflowError 是由 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);
}

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

但是，然后您继续添加相同的节点作为根节点的子节点 - 这意味着该节点将添加为其自身的左子节点。正是这一点导致了无限递归。

相反，您的 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);
    }
}