[자료구조] 이진탐색트리 :: 늦깍이 IT

---

이 포스팅은 이전의 [이진탐색트리] 내용을 보완하여 다시 작성된 포스팅입니다.

---

[ 이진탐색트리란? ]

이진탐색트리란 이진 트리 기반의 탐색을 위한 자료구조로써 아래와 같은 특성을 만족한다.

• 모든 키는 유일하다.

• 왼쪽 서브트리의 키값은 루트노드의 키값보다 작다.

• 오른쪽 서브트리의 키값은 루트노드의 키값보다 크다.

• 왼쪽과 오른쪽 서브트리도 이진탐색 트리이다.

아래 그림은 이진탐색트리로써 각각의 모든 노드들에 대해서 위의 전제조건을 모두 만족시킨다.

[ 탐색 ]

이진탐색트리의 특징을 활용한 탐색 알고리즘을 알아보자. 이진탐색트리에서 임의의 데이터를 찾을 경우에는 다음과 같은 과정을 거친다.

• 루트노드의 키값과 찾고자하는 값을 비교한다. 찾고자하는 값이 루트노드의 키값이라면 종료한다.

• 찾고자하는 값이 루트노드보다 작을 경우, 루트노드의 왼쪽 서브트리를 기준으로 다시 탐색한다.

• 찾고자하는 값이 루트노드보다 클 경우, 루트노드의 오른쪽 서브트리를 기준으로 다시 탐색한다.

[ 최소 값과 최대 값 탐색 ]

이진탐색트리에서 최소 값은 항상 트리의 가장 왼쪽 서브트리에 존재한다. 그 이유는 부모노드보다 작은 값은 왼쪽에 저장되기 때문이다. 이와 마찬가지로 최대 값은 항상 트리의 가장 오른쪽 서브트리에 존재한다.

[ 의사 코드 ]

BST-SEARCH(x, k)    // x는 루트노드, k는 탐색 대상
    if x == null or key[x] == k
        return x
    
    if k < key[t]
        return BST-SEARCH(left[x], k)
    else
        return BST-SEARCH(right[x], k)
 
BST-MINIMUM(x)    // 최소값 찾기
    while left[x] is not null do
        x ← left[x]
    return x
 
BST-MAXIMUM(x) // 최대값 
    while right[x] is not null do
        x ← right[x]
    return x
 

[ 삽입 ]

이진탐색트리에 데이터를 저장하기 위해서는 다음과 같은 과정을 거친다.

• 삽입할 데이터와 루트노드의 키 값을 비교한다.
• 삽입할 데이터가 루트노드보다 작다면, 루트노드의 왼쪽 서브트리에 저장한다.
• 삽입할 데이터가 루트노드보다 크다면, 루트노드의 오른쪽 서브트리에 저장한다.

데이터를 삽입할 위치를 찾기 위해서는 두 개의 포인터가 필요하다. 

• 비교 대상이되는 노드를 가리키는 포인터 x와 그 노드의 부모노드를 가리키는 포인터 y가 있다.
• 부모노드를 가리키는 포인터를 x의 위치로 옮겨준다.
• 삽입할 데이터가 더 작다면 포인터 x를 왼쪽 서브트리로, 더 크다면 포인터 x를 오른쪽 서브트리로 이동시킨다.
• 이와 같은 과정을 반복하면 포인터 x는 결국 null을 가리키게 되는데, 이때 그 부모노드를 가리키는 포인터 y를 이용해서 데이터를 저장한다.

[ 의사 코드 ]

BST-INSERT(T, z) // T는 BST, z는 삽입할 노드
    y ← null
    x ← root[T]
 
    while x is not null do
        y ← x
        if key[x] > key[z]
            x ← left[x]
        else
            x ← right[x]
 
    if y is null
        root[T] ← z
    else if key[y] > key[z]
        left[y] ← z
    else
        right[y] ← z

[ 삭제 ]

