이진 탐색 트리 (BST)에서 노드 삭제

Source: Dev.to

빠른 복습: BST가 특별한 이유는?

• 왼쪽 서브트리의 모든 값은 노드보다 작습니다.
• 오른쪽 서브트리의 모든 값은 노드보다 큽니다.

이 정렬 덕분에 검색, 삽입, 삭제가 효율적으로 이루어집니다.

문제 설명

BST의 루트와 값 key가 주어집니다.
해당 키를 가진 노드를 삭제하고(존재한다면) 업데이트된 트리를 반환하세요. 트리는 여전히 유효한 BST여야 합니다.

먼저 노드 찾기

• key < root.val → 왼쪽으로 이동.
• key > root.val → 오른쪽으로 이동.
• 같으면 → 삭제할 노드입니다.

세 가지 삭제 경우

경우 1: 자식이 없는 노드(리프 노드)

그냥 노드를 제거합니다:

return null;

경우 2: 자식이 하나만 있는 노드

노드를 유일한 자식으로 교체합니다.

• 오른쪽 자식만 있는 경우 → return root.right;
• 왼쪽 자식만 있는 경우 → return root.left;

경우 3: 자식이 두 개인 노드(가장 흥미로운 경우)

1. 중위 후계자(오른쪽 서브트리에서 가장 작은 값)를 찾습니다.
2. 그 값을 현재 노드에 복사합니다.
3. 오른쪽 서브트리에서 그 후계자 노드를 삭제합니다.

전체 코드

class Solution {

    // Finds the inorder successor (smallest node in right subtree)
    public static TreeNode inOrderSuccessor(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return root;

        // Search for the node
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else {
            // Found the node to delete

            // Case 1: No children
            if (root.left == null && root.right == null) {
                return null;
            }

            // Case 2: One child
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            // Case 3: Two children
            TreeNode successor = inOrderSuccessor(root.right);
            root.val = successor.val;
            root.right = deleteNode(root.right, successor.val);
        }

        return root;
    }
}

마무리 생각

• BST 속성을 이해합니다.
• 삭제할 노드를 식별합니다.
• 각 삭제 경우를 체계적으로 처리합니다.
• 트리 구조를 유지합니다.

이 패턴을 연습하면 대부분의 트리 문제를 더 쉽게 다룰 수 있습니다. 코딩을 즐기세요!