AVL树旋转异常问题咨询及Java泛型AVL树实现需求

Hey there! Let's break down how to fix those rotation bugs and build your generic AVL tree class that meets all your assignment requirements. Rotation issues usually boil down to missing height updates, incorrect node reference assignments, or miscalculating balance factors—we'll tackle those first, then walk through a complete implementation.

First: Common Rotation Pitfalls to Fix #

Before diving into code, let's cover the most frequent mistakes that cause rotation anomalies:

• Forgetting to update heights: After any rotation (or insertion/deletion), you must recalculate the height of the affected nodes. Skipping this leads to wrong balance factor checks later.
• Misplacing child nodes: For example, during a left rotation, you need to reattach the right child's left subtree to the original root's right—this step is often missed.
• Incorrect balance factor calculation: Balance factor is getHeight(left) - getHeight(right). Make sure you handle null nodes correctly (assign them a height of 0 here for consistency).
• Not returning the new root: Rotations change the root of the subtree—you need to return this new root to update the parent node's reference.

Complete Generic AVL Tree Implementation #

Here's a full Java class that implements all your required methods, with robust rotation logic:

import java.util.ArrayList;

public class AVLTree<K extends Comparable<K>, V> {
    // Internal Node class storing Key and Value
    private class Node<K, V> {
        K key;
        V value;
        Node<K, V> left, right;
        int height;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.height = 1; // New node starts as a leaf
        }
    }

    private Node<K, V> root;

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

    // Helper to get height of a node (handle null)
    private int getHeight(Node<K, V> node) {
        return (node == null) ? 0 : node.height;
    }

    // Helper to calculate balance factor of a node
    private int getBalanceFactor(Node<K, V> node) {
        return (node == null) ? 0 : getHeight(node.left) - getHeight(node.right);
    }

    // Right rotation
    private Node<K, V> rightRotate(Node<K, V> y) {
        Node<K, V> x = y.left;
        Node<K, V> T2 = x.right;

        // Perform rotation
        x.right = y;
        y.left = T2;

        // Update heights
        y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));
        x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));

        // Return new root of the subtree
        return x;
    }

    // Left rotation
    private Node<K, V> leftRotate(Node<K, V> x) {
        Node<K, V> y = x.right;
        Node<K, V> T2 = y.left;

        // Perform rotation
        y.left = x;
        x.right = T2;

        // Update heights
        x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
        y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));

        // Return new root of the subtree
        return y;
    }

    // Insert method
    public void insert(K key, V value) {
        root = insertRecursive(root, key, value);
    }

    private Node<K, V> insertRecursive(Node<K, V> node, K key, V value) {
        // Step 1: Standard BST insertion
        if (node == null) {
            return new Node<>(key, value);
        }

        int compareResult = key.compareTo(node.key);
        if (compareResult < 0) {
            node.left = insertRecursive(node.left, key, value);
        } else if (compareResult > 0) {
            node.right = insertRecursive(node.right, key, value);
        } else {
            // Duplicate key: update existing value
            node.value = value;
            return node;
        }

        // Step 2: Update current node's height
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

        // Step 3: Check balance factor to fix imbalance
        int balance = getBalanceFactor(node);

        // Case 1: Left Left (LL)
        if (balance > 1 && key.compareTo(node.left.key) < 0) {
            return rightRotate(node);
        }

        // Case 2: Right Right (RR)
        if (balance < -1 && key.compareTo(node.right.key) > 0) {
            return leftRotate(node);
        }

        // Case 3: Left Right (LR)
        if (balance > 1 && key.compareTo(node.left.key) > 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Case 4: Right Left (RL)
        if (balance < -1 && key.compareTo(node.right.key) < 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        // Return unchanged node if balanced
        return node;
    }

    // Delete method
    public void delete(K key) {
        root = deleteRecursive(root, key);
    }

    private Node<K, V> deleteRecursive(Node<K, V> node, K key) {
        // Step 1: Standard BST deletion
        if (node == null) {
            return node;
        }

        int compareResult = key.compareTo(node.key);
        if (compareResult < 0) {
            node.left = deleteRecursive(node.left, key);
        } else if (compareResult > 0) {
            node.right = deleteRecursive(node.right, key);
        } else {
            // Node with 0 or 1 child
            if ((node.left == null) || (node.right == null)) {
                Node<K, V> temp = (node.left != null) ? node.left : node.right;

                // No child case
                if (temp == null) {
                    node = null;
                } else { // One child case: copy child's data
                    node = temp;
                }
            } else {
                // Node with 2 children: get inorder successor (smallest in right subtree)
                Node<K, V> temp = minValueNode(node.right);

                // Copy successor's data to current node
                node.key = temp.key;
                node.value = temp.value;

                // Delete the successor
                node.right = deleteRecursive(node.right, temp.key);
            }
        }

        // If tree is now empty
        if (node == null) {
            return node;
        }

        // Step 2: Update current node's height
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

        // Step 3: Fix imbalance
        int balance = getBalanceFactor(node);

        // Case 1: Left Left (LL)
        if (balance > 1 && getBalanceFactor(node.left) >= 0) {
            return rightRotate(node);
        }

        // Case 2: Left Right (LR)
        if (balance > 1 && getBalanceFactor(node.left) < 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Case 3: Right Right (RR)
        if (balance < -1 && getBalanceFactor(node.right) <= 0) {
            return leftRotate(node);
        }

        // Case 4: Right Left (RL)
        if (balance < -1 && getBalanceFactor(node.right) > 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    // Helper to find smallest node in a subtree
    private Node<K, V> minValueNode(Node<K, V> node) {
        Node<K, V> current = node;
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }

    // Find value by key
    public V find(K key) {
        return findRecursive(root, key);
    }

    private V findRecursive(Node<K, V> node, K key) {
        if (node == null) {
            return null; // Key not found
        }

        int compareResult = key.compareTo(node.key);
        if (compareResult < 0) {
            return findRecursive(node.left, key);
        } else if (compareResult > 0) {
            return findRecursive(node.right, key);
        } else {
            return node.value; // Key found
        }
    }

    // In-order traversal (returns ArrayList of values)
    public ArrayList<V> inOrder() {
        ArrayList<V> result = new ArrayList<>();
        inOrderRecursive(root, result);
        return result;
    }

    private void inOrderRecursive(Node<K, V> node, ArrayList<V> result) {
        if (node != null) {
            inOrderRecursive(node.left, result);
            result.add(node.value);
            inOrderRecursive(node.right, result);
        }
    }

    // Pre-order traversal (returns ArrayList of values)
    public ArrayList<V> preOrder() {
        ArrayList<V> result = new ArrayList<>();
        preOrderRecursive(root, result);
        return result;
    }

    private void preOrderRecursive(Node<K, V> node, ArrayList<V> result) {
        if (node != null) {
            result.add(node.value);
            preOrderRecursive(node.left, result);
            preOrderRecursive(node.right, result);
        }
    }

    // Post-order traversal (returns ArrayList of values)
    public ArrayList<V> postOrder() {
        ArrayList<V> result = new ArrayList<>();
        postOrderRecursive(root, result);
        return result;
    }

    private void postOrderRecursive(Node<K, V> node, ArrayList<V> result) {
        if (node != null) {
            postOrderRecursive(node.left, result);
            postOrderRecursive(node.right, result);
            result.add(node.value);
        }
    }
}

Key Rotation & Implementation Notes #

• Rotation Logic: Each rotation method returns the new root of the subtree—this is critical because the parent node's reference needs to point to this new root to maintain the tree structure.
• Balance Factor Checks: After insertion and deletion, we backtrack up the tree to check balance factors. For insertion, we use the inserted key to determine the rotation case; for deletion, we check the balance factor of the child nodes since the deletion could have affected either subtree.
• Generic Safety: The K type is bounded by Comparable<K> to ensure we can compare keys for BST operations.
• Duplicate Keys: The insert method updates the value if the key already exists—adjust this if your assignment requires rejecting duplicates instead.

Testing Your Rotations #

To debug rotation issues, add a method to print the tree's structure (e.g., level-order traversal) or log balance factors after each insertion/deletion. This will help you see exactly where the tree becomes unbalanced and why rotations aren't correcting it.

内容的提问来源于stack exchange，提问作者Jeremy Martinez