삭제 과정은 삭제 대상이 되는 노드가 자식노드를 갖는 경우와 갖지 않는 경우로 나뉜다.

1. 자식 노드를 갖지 않는 경우

위의 그림에서 3을 삭제한다고 가정해보자. 3은 자식노드를 갖지 않으므로 단순히 부모노드와의 연결을 끊어버리면 된다.

2. 자식 노드를 하나 갖는 경우

위의 그림에서 2를 삭제한다고 가정해보자. 2는 하나의 자식 노드가 있으므로, 자신의 부모노드와 자식 노드를 연결해주면 된다. 이는 연결리스트에서 중간에 있는 노드를 삭제하는 연산과 같다.

3. 자식 노드를 두 개 갖는 경우

자식노드를 두 개 갖는 노드를 삭제하기 위해서는 Predecessor와 Successor라는 개념을 알아야 한다.

1) Predecessor

• 임의의 노드 A가 있다고 가정하자. 노드 A의 Predecessor는 노드 A보다 작은 값들 중에서 가장 큰 값이다.
• 이진탐색트리에 있는 모든 키 값들을 오름차순으로 정렬했을 때, 노드 A의 바로 앞에 있는 값을 Predecessor라고 한다.

2) Successor

• 임의의 노드 A가 있다고 가정하자. 노드 A의 Successor는 노드 A보다 큰 값들 중에서 가장 작은 값이다.
• 이진탐색트리에 있는 모든 키 값들을 오름차순으로 정렬했을 때, 노드 A의 바로 뒤에 있는 값을 Successor라고 한다.

위의 그림에서, 4의 Predecessor는 3이고, Successor는 5이다. Predecessor는 노드 4의 왼쪽 서브트리 중 가장 큰 값이고, Successor는 노드 4의 오른쪽 서브트리 중 가장 작은 값이다.

Predecessor와 Successor의 개념을 설명한 이유는 삭제할 노드를 Predecessor혹은 Successor로 대체해야하기 때문이다.

임의의 노드 A를 삭제한다고 가정했을 때, 노드 A의 자리에 노드 A의 Predecessor혹은 Successor로 대체한다면 BST 전제조건이 깨지지 않기 때문이다.

위의 그림에서, 노드 4를 삭제한다고 가정해보자. 노드 4의 Successor인 노드 5를 노드 4의 위치에 복사하고, 원래 노드 5를 삭제해주면 된다.

여기서 주의할점은, 삭제 대상이 되는 노드4와 그 자식들간의 연결을 끊지 않는다는 것이다. 단, 삭제 대상 노드의 Successor 노드의 연결을 끊어줘야 한다.

[ 의사 코드 ]

BST-DELETE(T, z) // T는 BST, z는 삭제할 노드
    if left[z] == null or right[z] == null
        then y ← z
        else y ← BST-SUCCESSOR(T, z)
 
    if left[y] != null
        then x ← left[y]
        else x ← right[y]
 
    if x != null
        then p[x] ← p[y]
 
    if p[y] == null
        then root[T] ← x
        else if y == left[p[y]]
            then left[p[y]] ← x
            else right[p[y]] ← x
 
    if y != z
        then key[z] ← key[y]
 
    return y
 
 
BST-SUCCESSOR(T, x)
    if right[x] != null
        return BST-MINIMUM(right[x])
 
    y ← p[x]
    while y != null and x == right[y] do
        x ← y
        y ← p[y]
    
    return y    

[ 시간 복잡도 ]

트리의 높이를 h라고 했을 때, 이진탐색트리의 시간 복잡도는 다음과 같다.

1. 검색

찾고자하는 데이터를 찾기 위해 트리의 높이만큼 반복하므로 O(h)이다.

2. 삽입

삽입할 위치를 찾기 위해 트리의 높이만큼 반복하므로 O(h)이다.

3. 삭제

