이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리란

이진 트리에서 데이터의 크기를 판단해 탐색하는 트리
부모 노드를 기준으로 작은 값은 왼쪽 서브 트리로, 큰 값은 오른쪽 서브 트리로 배치된다.
따라서 맨 왼쪽 리프 노드는 트리의 최솟값이고, 맨 오른쪽 리프 노드는 트리의 최댓값이다.

이를 이용해 값을 찾을 때 대소 비교를 통해 탐색 방향을 정한다.
매 탐색마다 경우의 수가 절반씩 줄어들기 때문에 삽입, 삭제, 탐색에서 logN의 시간 복잡도를 가진다.

이진 탐색 트리의 문제

오름차순 또는 내림차순 된 리스트를 순차적으로 저장하는 경우 트리의 방향이 한쪽으로 치우치는 편향 이진 트리가 된다.
이경우, logN의 시간 복잡도가 아닌 O(N)의 시간 복잡도가 발생한다.

노드 정의

    private static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

노드 삽입

보통 재귀를 통해 구현하지만, 큐를 이용해 구현했다.

    public static void insert(int data) {
        if (root == null) {
            root = new Node(data);
            return;
        }

        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node here = q.poll();
            // 자신보다 작거나 같으면 왼쪽
            if (here.data >= data) {
                if (here.left == null) {
                    here.left = new Node(data);
                    break;
                }
                q.add(here.left);
            }
            if (here.data < data) {
                if (here.right == null) {
                    here.right = new Node(data);
                    break;
                }
                q.add(here.right);
            }
        }
    }

구현된 트리는 다음 형태라 가정한다.

노드 삭제

삭제의 경우 특정 상황에선 고려해야 할 요소들이 있다.

자식 노드 0개 (리프 노드)

단순히 노드만 지우면 된다.
null을 반환해서 부모노드가 삭제된 노드에 접근하지 못하게 해야 한다.

다음 트리에서 노드 4를 삭제해도 큰 변경 사항은 없다.

        // 자식 노드가 없는 경우(리프 노드)
        if (node.left == null && node.right == null) {
            node = null;
            return null;
        }

자식 노드 1개

이진 탐색 트리의 특성으로 인해 부모 노드의 왼쪽 노드들은 부모보다 작고, 오른쪽 노드들은 부모보다 크다.
따라서, 자식이 있는 노드를 부모 노드의 left, 또는 right 값에 덮어쓴다.

다음 트리에서 노드 2를 지우는 경우 노드1은 노드 3의 왼쪽 자식 노드가 된다.

        // 자식 노드를 1개만 가지는 경우
        if (node.left != null) {
            node = node.left;
        } else if (node.right != null) {
            node = node.right;
        }
        return node;

자식 노드 2개

고려해야 할 부분들이 좀 있다.

중위 탐색을 기준으로 삭제할 노드의 바로 왼쪽 노드 or 오른쪽 노드를 올려야 한다.
각 노드에 대한 삭제 흐름은 다음과 같다.

 

삭제할 노드 7을 A라고 한다면

• 왼쪽 노드(PredecessorNode)를 올릴 때
  • A의 left 서브 트리를 기준으로 가장 right 리프 노드 B를 찾는다.
  • B의 값을 A의 값에 덮어씌우고, B의 부모 노드의 right에 null 할당.
    • 만약 A의 left 서브트리가 자식 노드를 가지지 않는 리프 노드라면 A의 left에 null 할당

// 자식 노드를 2개를 가지고, 왼쪽 노드(Predecessor)를 위로 올릴 때
else if (node.left != null && node.right != null) {
    Node predecessorNode = findPredecessor(node, node, node.left);
    node.data = predecessorNode.data;
    return node;
}

• 오른쪽 노드(SuccessorNode)를 올릴 때
  • A의 right 서브 트리를 기준으로 가장 left 리프 노드 C를 찾는다.
  • C의 값을 A의 값에 덮어씌우고, C의 부모 노드의 left에 null 할당.
    • 만약 A의 right 서브트리가 자식 노드를 가지지 않는 리프 노드라면 A의 right에 null 할당

// 자식 노드를 2개를 가지고, 오른쪽 노드(Successor)를 위로 올릴 때
else if (node.left != null && node.right != null) {
    Node successorNode = findSuccessor(node, node, node.right);
    node.data = successorNode.data;
    return node;
}

