PatientAVL.java

/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
package hospitalmanagementsystem;

/**
 *
 * @author egehanhatipoglu
 */

public class PatientAVL {

   
    // INNER CLASS: AVLNode
   
    // Each node stores a patient and its 'height'.
    // Height is critical for calculating the Balance Factor.
    private class AVLNode {
        Patient patient;
        AVLNode left;
        AVLNode right;
        int height;

        AVLNode(Patient patient) {
            this.patient = patient;
            this.left = null;
            this.right = null;
            this.height = 1;
        }
    }

    private AVLNode root;

    public PatientAVL() {
        this.root = null;
    }

    // ============================================
    // HEIGHT & BALANCE
    // ============================================
    // Returns height of a node (0 if null). 
    // This is a helper for calculating balance.
    private int height(AVLNode node) {
        return node == null ? 0 : node.height;
    }

    // Calculates Balance Factor = Height(Left) - Height(Right).
    // A value > 1 or < -1 indicates the tree is unbalanced and needs rotation.
    private int getBalance(AVLNode node) {
        return node == null ? 0 : height(node.left) - height(node.right);
    }

    // ============================================
    // ROTATIONS
    // ============================================
    // Right Rotation: Fixes Left-Left heavy imbalance.
    // Moves the left child up to become the parent.
    // Time Complexity: O(1)
    private AVLNode rightRotate(AVLNode node) {
        AVLNode leftChild = node.left;
        AVLNode temp = leftChild.right;

        leftChild.right = node;
        node.left = temp;

        node.height = Math.max(height(node.left), height(node.right)) + 1;
        leftChild.height = Math.max(height(leftChild.left), height(leftChild.right)) + 1;

        return leftChild;
    }

    // Left Rotation: Fixes Right-Right heavy imbalance.
    // Moves the right child up to become the parent.
    // Time Complexity: O(1)
    private AVLNode leftRotate(AVLNode node) {
        AVLNode rightChild = node.right;
        AVLNode temp = rightChild.left;

        rightChild.left = node;
        node.right = temp;

        node.height = Math.max(height(node.left), height(node.right)) + 1;
        rightChild.height = Math.max(height(rightChild.left), height(rightChild.right)) + 1;

        return rightChild;
    }

   
    // INSERT
  
    public void insert(Patient patient) {
        root = insertRec(root, patient);
    }

    // Recursive Insert:
    // 1. Standard BST Insert (sorted by Name).
    // 2. Update Height of the current node.
    // 3. Check Balance Factor.
    // 4. Perform Rotations (LL, RR, LR, RL) if unbalanced.
    // Time Complexity: O(log n) guaranteed.
    private AVLNode insertRec(AVLNode node, Patient patient) {

        if (node == null) {
            return new AVLNode(patient);
        }

        String newPatientName =  patient.getFirstName() + " " + patient.getLastName();
        String nodeName = node.patient.getFirstName() + " " + node.patient.getLastName();

        if (newPatientName.compareToIgnoreCase(nodeName) < 0) {
            node.left = insertRec(node.left, patient);
        }
        else if (newPatientName.compareToIgnoreCase(nodeName) > 0) {
            node.right = insertRec(node.right, patient);
        }
        else {
            return node; // Duplicate names are not allowed in this implementation
        }

        // Update height for balancing check
        node.height = 1 + Math.max(height(node.left), height(node.right));
        
        // Check for imbalance
        int balance = getBalance(node);

        // --- REBALANCING LOGIC ---
        
        // Helper variables for name comparison to prevent code duplication
        // Note: If balance > 1, node.left is guaranteed not to be null in AVL logic.

        // Check if the Left Subtree is unbalanced
        if (balance > 1) {
            String leftChildName = node.left.patient.getFirstName() + " " + node.left.patient.getLastName();

            // LEFT LEFT CASE: The new node is in the left subtree of the left child
            if (newPatientName.compareToIgnoreCase(leftChildName) < 0) {
                return rightRotate(node);
            }
            // LEFT RIGHT CASE: The new node is in the right subtree of the left child
            else if (newPatientName.compareToIgnoreCase(leftChildName) > 0) {
                node.left = leftRotate(node.left);  // First, rotate left child to the left
                return rightRotate(node);           // Then, rotate current node to the right
            }
        }

        // Check if the Right Subtree is unbalanced
        if (balance < -1) {
            String rightChildName = node.right.patient.getFirstName() + " " + node.right.patient.getLastName();

            // RIGHT RIGHT CASE: The new node is in the right subtree of the right child
            if (newPatientName.compareToIgnoreCase(rightChildName) > 0) {
                return leftRotate(node);
            }
            // RIGHT LEFT CASE: The new node is in the left subtree of the right child
            else if (newPatientName.compareToIgnoreCase(rightChildName) < 0) {
                node.right = rightRotate(node.right); // First, rotate right child to the right
                return leftRotate(node);              // Then, rotate current node to the left
            }
        }

        return node; // Return the (possibly new root) node
    }

    
   
