[알고리즘-이론] 이진 검색 트리(Binary Search Tree)

---

이진 검색 트리(Binary Search Tree)

이진 검색 트리에 대해서 공부하기 전에 트리에 대해서 먼저 알고 넘어가자

##트리(Binary Search Tree)란?

트리란 자료들이 List, Stack, Queue와 같은 1:1 관계의 선형 구조가 아닌 1:n 관계의 비선형 구조로 계층 관계로 만들어진 계층형 자료구조라고 한다.

위의 그림에서 숫자들은 아래의 숫자들을 연결하는 관계를 갖고 이를 부모-자식 관계라고 한다.

형제 관계란?

30은 아래로(계층적으로) 20과 40이 연결되어 있다면 부모는 30이 되고 자식은 각각 20과40이 되며 이 둘은 서로 형제관계 라고한다.

노드란?

이 때 30은 부모 노드가 되고 20과 40은 각각의 자식 노드라고 불린다. 이를 미루어 보았을 때 노드는 각각의 원소를 일컫는 말이다. 추가적으로 이는 선으로 연결되어있는데 이 선을 바로 간선이라고 한다.

서브 트리란?

자식들은 각각 독립하여 새로운 트리를 구성할 수 있으므로 각 노드는 자식의 노드만큼 서브 트리를 갖는다. 30의 서브트리는 자식노드의 수와 같으므로 2가 된다.

차수란?

차수란 한 노드가 가지는 서브트리의 수, 즉 자식 노드의 수이다.

단말 노드, 리프 노드, Reaf Node란?

차수가 0인 노드, 즉 자식 노드가 없는 노드를 단말 노드 또는 리프 노드라고 한다.

키(Key)란?

Index 에 해당하는 실존하는 값(Value)를 뜻하며 배열에서의 Arr[0] = 12, Arr[2] = 10 에서 12와 10은 키값이 된다.

##이진 검색 트리(Binary Search Tree)란?

좌우가 구분된 왼쪽, 오른쪽, 혹은 둘 만의 자식 노드를 갖는(차수가 2인) 트리를 뜻한다. 이진 트리가 되기 위한 조건이 있는데

• 조건 1 : 이진 검색 트리의 각 노드는 키값을 하나씩 갖는다. 각 노드의 키 값은 모두 달라야 한다.

• 조건 2 : 최상위 레벨에 루트 노드가 잇고, 각 노드는 최대 두 개의 자식 노드를 갖는다.

• 조건 3 : 임의의 노드의 키 값은 자신의 왼쪽에 있는 노드의 키 값보다 크고, 오른쪽에 있는 모든 노드의 키 값보다 작다.

이진 검색 트리에서의 검색

이진 검색 트리에서 키가 [x]인 노드를 검색하고자 한다. 트리에 키가 x인 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면(실패하는 검색) NIL을 리턴한다.

pseudo code

treeSearch(t, x){ // 검색 트리의 루트 노드 t의 키 값, 검색하고자 하는 값 x
    if(t=NIL or key[t] = x) then return t;            // 루트노드의 값과 x의 값이 같다면 루트노드를 리턴한다.
    if(x<key[t]) then return treeSearch(left[t], x);            // x가 키 값보다 작으면 left[t]를 재귀호출 한다.
    else return treeSearch(right[t], x);            // x가 키 값보다 크면 right[t]를 재귀적으로 호출한다.
}

아까 봤던 그림을 다시 예로써 사용해서 흐름적으로 보자. 키 값 x=35라고 했을 때.

1 : 알고리즘을 호출했을 때 루트 노드의 값(30)과 검색하고자 하는 값(35)이 같으면 t를 리턴한다. 하지만 다르므로 if조건문에 분기되지 않는다.

2 : 루트 노드의 값보다 키의 값이 작으면 재귀호출로 searchTree를 재귀한다. -> 루트 노드의 값(30)보다 x값이 크므로 searchTree(40, 35)을 재귀호출 한다.

