[자료구조 트리] 이진 탐색 트리(Binary Search Tree)

  이진 탐색 트리(Binary Search Tree; BST)란 이진 탐색의 개념을 트리 형태의 구조에 접목한 자료구조입니다. 이진 탐색을 수행하기 위해 단순 연결 리스트를 변형시킨 것입니다. 이진 탐색은 정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어 가며 특정 항목을 찾는 탐색 방법입니다. 각 노드 n에 저장된 키가 n의 왼쪽 서브트리에 있는 노드에 저장된 키보다 크고 n의 오른쪽 서브트리에 있는 노드의 키보다 작은 것이 이진 탐색 트리의 조건입니다. 각각의 서브 트리도 이진 탐색 트리를 유지하면서 중복된 키를 허용하지 않습니다. 특징 중 하나는 트리를 중위 순회(Inorder Traversal)하면 오름차순으로 정렬된 출력을 얻을 수 있다는 점입니다. 또 균형이 유지된 이진 탐색 트리는 이진 트리에 비해 탐색이 빠르다는(O(logN)) 장점도 있습니다.

  균형 이진 탐색 트리, B-트리, 다방향 탐색 트리는 이진 탐색 트리에 기반한 자료구조들입니다. 데이터베이스 등 대용량 데이터 저장의 기본 개념으로도 활용됩니다.

  이진 탐색 트리에서의 탐색은 항상 루트에서 시작합니다. 찾고자 하는 데이터를 루트 노드부터 비교를 시작하여, 대소 비교로 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동합니다. 찾는 데이터가 없다면 null을 반환합니다. 어떤 데이터를 찾더라도 최대 트리의 높이만큼의 탐색이 이루어집니다.

 

  노드의 삽입과 삭제 구현 코드

class Node {
    int key;
    Node left;
    Node right;
    Node(int key, Node left, Node right) {
        this.key = key;
        this.left = left;
        this.right = right;
    }
}
class BinarySearchTree {
    Node head;

    BinarySearchTree(int key) {
        this.head = new Node(key, null, null);
    }
    public void addNode(int key) {
        if (this.head == null) {
            this.head = new Node(key, null, null);
        } else {
            Node cur = this.head;
            while (true) {
                Node pre = cur;
                if(key < cur.key) {
                    cur = cur.left;
                    if (cur == null) {
                        pre.left = new Node(key, null, null);
                        break;
                    }
                } else {
                    cur = cur.right;
                    if (cur == null) {
                        pre.right = new Node(key, null, null);
                        break;
                    }
                }
            }
        }
    }
    public void removeNode(int key) {
        Node parent = null;
        Node successor = null;
        Node predecessor = null;
        Node child = null;

        Node cur = this.head;
        while (cur != null) {
            if (key == cur.key) {
                break;
            }
            parent = cur;
            if (key < cur.key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        if (cur.left == null && cur.right == null) {
            if (parent == null) {
                this.head = null;
            } else {
                if (parent.left == cur) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
            }
        } else if (cur.left != null && cur.right == null || 
        cur.left == null && cur.right != null) {
            if (cur.left != null) {
                child = cur.left;
            } else {
                child = cur.right;
            }
            if (parent == null) {
                this.head = child;
            } else {
                if (parent.left == cur) {
                    parent.left = child;
                } else {
                    parent.right = child;
                }
            }
        }
        else {
            predecessor = cur;
            successor = cur.left;
            while (successor.right != null) {
                predecessor = successor;
                successor = successor.right;
            }
            predecessor.right = successor.left;
            successor.left =  cur.left;
            successor.right = cur.right;
            if (parent == null) {
                this.head = successor;
            } else {
                if (parent.left == cur) {
                    parent.left = successor;
                } else {
                    parent.right = successor;
                }
            }

        }
    }
}

  이진 탐색 트리에서의 삽입 역시 루트에서 시작합니다. 중복 키 발견 시, 중복된 키를 허용하지 않으므로 노드를 추가하지 않고 종료합니다. 삽입할 키가 현재 노드의 키보다 작으면 왼쪽, 크면 오른쪽으로 이동합니다. Leaf 노드에 도달한 뒤 키를 비교하여 작으면 왼쪽, 크면 오른쪽에 삽입합니다.

  이진 탐색 트리에서의 삭제에는 여러 경우가 있습니다. 삭제 대상 노드가 Leaf 노드인 경우 삭제 대상 노드를 삭제한 뒤 부모 노드의 해당 자식 링크를 null로 변경합니다. 삭제 대상 노드에 자식 노드가 하나 있는 경우에는 자식 노드를 삭제 대상 노드의 부모 노드에 연결한 뒤 삭제 대상 노드를 삭제합니다. 삭제 대상 노드에 자식 노드가 둘인 경우 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드를 선택하거나, 삭제 대상 노드의 오른쪽 서브 트리에서 가장 작은 노드를 선택합니다. 선택한 노드를 삭제 대상 노드 위치로 올립니다. 위로 올리는 과정에서 다른 자식 노드들의 링크 연결 작업을 진행한 뒤 삭제 대상 노드를 삭제합니다.

 

  ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.