전체 코드는 여기에 있다.

import java.util.*;

public class BST {

    private static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    private static Node root = null;

    public static void main(String[] args) {
        TestDeleteNoChildNode();
        TestDeleteOneChildNode();
        TestDeleteTwoChildNode();
    }

    public static void insert(int data) {
        if (root == null) {
            root = new Node(data);
            return;
        }

        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node here = q.poll();
            // 자신보다 작거나 같으면 왼쪽
            if (here.data >= data) {
                if (here.left == null) {
                    here.left = new Node(data);
                    break;
                }
                q.add(here.left);
            }
            if (here.data < data) {
                if (here.right == null) {
                    here.right = new Node(data);
                    break;
                }
                q.add(here.right);
            }
        }
    }

    private static Node delete(Node node, int data) {
        if (node == null) {
            return null;
        }
        if (node.data > data) {
            node.left = delete(node.left, data);
            return node;
        }
        if (node.data < data) {
            node.right = delete(node.right, data);
            return node;
        }
        // 자식 노드가 없는 경우(리프 노드)
        if (node.left == null && node.right == null) {
            node = null;
            return null;
        }
        // 자식 노드를 2개를 가지고, 오른쪽 노드(Successor)를 위로 올릴 때
        else if (node.left != null && node.right != null) {
            Node successorNode = findSuccessor(node, node, node.right);
            node.data = successorNode.data;

            /* 왼쪽 노드(Predecessor)를 위로 올릴 때
            Node predecessorNode = findPredecessor(node, node, node.left);
            node.data = predecessorNode.data;
            */
            return node;
        }
        // 자식 노드를 1개만 가지는 경우
        else {
            if (node.left != null) {
                node = node.left;
            } else if (node.right != null) {
                node = node.right;
            }
            return node;
        }
    }
    // 레벨 순회
    public static void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.printf("%d ", node.data);
        preOrder(node.left);
        preOrder(node.right);
    }

    private static Node findPredecessor(Node root, Node prev, Node node) {
        if (node.right != null) {
            return findPredecessor(root, node, node.right);
        }
        if (root == prev) {
            root.left = null;
        } else if (root != prev) {
            prev.right = null;
        }
        return node;
    }

    private static Node findSuccessor(Node root, Node prev, Node node) {
        if (node.left != null) {
            return findSuccessor(root, node, node.left);
        }
        if (root == prev) {
            root.right = null;
        } else if (root != prev) {
            prev.left = null;
        }
        return node;
    }

    private static void TestDeleteNoChildNode() {
        root = null;
        insert(5);
        insert(3);
        insert(7);
        insert(2);
        insert(4);
        insert(6);
        insert(9);
        insert(1);
        insert(8);
        insert(10);
        System.out.printf("PreOrder: ");
        preOrder(root);
        System.out.printf("\ndata %d delete", 4);
        root = delete(root,4);
        System.out.printf("\nPreOrder: ");
        preOrder(root);
        System.out.printf("\n\n");
    }

    private static void TestDeleteOneChildNode() {
        root = null;
        insert(5);
        insert(3);
        insert(7);
        insert(2);
        insert(4);
        insert(6);
        insert(9);
        insert(1);
        insert(8);
        insert(10);
        System.out.printf("PreOrder: ");
        preOrder(root);
        System.out.printf("\ndata %d delete", 2);
        root = delete(root,2);
        System.out.printf("\nPreOrder: ");
        preOrder(root);
        System.out.printf("\n\n");
    }

    private static void TestDeleteTwoChildNode() {
        root = null;
        insert(5);
        insert(3);
        insert(7);
        insert(2);
        insert(4);
        insert(6);
        insert(9);
        insert(1);
        insert(8);
        insert(10);
        System.out.printf("PreOrder: ");
        preOrder(root);
        System.out.printf("\ndata %d delete", 7);
        root = delete(root,7);
        System.out.printf("\nPreOrder: ");
        preOrder(root);
        System.out.printf("\n\n");
    }
}

https://github.com/brorica/DataStructure/blob/master/src/BST.java

GitHub - brorica/DataStructure: 수상할 정도로 나무를 좋아하는 레포