Binary Search Tree(이진탐색트리)

 

Binary Search (이진탐색, 이분탐색)

 

이진탐색트리에 대해 알아보기 전에 '이진탐색' 이 무엇인지 알아야 합니다. 

사전(Dictionay)에는 1) List 2) Search table 3) hash table 이 있었습니다. 이 중  2) 서치테이블은 정렬된 배열

즉, sorted array를 통해 구현되는 사전을 의미합니다. 정렬된 '배열' 로 구현하는 이유는 이진탐색 방식을 수행하기 위함입니다. 

 

탐색 연산 수행시 이미 배열이 정렬된 상태이기에, O(logn)-time 이 걸리지만, 삽입과 제거 연산에서는 '배열'이기 때문에 최악의 경우 n/2 만큼의 원소를 이동시켜야 하는 번거로움이 유발되며 이는 곧  O(n)-time 의 수행시간이 걸리게 됩니다. 

 

<이진탐색의 시간복잡도>

find(k)	O(log n)
put(k)	O(n)
erase(k)	O(n)

 

 

→ 탐색 위주의 dictionary 

 

 

Perfomance

이진탐색을 수행하는 방식으로는 1) 반복문 2) 재귀 방식이 있습니다.

 

<재귀방식으로 구현한 이진탐색 의사 코드 >

Algorithm BinarySearch(int[] s, int l, int h, int k )
	if(l>h) //비교원소가 없음
    	return -1; 
    else 
    	int m = (l + h) % 2 ; 
        if(k == s[m].key())//탐색 성공
        	return m; 
        else if(k < s[m].key())
        	return BinarySearch(s, l, m-1, k); 
        else // k> s[m].key()
        	return BinarySearch(s, m+1, h, k);

 

 

 

 

 

본론으로 돌아와, 이진탐색트리에 대해 알아보도록 하겠습니다 ! 

 

Concept

: 이진탐색트리란, 왼쪽자식key값 <= 부모key값 <= 오른쪽 자식key값의 조건을 만족하는 (자식을 최대 2개 갖는) 이진트리입니다. 

 

 

Propertry

- 이진트리 기반의 자료구조 

- 검색목적의 자료구조이므로 해당노드는 유일한 키값을 갖도록 하는 게 좋다. 

- 이진탐색트리를 Inorder traversal(중위순회) 하면, 오름차순으로 노드를 방문할 수 있다. 

- O(n) - space ( internal - n개  + external n +1 개 = 2n+1)

 

 

 

 

 

ADT 

 

1. Search(탐색)

- 루트에서 시작 , leaf 까지 자식의 key 값과 비교 key값을 비교하며 탐색 수행한다.

- 

 

<의사코드>

Algorithm BinarySearchTreeSearch(k, v)//비교 key 값, 현재 임의의 노드 
	if v.leaf() 
    	return v
    if k < v.key() 
    	return BinarySearchTreeSearch(k, v.left())
    else if k = v.key()
    	return v
   	else // k > v.key()
    	return BinarySearchTreeSearch(k, v.right())

 

※ 이진탐색트리는 이진탐색과 달리, 원소의 수를  n/2로 보장하지 않습니다. ex)  skewed tree

 

 

2. Insertion 

- put (k,o) 

- 새로운 노드 동적 할당 v

- 탐색 후 해당 leaf노드 w 에 v 복사

-  w 노드의 left, right NULL 할당

 

 

 

3. Deletion

삭제연산은, 탐색과 삽입 연산에 비해 좀 더 복잡합니다. 이는 해당 노드의 자식lefa노드 개수로 경우를 나누어 구현할 수 있습니다. 

- erase(k) 은 탐색연산을 전제로 이어짐 

 

case 1. v의 자식 중 1개라도 leaf 노드인 경우 

- 왼쪽자식이 leaf 인지 확인 

  1) leaf 라면, 오른쪽 자식과 관계없이 v의 부모노드 - v의 오른쪽 자식 연결 

  2) leaf가 아니라면, 오른쪽 노드가 leaf인지 확인 - > 오른쪽 노드 leaf -> v의 부모노드 - v의 왼쪽자식 연결

 

case2. v 자식 모두 leaf

case 1- 2)에서 오른쪽 자식도 leaf노드로 확인되었다면,  v노드가 부모노드의 왼/오른쪽 자식인지에 따라 v의 자리를 NULL

즉, leaf 노드로 수정한다. 

 

case3. v의 자식 중 어떤 것도 leaf 가 아닐 때 

- case 1 - 2)에서 오른쪽 자식이 leaf노드가 아님이 확인되었다면, 결국 두 자식 노드 모두 leaf가 아님을 의미한다. 

- v노드의 오른쪽 자식 서브트리에서 가장 작은 후임자노드(successor) 찾기

  or 왼쪽 자식 서브트리에서 가장 큰 전임자노드(predeccessor) 찾기 

- v의 key와 후임자/전임자 노드의 key값 바꿔치기

- 후임자/전임자 노드는 이미 적어도 하나의 leaf 를 갖고 있기 때문에  →  case 1 or case 2 로 삭제 연산 수행 

 

Performance

- O(n) - space 

- O(h) - time → O(n) -time

- worst case -  O(n)-time Skewed Tree

- best case - O(log n)- time Complete Tree(완전이진트리) 

  ㄴ + 완전이진트리는 편향된 이진트리와 다르게 O(logn)의 빠른 검색속도를 보장한다. 

  ㄴ -  그 대신, 자료가 추가될 경우 완전이진트리를 유지하기 위해 트리의 모양을 바꿔야 한다. 즉, 삽입,제거 속도가 느림.

 

※ 이진탐색트리의 경우, 최악의 경우(skewed binary tree) O(n)-time의 시간복잡도를 가진다. 

    (계속해서 자료가 추가되면 트리의 높이는 계속 커지게 되어 수행시간에 악영향을 미치게 된다.)

    최선의 경우(complete tree) 는 빠른 검색속도를 갖지만, 삽입과 제거연산 시 수행시간이 느리다. 

    이를 보안하기 위한 트리가 바로 균형이진탐색트리(Balanced Binary Search Tree) 이다. 

 

※ 균형이진탐색트리는 검색, 삽입, 삭제 연산 모두 O(log n)의 시간복잡도를 가진다.