• 삭제할 대상을 찾기 위해 걸리는 시간이 O(h)이다.
• 삭제 대상이 되는 노드의 자식노드가 0개이거나 1개일 경우, 삭제하는 데 걸리는 시간은 O(1)이고,
• 삭제 대상이 되는 노드의 자식이 둘인 경우, Successor를 찾아야하는데 걸리는 시간은 O(h), 삭제하는 데 걸리는 시간은 O(1)이다.

[ 이진탐색트리의 단점 ]

이진탐색트리의 시간복잡도는 트리의 높이에 의존한다. 이진탐색트리는 일반적으로 O(logN)의 시간복잡도를 가진다고 말하지만, 트리의 균형이 맞지 않을수록 O(N)에 가까운 시간복잡도를 보인다.

위의 왼쪽 그림에서는 1부터 5까지의 정수가 순서대로 저장되었을 때의 이진탐색트리를 보여준다. 이는 분명 이진탐색트리의 전제조건을 만족하지만 노드의 수에 가까운 높이를 형성했다.

반면, 오른쪽 그림에서는 1부터 5까지의 정수를 순서대로 저장하되 3만 제일 먼저 저장을 해도 결과는 왼쪽과는 확연하게 달라진다. 이처럼 저장순서를 조금만 바꿔도 어느정도 균형이 잡혀있는 트리를 형성한다.

즉, 이진탐색트리는 저장 순서에 따라 탐색의 성능에 큰 차이를 보이게 되고, 이것이 이진탐색트리의 단점이다.

[ JAVA 코드 ]

 
public class BSTree {
 
    Node root;
 
    static class Node {
        int value;
        Node left;
        Node right;
 
        public Node(int value) {
            this.value = value;
            this.left = this.right = null;
        }
    }
 
    public void add(int value) {
        root = addRecursive(root, value);
    }
 
    private Node addRecursive(Node current, int value) {
 
        if (current == null)
            return new Node(value);
 
        if (current.value > value)
            current.left = addRecursive(current.left, value);
        else if (current.value < value)
            current.right = addRecursive(current.right, value);
        else
            return current;
 
        return current;
    }
 
    public boolean containsNode(int value) {
        return containsNodeRecursive(root, value);
    }
 
    private boolean containsNodeRecursive(Node current, int value) {
 
        if (current == null)
            return false;
 
        if (current.value == value)
            return true;
        else if (current.value > value)
            return containsNodeRecursive(current.left, value);
        else
            return containsNodeRecursive(current.right, value);
    }
 
    public void delete(int value) {
        root = deleteRecursive(root, value);
    }
 
    private Node deleteRecursive(Node current, int value) {
 
        if (current == null)
            return null;
 
        if (current.value == value) {
 
            if (current.left == null && current.right == null)
                return null;
 
            if (current.right == null)
                return current.left;
 
            if (current.left == null)
                return current.right;
 
            int successor = findSuccessor(current.right);
            current.value = successor;
            current.right = deleteRecursive(current.right, successor);
            return current;
 
        } else if (current.value > value) {
            current.left = deleteRecursive(current.left, value);
            return current;
        } else {
            current.right = deleteRecursive(current.right, value);
            return current;
        }
    }
 
    private int findSuccessor(Node current) {
        if (current.left == null)
            return current.value;
        else
            return findSuccessor(current.left);
    }
 
    public void traverseInOrder(Node current) {
 
        if (current == null)
            return;
 
        traverseInOrder(current.left);
        System.out.print(current.value + " ");
        traverseInOrder(current.right);
    }
 
    public static void main(String[] args) {
        BSTree bst = new BSTree();
        bst.add(6);
        bst.add(4);
        bst.add(8);
        bst.add(3);
        bst.add(5);
        bst.add(7);
        bst.add(9);
 
        bst.traverseInOrder(bst.root);
        System.out.println();
        
        bst.delete(5);
        bst.traverseInOrder(bst.root);
        System.out.println();
        
        bst.delete(4);
        bst.traverseInOrder(bst.root);
        System.out.println();
        
        bst.delete(8);
        bst.traverseInOrder(bst.root);
        System.out.println();
 
    }
}