Получение StackOverFlowError всякий раз, когда я запускаю свой код AVLTree.java - PullRequest
Новая
       20

Получение StackOverFlowError всякий раз, когда я запускаю свой код AVLTree.java

0 голосов
/ 12 мая 2019

В данный момент я пытаюсь создать AVLTree для хранения данных, а затем распечатать данные через обратный порядок.Однако в настоящее время я застрял, пытаясь исправить ошибку StackOverflowError, которая возникает, когда я вызываю мой метод height ().

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

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);
    }

1 Ответ

0 голосов
/ 12 мая 2019

Ваша проблема не в методе 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);
    }
}
...