java - 无法从JAVA中的AVLTree获取高度

Question

我正在制作一个 AVL 树作为作业。
我在获取树的高度时遇到问题。
我的代码有问题，除了高度方法之外，所有方法都正常工作。
当我调用 getHeight() 时，它向我显示:零(0)它必须是 6 或 7。
我找不到我哪里做错了。

class AVLNode<K extends Comparable<K>, V extends K> {
    AVLNode<K, V> leftChild, rightChild;
    K key;
    V value;
    int avlNodeHeight;

    /* Constructor */
    public AVLNode() {
        leftChild = null;
        rightChild = null;
        key = null;
        avlNodeHeight = 0;
    }

    /* Constructor */
    public AVLNode(K n) {
        leftChild = null;
        rightChild = null;
        key = n;
        avlNodeHeight = 0;
    }

    /* Constructor */

    public AVLNode(K key, V value) {
        leftChild = null;
        rightChild = null;
        this.key = key;
        this.value = value;
        avlNodeHeight = 0;
    }

    public void setLeftChild(AVLNode<K, V> leftChild) {
        this.leftChild = leftChild;
    }

    public AVLNode<K, V> getLeftChild() {
        return leftChild;
    }

    public void setRightChild(AVLNode<K, V> rightChild) {
        this.rightChild = rightChild;
    }