    // DELETE
   
    public boolean delete(String firstName, String lastName) {
        int initialSize = countNodes(root);
        root = deleteRec(root, firstName, lastName);
        int finalSize = countNodes(root);
        return finalSize < initialSize; 
    }

    // Recursive Delete:
    // 1. Standard BST Delete.
    // 2. Update Height.
    // 3. Re-balance the tree moving upwards from the deletion point.
    private AVLNode deleteRec(AVLNode node, String firstName, String lastName) {
        if (node == null) {
            return null;
        }

        String targetName = firstName + " " + lastName;
        String nodeName = node.patient.getFirstName() + " " + node.patient.getLastName();

        // Navigate to the node
        if (targetName.compareToIgnoreCase(nodeName) < 0) {
            node.left = deleteRec(node.left, firstName, lastName);
        }
        else if (targetName.compareToIgnoreCase(nodeName) > 0) {
            node.right = deleteRec(node.right, firstName, lastName);
        }
        else {
            // Node found. Handle deletion cases:
            
            // Case 1 & 2: No child or One child
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }
            
            // Case 3: Two children
            // Find in-order successor (smallest in right subtree)
            AVLNode successor = findMin(node.right);
            
            // Copy successor data to current node
            node.patient = successor.patient;
            
            // Recursively delete the successor
            node.right = deleteRec(node.right, 
                                  successor.patient.getFirstName(), 
                                  successor.patient.getLastName());
        }
        
        if (node == null) {
            return null;
        }
        
        // Update height
        node.height = 1 + Math.max(height(node.left), height(node.right));
        
        // Check Balance and Rotate if necessary
        int balance = getBalance(node);
        
        // Left-Left Case
        if (balance > 1 && getBalance(node.left) >= 0) {
            return rightRotate(node);
        }
        
        // Left-Right Case
        if (balance > 1 && getBalance(node.left) < 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        
        // Right-Right Case
        if (balance < -1 && getBalance(node.right) <= 0) {
            return leftRotate(node);
        }
        
        // Right-Left Case
        if (balance < -1 && getBalance(node.right) > 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        
        return node;
    }

    // Helper to find the smallest node in a subtree (used for deletion).
     private AVLNode findMin(AVLNode node) {
          while (node.left != null) {
        node = node.left;
    }
    return node;
}
    
    
    
    
    // SEARCH
  
    // Searches for a patient by full name.
    // Time Complexity: O(log n)
    public Patient search(String firstName, String lastName) {
        return searchRec(root, firstName, lastName);
    }

    private Patient searchRec(AVLNode node, String firstName, String lastName) {

        if (node == null) {
            return null;
        }

        String searchPatientName = firstName + " " + lastName;
        String nodeName =
                node.patient.getFirstName() + " " + node.patient.getLastName();

        if (searchPatientName.equalsIgnoreCase(nodeName)) {
            return node.patient;
        }

        if (searchPatientName.compareToIgnoreCase(nodeName) < 0) {
            return searchRec(node.left, firstName, lastName);
        }
        else {
            return searchRec(node.right, firstName, lastName);
        }
    }

    // ============================================
    // DISPLAY
    // ============================================
    // Performs an In-Order Traversal to print patients alphabetically.
    public void displayInOrder() {
        if (root == null) {
            System.out.println("  AVL tree is empty.");
            return;
        }

        System.out.println("=== Patients (Alphabetical - AVL) ===");
        displayInOrderRec(root);
    }

    private void displayInOrderRec(AVLNode node) {
        if (node != null) {
            displayInOrderRec(node.left);

            Patient p = node.patient;
            System.out.println(
                "  " + p.getFirstName() + " " + p.getLastName() +
                " (ID: " + p.getId() +
                ", National ID: " + p.getNationalId() +
                ", Height: " + node.height + ")"
            );

            displayInOrderRec(node.right);
        }
    }
    
    
    // Utility: Checks if the entire tree satisfies AVL property.
    public boolean isBalanced() {
        return isBalancedRec(root);
    }

    private boolean isBalancedRec(AVLNode node) {
        if (node == null) return true;
        
        int balance = getBalance(node);
        if (Math.abs(balance) > 1) return false;
        
        return isBalancedRec(node.left) && isBalancedRec(node.right);
    }

    // Displays technical stats (Total nodes, Height) for debugging.
    public void displayStats() {
        System.out.println("\n=== AVL Tree Statistics ===");
        System.out.println("  Total patients: " + countNodes(root));
        System.out.println("  Tree height: " + height(root));
        System.out.println("  Balanced? " + (isBalanced() ? "✓ Yes" : "✗ No"));
    }

    private int countNodes(AVLNode node) {
        if (node == null) return 0;
        return 1 + countNodes(node.left) + countNodes(node.right);
    }
}