1. Binary Search Tree 만들기 - 삽입과 탐색

시작 하기 전에, Tree에서 구현한 BinaryTree 헤더 파일과 소스파일이 필요하다.

그리고 BinarySearchTree에서의 삽입과 탐색 그리고 삭제 함수들은

모두 BinarySearchTree 헤더 파일과 소스 파일에 구현하도록 함.

 

1. 이진 탐색 트리의 정의

이진 탐색 트리란 이진 탐색 트리의 성질을 만족하는 이진 트리를 말한다.

이진 탐색 트리의 정의는 아래와 같다.

 

(1). 모든 노드의 키는 유일하다.

(2). 왼쪽 서브 트리의 키들은 루트의 키보다 작다.

(3). 오른쪽 서브 트리의 키들은 루트의 키보다 크다.

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

 

위의 정의와 같이, 찾고자 하는 키값이 이진 트리의 루트 노드의 키값과 비교하여 작으면

우리가 찾고자 하는 키값은 왼쪽 서브 트리에 있고, 루트 노드보다 크면 찾고자 하는 키값은 오른쪽 서브 트리에 있음을 쉽게 알수 있다. 

 

아래의 그림을 보자.

위의 그림의 트리는 이진 탐색 트리가 된다.

왼쪽 서브 트리에 있는 값들은 루트 노드인 18보다 작다.

오른쪽 서브 트리에 있는 값들은 루트 노드인 18보다 크다.

위의 성질은 모든 노드에서 만족된다.

위의 탐색 트리를 중위 순회 방법으로 순회 하면

3, 7, 12, 18, 26, 27, 31 로 숫자들의 크기 순이 된다.

 

2. 이진 탐색 트리의 탐색

이진 탐색 트리에서 특정 키 값을 가진 노드를 찾기 위해서는 먼저 주어진 탐색키 값과

현재의 루트 노드의 키값을 비교한다.

비교한 결과에 따라, 아래의 3가지로 나누어 진다.

 

(1). 비교한 결과가 같으면 탐색이 성공적으로 끝난다.

(2). 주어진 키값이 루트 노드의 키값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로

    다시 시작한다.

(3). 주어진 키값이 루트 노드의 키값보다 크면, 탐색은 이 루트 노드의 오른쪽 자식을 기준으로

   다시 시작한다. 

 

즉, 루트 노드보다 작으면 왼쪽 서브 트리로,

루트 노드보다 크면 오른쪽 서브 트리로 진행하면 된다.

그 이하의 노드에서도 같은 과정을 되풀이 하면 된다.

 

위의 그림을 다시 가지고 오자.

우리가 12를 탐색값이라고 보면, 아래와 같이 탐색이 이루어진다.

이진 탐색 트리의 탐색을 구현하는 방법은 순환적 방법과 반복적인 방법이 있다.

아래는 순환적 방법이다.

 

이진 탐색 트리 탐색 알고리즘 의사코드 ( 반복적 방법 )

이진트리에서 탐색하는 방법에는 순환적인 방법이 아닌 반복적인 방법도 존재.

효율성을 따지면, 반복적인 함수가 훨씬 우수하다.

반복적인 탐색 함수는 먼저 매개변수 node가 NULL이 아니면 반복을 계속한다.

반복 루프 안에서는 현재 node의 키값이 key와 같은지를 검사한다.

만약 같으면 탐색 성공이므로 현재 노드 포인터를 반환하고 끝낸다.

만약 key가 현재 노드 키값보다 작으면 node 변수를 node의 왼쪽 자식을 가르키도록

변경한다.

또한 key값이 현재 노드 키값보다 크면 node 변수를 node의 오른쪽 자식을 가르키도록

변경한다.

이러한 반복은 결국 단말 노드까지 내려가서 node가 NULL값이 될 때까지 계속된다.

만약 반복이 종료되었는데도 아직 리턴이 되지 않았다면

탐색이 실패한 것이므로 NULL을 반환한다.

여기서는 함수의 매개변수 node를 직접 사용하였는데,

사실 매개변수는 원본 변수의 복사본이므로

변경하여도 호출한 함수에는 별 영향이 없다. 그냥 사용해도 된다. ​

 

이진 탐색 트리 탐색 알고리즘 의사코드 ( 순환적 방법 ) 

알고리즘 설명

(1). 이진 탐색 트리가 NULL상태이면 그냥 복귀한다.

(2). 탐색키가 현재 트리의 루트 키값과 같으면 루트를 반환한다.

(3). 탐색키가 루트 키값보다 작으면, 왼쪽 서브 트리를 순환 호출을 이용하여 탐색한다.

(4). 그렇지 않으면 오른쪽 서브 트리를 순환 호출을 이용하여 탐색한다.

 

3. 이진 탐색 트리의 삽입

이진 탐색 트리에 데이터를 삽입하기 위해서는 먼저 탐색을 수행하는 것이 필요하다.

이유는 이진 탐색 트리에서는 같은 키값을 갖는 노드가 없어야 하기 때문이다.

또한 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치가 되기 때문이다.

이진 탐색 트리에 대한 삽입 알고리즘을 간단하게 기술하면 아래와 같다.

위의 그림을 다시 가져와 보자.

위의 이진 탐색 트리에 9를 삽입해보자.

삽입하기 위해서는 먼저, 9를 탐색을 해본다.

아래의 그림을 보자.

만약에, 탐색이 성공하면 이미 9가 트리 안에 존재하는 것이고,

탐색키가 중복되는 것이므로, 삽입이 불가능하다.

만약 9가 트리 안에 없다면 어디선가 탐색이 실패로 끝날 것이다.

바로 실패로 끝난 위치가 9가 있어야 할 곳이 된다.

따라서 탐색이 실패로 끝난 위치인 12의 왼쪽에 9를 삽입하면 된다.

아래의 그림을 보자.

이진 탐색 트리 삽입 알고리즘 의사코드

알고리즘 설명

pParent는 부모 노드 포인터, pCur는 탐색을 위한 포인터

1. pCur가 NULL이 될 때까지 탐색을 수행한다.

2. 현재 탐색 포인터의 값을 부모 노드 포인터에 복사한다.

3. 삽입할 키값이 pCur의 키값보다 작으면 왼쪽 자식 노드로 진행.

4. 삽입할 키값이 pCur의 키값보다 크면 오른쪽 자식 노드로 진행.

5. 반복이 끝났고, 만약 부모 노드가 NULL이면, 현재 트리가 NULL상태이다.

   따라서 새로운 노드를 루트로 설정한다.

6. 부모 노드의 키값과 비교하여 작으면 왼쪽 자식으로 연결,

    그렇지 않으면 오른쪽 자식으로 연결한다.

 

이진 탐색 트리의 삽입 함수는 재귀 함수의 현태로 만드는 법을 추천하는데,

그 이유는 나중에 뒤에서 할 AVL 트리 때문.

그리고, 마지막으로 아래는 이진 탐색 트리의 루트 노드를 초기화 하는 함수

아래는 메인 함수

프로그램 실행 결과

아래는 헤더 파일과 소스 파일

BinarySearchTree.c

0.00MB

BinarySearchTree.h

0.00MB

BinaryTree.c

0.00MB

BinaryTree.h

0.00MB

common.h

0.00MB

main.c

0.00MB