3 : 루트 노드의 값(40)과 x 값(35)를 비교했을 때 루트 노드의 값이 더 크므로 right[t]에 대한 재귀호출을 실행한다.

4 : 루트 노드의 값(35)와 x 값이 같으므로 루트노드의 값을 return 한다.

이진 검색 트리에서의 삽입

이진 검색 트리에서 삽입을 하기 위해서는 삽입을 원하는 수 x가 없어야하고 검색 알고리즘을 거친 후에 삽입이 이루어진다.

 

우선 원소 x를 삽입할 자리에 x에 대한 검색을 실시한 수 리프 노드로 다다라서 더 이상 내려갈 곳이 없다면 x는 리프노드에 자식으로 추가시킨다.

pseudo code

treeInsert(t, x){
    if(t=NIL) then{ // x에 해당하는 노드가 없을 경우
        key[r] <- x; // x에 해당하는 값을 키에 넣고
        left[r] <- NIL; // 왼쪽 오른쪽 은 NIL인 채로 새로운 노드를 만든다
        right[r] <- NIL;
        return r; // 새 노드 r을 리턴한다.
    }
    if(x<key[t]){ // 키 값보다 x가 작으면
        then {left[t] <- treeInsert(left[t], x); return t;} // 왼쪽 노드에 재귀적 호출로 treeInsert를 사용한다.
    }
    else {right[t] <- treeInsert(right[t], x); return t;} // 키 값이 x보다 크면 오른쪽 노드에 재귀적 호출로 사용한다.
}

30, 20, 25, 40, 10, 35를 순서대로 삽입한다고 할 때.

(a) : 아무것도 없는 상태에서 30이 삽입되면 30하나만으로 이루어진 트리가 생성된다.

(b) : 20과 30을 비교했을 때 20이 더 작으므로 30 왼쪽에 추가시킨다.

(c) : 25가 입력되면 30보다 작으므로 왼쪽으로 가서 20과 비교한 후 20보다 크므로 20 오른쪽에 25를 추가시킨다.

(d) : 40이 입력되면 30보다 크므로 오른쪽으로 가서 30과 비교한 후 30보다 크므로 30 오른쪽에 40을 추가시킨다.

(e) : 10이 입력되면 30보다 작으므로 왼쪽으로 가서 20과 비교한 후 20보다 작으므로 20 왼쪽에 추가시킨다.

(f) : 35가 입력되면 30보다 크므로 오른쪽으로 가서 40과 비교한 수 40보다 작으므로 40 왼쪽에 추가시킨다.

순서: 1. 해당 값을 검색한다 -> 해당 값이 있을 수 있는 제일 마지막 노드로 간다. -> 제일 마지막 노드에 추가시킨다.

이진 검색 트리에서의 삭제

이진 검색 트리에서 삽입은 노드가 삽입될 자리만 정해지면 간단하지만 삭제의 경우는 삭제할 노드가 정해진 이후가 더 복잡하다.

 

이진 검색 트리에서 노드r을 삭제제하고자 할 때는 다음 세 가지에 따라 다른 처리가 필요하다.

 

다른 처리를 각각 Case로 나눠 놨다.

• Case1: r이 리프 노드인 경우

r은 리프노드이므로 자식이 없어 r이 삭제되어도 r의 아래쪽에는 영향을 미치지 않는다. 단지 r의 부모노드에서 r을 가리키고 있던 포인터를 NIL로 바꿔주면 된다.

18을 삭제하려고 한다

(a) 18을 키로 갖는 노드로 가서 자식의 존재 여부를 확인한다 -> 없음.

(b) 자식이 없다면 r = NIL 로 제거한다.

• Case2: r의 자식 노드가 하나인 경우

r은 r을 제거하면 r의 자식 노드로 연결이 끊어지므로 r의 부모 노드에서 r을 가리키고 있던 포인터를r의 자식을 가리키도록 바꾸어준다.

(a) 30을 검색하고 30에 자식이 있는지 확인한다.

