AVLTree.java

//CS 145 - Binary Search Tree
//Duncan Jackson 
//Extra credit: AVL Tree implementation
//3/20/26

public class AVLTree {
    Node root; 

    //Constructors  
    public AVLTree(){
        //default empty tree
    }

    //instance methods
    public void insert(int key){
        root = newNode(root, key);
    }
    public void delete(int key){
        root = deleteNode(root, key);
    }


    //helper methods 
    public static Node newNode(Node rootNode, int key){
        if (rootNode == null){
            return new Node(key);
        } 
        else if (rootNode.key > key){
            rootNode.left = newNode(rootNode.left,key);
        }
        else if (rootNode.key < key) {
            rootNode.right = newNode(rootNode.right, key);
        } else if (rootNode.key == key){
            return rootNode;
        }
        updateHeight(rootNode);

        return reBalance(rootNode);
    }

    public static Node deleteNode(Node rootNode, int key){
        //traverse tree to find node to delete
        if(rootNode == null){
            return rootNode;
        }
        if(rootNode.key > key){
            rootNode.left = deleteNode(rootNode.left, key);
        } else if (rootNode.key < key){
            rootNode.right = deleteNode(rootNode.right, key);
        } else { //we have found our target node to delete
            //node with only one child or no children
            if(rootNode.left == null || rootNode.right == null){
                Node temp = null;
                if(rootNode.left == null){
                    temp = rootNode.right; //return right or left child depending on which is not null, target is unlinked and will be garbage collected
                } else {
                    temp = rootNode.left;
                }
                //leaf node case simply delete the node
                if(temp == null){
                    return null;
                } else { //one child case
                    return temp; //non-null child will take place of deleted node
                }
            } else { //node with two children
                Node temp = inOrderSuccesor(rootNode.right); //get the inorder successor of the right subtree
                rootNode.key = temp.key; //copy the inorder successor's content to this node
                //TODO copy data method
                rootNode.right = deleteNode(rootNode.right, temp.key); //delete the inorder successor
            }
        }

        //update heights and rebalance tree
        updateHeight(rootNode);
        return reBalance(rootNode);
    }

    //finds leftmost node in subtree, used in deletion algorithm 
    public static Node inOrderSuccesor(Node node){
        Node current = node;
        while(current.left != null){
            current = current.left;
        }
        return current;
    }

    //gets balance factor of node
    public static int balanceFactor(Node node){
        return height(node.left) - height(node.right);
    }

    //if node balance factor is greater than abs(1) then we do the appropriate rotations to rebalance and maintain AVL property
    public static Node reBalance(Node node){
        int bf = balanceFactor(node); 
        if(bf > 1){
            if(balanceFactor(node.left)< 0){
                node.left = leftRotate(node.left);
            }
            return rightRotate(node);
        }
        if(bf < -1){
            if(balanceFactor(node.right) > 0){
                node.right = rightRotate(node.right);
            }
            return leftRotate(node);
        }
        return node;
    }

    //returns height of -1 for null nodes 
    public static int height(Node node){
        if(node == null){
            return -1;
        }
        return node.height;
    }

    //calculates height of tree as 1(it's own height) + max of left and right subtree heights
    public static void updateHeight(Node node){
        node.height = 1 + Math.max(height(node.left),height(node.right));
    }

    //rotations
    public static Node leftRotate(Node x){
        Node y = x.right; //x's child right child is y 
        Node T2 = y.left; //y's left child
        
        //wotation >⩊<
        y.left = x; //y's left branch becomes x 
        x.right = T2; //x's right branch adopts y's left child
       

        updateHeight(x); //update heights
        updateHeight(y);

        return y; //return to parent 
    }

    public static Node rightRotate(Node y){
        Node x = y.left; //x is y's left child 
        Node T2 = x.right; //x's right child to be transfer to y

        //wotation ₍^. .^₎⟆
        x.right = y; //x's right branch adopts y
        y.left = T2; //y adopts x's right child

        updateHeight(y); //update heights
        updateHeight(x);

        return x; //return to parent
    }

    //printing methods
    public void print(Node node){
        printTree(node, "", false);
    }

    public static void printTree(Node node, String prefix, boolean isRight) {
        if (node == null) return;
        
        printTree(node.right, prefix + (isRight ? "    " : "│   "), true);
        System.out.println(prefix + (isRight ? "┌── " : "└── ") + node.key + " (h=" + node.height + ")");
        printTree(node.left, prefix + (isRight ? "│   " : "    "), false);
    }

    //inorder traversal
    public static void inOrder(Node node){
        if(node == null){
            return; //if we hit the bottom of the tree we return
        }

        inOrder(node.left); //traverses the left subtree
        System.out.print(node.key + " "); //after travering the left trees below us we print ourself
        inOrder(node.right); //then we go and investigate the right sub tree and do the same     
        }
    
    //preorder traversal
    public static void preOrder(Node node){
        if (node == null){
            return;
        }
        System.out.print(node.key +" "); //first we print ourselves 
        preOrder(node.left); //then we go down the left sub tree
        preOrder(node.right); //then we go down the right sub tree
    }

    //post order traversal
    public static void postOrder(Node node){
        if(node == null){
            return;
        }
        postOrder(node.left); //first we investigate the left node
        postOrder(node.right); //then we go down the right node
        System.out.print(node.key + " "); //then we print ourselves
    }
}