    public AVLNode<K, V> getRightChild() {
        return rightChild;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public K getKey() {
        return key;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public V getValue() {
        return value;
    }

    public void setHeight(int height) {
        avlNodeHeight = height;
    }

    public int getHeight() {
        return avlNodeHeight;
    }

}

/* Class AVLTree */
class AVLTree<K extends Comparable<K>, V extends K> {
    AVLNode<K, V> root;

    /* Constructor */
    public AVLTree() {
        root = null;
    }

    /* Function to check if tree is empty */
    public boolean isEmpty() {
        return root == null;
    }

    /* Make the tree logically empty */
    public void makeEmpty() {
        root = null;
    }

    /* Function to get height of node */
    protected int height(AVLNode<K, V> root) {
        return root == null ? -1 : root.avlNodeHeight;
    }

    /* Function to max of left/right node */
    protected int max(int value1, int value2) {
        return Math.max(value1, value2);
    }

    protected K getSmallestValue(AVLNode<K, V> n) {
        if (n.getLeftChild() == null)
            return n.getKey();
        return getSmallestValue(n.getLeftChild());
    }

    /* Function to insert data */
    public void insert(K key, V value) {
        root = insert(key, value, root);
    }

    /* Function to insert data recursively */
    protected AVLNode<K, V> insert(K key, V value, AVLNode<K, V> root) {
        if (root == null)
            root = new AVLNode<K, V>(key, value);
        else if (key.compareTo(root.getKey()) < 0) {
            root.leftChild = insert(key, value, root.leftChild);

            if (height(root.leftChild) - height(root.rightChild) == 2)
                if (key.compareTo(root.getLeftChild().getKey()) < 0)
                    root = rotateLeftChild(root);
                else
                    root = doubleRotateLeftChild(root);
        } else if (key.compareTo(root.getKey()) > 0) {

            root.rightChild = insert(key, value, root.rightChild);
            if (height(root.rightChild) - height(root.leftChild) == 2)
                if (key.compareTo(root.rightChild.getKey()) > 0)
                    root = rotateRightChild(root);
                else
                    root = doubleRotateRightChild(root);
        } else if (root.getKey().equals(key)) {
            root.setValue(value);
            return root;
        } else
            root.avlNodeHeight = max(height(root.leftChild),
                    height(root.rightChild)) + 1;
        return root;
    }

    public void delete(K key) {
        root = delete(root, key);
    }

    protected AVLNode<K, V> delete(AVLNode<K, V> n, K key) {
        if (n == null)
            return null;
        if (key.compareTo(n.getKey()) < 0) {
            n.setLeftChild(delete(n.getLeftChild(), key));
            return balance(n);
        }
        else if (key.compareTo(n.getKey()) > 0) {
            n.setRightChild(delete(n.getRightChild(), key));
            return balance(n); // Deleting may have unbalanced tree.
        }
        // Else, we found it! Remove n.
        else {
            // 0 children
            if (n.getLeftChild() == null && n.getRightChild() == null)
                return null;
            // 1 child - guaranteed to be balanced.
            if (n.getLeftChild() == null)
                return n.getRightChild();
            if (n.getRightChild() == null)
                return n.getLeftChild();

            // 2 children - deleting may have unbalanced tree.

            K smallestKey = getSmallestValue(n.getRightChild());
            n.setKey(smallestKey);
            n.setRightChild(delete(n.getRightChild(), smallestKey));
            return balance(n);

        }
    }

    /* Functions to count number of nodes */
    public int countNodes() {
        return getNodesCount(root);
    }

    protected int getNodesCount(AVLNode<K, V> root) {

        if (root != null) {
            int counter = 1;
            counter += getNodesCount(root.leftChild);
            counter += getNodesCount(root.rightChild);
            return counter;
        } else
            return 0;

    }

    /* Functions to search for an element */
    public boolean search(K key) {
        return search(root, key);
    }

    protected boolean search(AVLNode<K, V> root, K key) {
        boolean check = false;

        while ((root != null) && !check) {
            K rootValue = root.key;

            if (key.compareTo(rootValue) > 0)
                root = root.rightChild;
            else if (key.compareTo(rootValue) < 0)
                root = root.leftChild;
            else {
                check = true;
                break;
            }
            check = search(root, key);
        }
        return check;
    }

    protected AVLNode<K, V> balance(AVLNode<K, V> root) {
        root.setHeight(1 + Math.max(height(root.getLeftChild()),
                height(root.getRightChild())));
        return root;
    }

    /* Rotate binary tree node with left child */
    protected AVLNode<K, V> rotateLeftChild(AVLNode<K, V> node) {
        AVLNode<K, V> avlNode = node.leftChild;

        node.leftChild = avlNode.rightChild;

        avlNode.rightChild = node;

        node.avlNodeHeight = max(height(node.leftChild),
                height(node.rightChild)) + 1;

        avlNode.avlNodeHeight = max(height(avlNode.leftChild),
                node.avlNodeHeight) + 1;

        return avlNode;
    }

    /* Rotate binary tree node with right child */
    protected AVLNode<K, V> rotateRightChild(AVLNode<K, V> node) {
        AVLNode<K, V> avlNode = node.rightChild;

        node.rightChild = avlNode.leftChild;

        avlNode.leftChild = node;

        node.avlNodeHeight = max(height(node.leftChild),
                height(node.rightChild)) + 1;

        avlNode.avlNodeHeight = max(height(avlNode.rightChild),
                node.avlNodeHeight) + 1;
        return avlNode;
    }

    protected AVLNode<K, V> doubleRotateLeftChild(AVLNode<K, V> node) {
        node.leftChild = rotateRightChild(node.leftChild);
        return rotateLeftChild(node);
    }

    protected AVLNode<K, V> doubleRotateRightChild(AVLNode<K, V> node) {
        node.rightChild = rotateLeftChild(node.rightChild);
        return rotateRightChild(node);
    }

}

public class AVLTreeTest {
    public static void main(String[] args) {
        AVLTree<Integer, Integer> avlt = new AVLTree<>();

        for (int i = 0; i < 1200; i++)
            avlt.insert(i, i + 5);

        System.out.println("Height of AVL TREE: " + avlt.root.getHeight());
    }
}

Answer 1

在 insert() 中，第一个和第二个 else if 永远不会更新高度。

我想你想搬家

    root.avlNodeHeight = max(height(root.leftChild),
            height(root.rightChild)) + 1;

除其他之外。

可能还有其他错误...