(b) 30에는 자식이 하나인 것을 확인하고 case2임을 인지한 후 삭제한다. (개념적인 설명을 하기위해 삭제한다라고 하였고 실질적으로는 바로 C의 과정을 거친다)

(c) 30은 48과 연결되어 있으므로 right[28] = 48로 연결한다.

• Case3: r의 자식 노드가 두 개인 경우

  자식 노드가 두 개인 경우에는 이진 검색 트리의 성질을 끊지 않는 것이 중요하다. 만약 아래의 그림에서 28을 삭제한다고 했을때 40을 28이 있던 자리에 배치하게 된다면
  이진 트리가 되지 않고 다진 트리가 되기 때문에 성질을 유지해서 놓아야 한다.
  
  

(a) 28을 삭제하고 28의 다음 원소인 값을 찾는다.

(b) 다음 원소의 값을 찾기 위해서 right[r]의 left[최하단]의 값을 찾는다.

(c) 다음 원소 부모 노드는 다음 원소를 r으로 옮긴다.

(d) 다음 원소가 있던 자리에 다음 원소의 자식을 놓는다.

 

이를 Pseudo 코드로 나타낸다면 조금 복잡하지만 함께 해석해보자.

t: 트리의 루트 노드
r: 삭제하고자 하는 노드
p: r의 부모 노드

treeDelete(t, r, p){
    if(r=t) then root <-deleteNode(t); //

    else if(r=left[p]) then left[p] <-deleteNode(r); //p의 왼쪽 자식인 경우
    else right[p] <- deleteNode(r); // p의 오른쪽 자식인 경우
}

deleteNode(r){
    if(left[r] = right[r] = NIL) then return NIL; //자식 노드가 없는 경우 Case1
    else if (left[r] = NIL and right[r] != NIL) then return right[r]; // 자식 노드가 하나인 경우 Case2-1 (오른쪽에 자식이 있는 경우)
    else if (right[r] = NIL and left != NIL) then return left[r]; // 자식 노드가 하나인 경우 Case2-2 (왼쪽에 자식이 있는 경우)

    else{     // 자식 노드가 두 개인 경우 Case3
        s <- right[r]; // 삭제하고자 하는 노드 오른쪽 값을 
        while(left[s] != NUL){ //다음 값의 왼쪽 리프노드를 찾는다.
            parent <- s;
            s <- left[s];
        }
        key[r] <-key[s];
        if(s=right[r]) then right[r] <-right[s];
        else left[parent] <-right[s];

        return r;
    }
}

이진 검색 트리(Binary Search Tree)의 시간 복잡도

검색의 경우 O(log n) 이다.

 

삽입의 경우 n개의 원소로 이진 트리를 만들 때, 이진 검색 트리가 가장 이상적으로 균형이 잡히면 최악의 경우라 해도 O(logn) 이지만 가장 나쁘게 기울변 평균 검색 시간이 O(n)이 된다.

 

삭제의 경우 Case1과 Case2는 상수 시간이 들며 Case3은 노드 r의 직후 원소를 찾는데 최악의 경우 트리의 높이에 비례하는 시간이 든다. 따라서 최악의 시간은 트리의 높이에 따라

O(log n)과 O(n) 사이이다.

이진 검색 트리(Binary Search Tree)의 특징

이진 탐색 트리는 시간 복잡도가 O(logn)일 수도 있고 O(n)이 될 수도 있다고 했는데 이는 트리의 높이에 따라 결정되는 것이다.

만약 이진검색트리가 극단적인 구조로 한 쪽 노드에만 몰려있다면 탐색을 할 때 재귀적 관점(O(logn))으로 쪼개지지 않는다면 한 쪽으로 계속 탐색을 하여 결국 O(n)이 될 것이다.

 

이것을 해결하기 위해 AVL 트리라는 것이 나왔는데 AVL 트리는 다음에 알아보는 것으로 하자.

이진 검색 트리(Binary Search Tree)의 자바 소스 코드