[JAVA자료구조] 이진트리탐색 클래스 최소값 찾기, 최소값 삭제, 삭제연산 구현

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    // 삽입 메서드
    public void insert(int key) {
        root = insertRec(root, key);
    }

    private TreeNode insertRec(TreeNode node, int key) {
        if (node == null) {
            node = new TreeNode(key);
            return node;
        }

        if (key < node.value) {
            node.left = insertRec(node.left, key);
        } else {
            node.right = insertRec(node.right, key);
        }

        return node;
    }

    // 최소값 찾기
    public int findMin() {
        if (root == null) {
            throw new RuntimeException("Tree is empty.");
        }
        return findMinRec(root);
    }

    private int findMinRec(TreeNode node) {
        TreeNode current = node;
        while (current.left != null) {
            current = current.left;
        }
        return current.value;
    }

    // 최소값 삭제
    public void deleteMin() {
        if (root == null) {
            System.out.println("Tree is empty.");
            return;
        }
        root = deleteMinRec(root);
    }

    private TreeNode deleteMinRec(TreeNode node) {
        if (node.left == null) {
            return node.right;
        }
        node.left = deleteMinRec(node.left);
        return node;
    }

    // 삭제 연산
    public void delete(int key) {
        root = deleteRec(root, key);
    }

    private TreeNode deleteRec(TreeNode node, int key) {
        if (node == null) {
            return null;
        }

        if (key < node.value) {
            node.left = deleteRec(node.left, key);
        } else if (key > node.value) {
            node.right = deleteRec(node.right, key);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }

            TreeNode minLargerNode = findMinNode(node.right);
            node.value = minLargerNode.value;
            node.right = deleteRec(node.right, minLargerNode.value);
        }

        return node;
    }

    private TreeNode findMinNode(TreeNode node) {
        TreeNode current = node;
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }

    // 중위 순회
    public void inorderTraversal() {
        inorderRec(root);
        System.out.println();
    }

    private void inorderRec(TreeNode node) {
        if (node != null) {
            inorderRec(node.left);
            System.out.print(node.value + " ");
            inorderRec(node.right);
        }
    }
}