__[8.5f] 이진 트리의 탐색

[문교식]

[8.5f] 이진 트리의 탐색

<<<<<  목 차  >>>>>

1. 탐색의 개념

2. 이진탐색트리의 정의

3. 이진탐색트리의 적용

4. 효율적인 이진탐색트리
====================

1. 탐색의 개념

트리에 저장된 데이터를 찾아내는 방법이다.

물론 트리에 있는 모든 노드를 하나씩 다 찾아보면 될 것이다.

그러나 효율적 탐색을 위하여

여러 가지 자료구조적인 방법을 고안하고 있다.

여기서는 가장 일반적으로 많이 사용되는 탐색방법을 배운다.

데이터를 찾기 위한 특별한 값을 키(key)라 하는데

키라는 말의 뜻을 생각해보자.

열쇠가 있어야 집의 문을 열수 있다.

집의 열쇠에 해당하는 것이 키(key)이다.

집의 열쇠가 있어야 어떤 특정한 집의 문을 열고 들어갈 수 있듯이

자료 검색에 있어서의 키도

어떤 특정한 데이터를 찾아주기 위한 역할을 하고 있다.

자료의 저장과 찾기를 위한 키(key)의 예를 여러분의 주변에서 찾아보자.

자료에 대한 킷값을 살펴보자. 
  1) 대학의 학생자료 데이터베이스; 키=학생번호 
  2) 주민정보 데이터베이스; 키=주민번호 
  3) 경찰서의 차량 데이터베이스; 키=자동차번호

[예제] 도서관에서 대출할 때 사용하는 도서 데이터베이스의 키는 무엇일까?

2. 이진탐색트리의 정의

이제 효율적인 탐색을 위하여 이진트리를 어떻게 사용하는지 살펴보자. 

모든 노드는 일정한 형태의 키가 하나 있다. 
하나의 키는 반드시 하나의 노드와 일대일 대응이 된다. 

각 노드의 킷값은 왼쪽 서브트리의 모든 노드의 킷값보다 작지 않고 

오른쪽 서브트리의 모든 노드의 킷값보다는 크지 않다. 

이러한 형태의 이진트리를 이진탐색트리(binary search tree)라고 부른다. 
     

[예제] 그림의 트리는 이진탐색트리인가?

          아래의 물음에 숫자, "있다", "없다", "크지않다", "작지않다"로 답하시오.

 

1) 루트의 킷값은?               
2) 루트의 킷값은 루트의 왼쪽서브트리(노드16으로 구성되는 루트가 16인 트리)의

    모든 노드의 킷값보다             (16<20). 

3) 루트의 킷값은 루트의 오른쪽서브트리의 모든 노드의 킷값보다           
    (20<34, 20<26, 20<33, 20<32, 20<43). 
4) 킷값이 34인 노드의 왼쪽서브트리(26,33,32 노드로 구성되는 루트가 26인 트리)의

    모든 노드의 킷값은 34보다             
    (34>26, 34>33, 34>32). 

 

5) 킷값이 34인 노드의 오른쪽서브트리(43 노드로 구성되는 루트가 43인 트리)의

    모든 노드의 킷값은 34보다           (34<43). 

6) 킷값이 26인 노드의 왼쪽서브트리는            . 

7) 킷값이 26인 노드의 오른쪽서브트리(33,32 노드로 구성되는 루트가 33인 트리)의

    모든 노드의 킷값은 26보다           (26<33, 26<32). 

8) 킷값이 33인 노드의 왼쪽서브트리(32 노드로 구성되는 루트가 32인 트리)의

    모든 노드의 킷값은 33보다           (33>32). 

9) 킷값이 33인 노드의 오른쪽서브트리는           .

     이와 같이 모든 조건을 만족하므로 그림은 이진탐색트리라 할 수 있다.

3. 이진탐색트리의 적용

그림에서 킷값이 33인 노드를 찾는다 하자. 

 
    1) 루트를 방문한다. 루트의 킷값이 20이므로 찾고자하는 노드(=33)는

        루트의  오른쪽 서브트리에 있음을 알 수 있다. 

    2) 노드34를 만난다. 33은 34보다 작으므로 왼쪽으로 내려간다. 

   

3) 노드26을 만난다. 33은 26보다 크므로 오른쪽으로 내려간다. 

    

     4) 노드33을 발견한다. 찾고자하는 킷값과 일치한다.

  만약 찾고자하는 킷값이 35라면?
    1) 노드34에서 오른쪽으로 내려갈 것이다.
    2) 노드43을 만나는데 단말노드이므로 더 찾을 데이터가 없다.
        즉, 이 트리에는 찾고자 하는 데이터가 없다.

4. 효율적인 이진탐색트리  

다음과 같은 데이터를 킷값으로 하는 이진탐색트리를 구성해 보자. 
데이터; 34, 43, 26, 99, 20, 16, 93, 33, 65, 78, 90, 32, 44, 50, 76, 88 
  

이제 루트의 킷값이 50인 이진탐색트리를 생각해 보자 (그림).

 
 

[예제] 그림의 트리는 이진탐색트리의 조건을 만족하는지 확인해 보자. 
     

이제 동일한 데이터에 대하여 루트가 20인 경우의 이진탐색트리를 생각해 보자.

검색 효율을 고려해 보자.

검색의 효율을 판단하는 근거는 무엇일까?

단말노드까지 찾아 들어갈 때 균등한 깊이를 제공하는가?

한쪽으로 치우치지 않고 깊이가 고른 트리가 균형이 잡혔다고 볼 수 있다(balanced).
이 트리는 균형있는 모습을 보이고 있는가? 

(답; 아니다. 단말노드의 깊이가 서로 차이가 많다)

트리를 좀 더 효율적으로 만들어 보자. 
각 노드의 좌우 서브트리가 비슷한 크기로 만들 수 있다. 
그림은 그 한 예를 보여준다. 

 

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆

[연습문제] 아래의 트리를 최대한 효율적인 이진탐색트리로 재구성하시오. 
 

//