Binary search tree

Binary search tree의 원리 및 정의

 

Binary search tree는 Binary tree를 이용하는 검색방법이다. 부모가 자식을 최대 왼쪽, 오른쪽으로 최대 2개까지 가진다. 자료를 삽입하거나 제거할 때 자료를 밀고 당기는 작업이 필요 없어 동적인 자료구조에 효율적이다. 트리 구조는 배열 또는 링크드 리스트로 구현하는데, 링크드 리스트로 구현 하는게 코드는 짜기 어렵지만 더 효율적이다. 그리고 이번 과제도 링크도 리스트로 구현하도록 되어있다.

Binary search tree의 특징은 왼쪽자식은 부모보다 작은값을 가지고, 오른쪽 자식은 부모보다 큰값을 항상 가진다는 것이다. 이 간단한 원리가 binary search tree를 이루는 근본 원리이며, 삽입, 삭제 탐색의 기본 원리로 작용 하게 된다.

Binary search tree는 평균 Binary search와 유사하므로 평균의 실행시간이 걸리며, 최악의 경우 0(N), 즉 트리의 높이가 된다.(균형이 전혀 잡혀있지 않을때) 이런 상황이 일어나지 않도록 트리의 균형을 맞춰주는 것이 필요하기도 하다.(Balanced Search Tree)

 

Binary search tree의 검색

 

Binary search tree의 탐색방법은 간단하다. 탐색은 맨 위 루트부터 시작한다. 현재 노드의 키 값과 탐색하고자 하는 값을 비교하여 같으면 탐색이 성공한 것이다.

현재 노드의 키 값과 탐색 값을 비교하여 탐색 값이 크다면 오른쪽 자식으로 가서 탐색을 계속 한다.(오른쪽 서브 트리에서 탐색한다.) 이와 반대로 현재 노드의 키 값과 탐색값 을 비교하여 탐색 값이 작으면 왼쪽 자식으로 가서 탐색을 계속한다.(왼쪽 서브 트리에서 탐색한다.)

탐색과정에서 마지막까지 가면, 즉 가리키는 곳이 Null인 곳을 만나게 되면 값이 탐색이 실패 한것이다.

알고리즘을 간단히 정리하여 다시 써보면,

1.     키 값이 현재 노드의 값과 같으면 찾은 것이다.

2.     키 값이 현재 노드의 값보다 크다면 오른쪽 자식 노드로 간다.

3.     키 값이 현재 노드의 값보다 작다면 왼쪽 자식 노드로 간다.

4.     만일 현재 노드가 NULL 이면 차지 못한 것이다.

 

Binary search tree의 삽입

 

Binary search tree에서 삽입은 tree의 원칙을 깨지 않는 한도에서 이루어 져야 한다. 위에서 설명한 검색과 비슷한 방법이 쓰인다. 이진 나무의 노드를 삽입할 노드와 비교하면서 외부 노드(external node)가 나올 때까지 순회한다. 그리고 외부 노드의 Null로 지정된 빈자리에 삽입을 하는 것이다. 검색과 비슷한 원리므로 더 자세한 설명을 하지 않겠다.

 

Binary search tree의 삭제

 

Binary search tree에서 삭제는 까다로운 작업이다. 일단 삭제할 노드가 몇 개의 자손을 가지는가에 따라 삭제유형을 3가지로 분류할 수 있다.

1.     노드의 자식이 하나도 없는 경우 (외부노드)

2.     노드의 자식이 하나 있는 경우

3.     노드의 자식이 둘인경우

 

노드의 자식이 하나도 없는 경우에는 그냥 간단하게 삭제할 노드를 메모리 해제(c언어에선 free) 시켜주면 된다. 두번째 경우도 삭제할 노드 바로 밑 자식 노드를 삭제하고자 하는 노드의 부모에게 원리에 맞게 왼쪽 오른쪽만 정하여 연결하여 주면된다.

자식이 둘인 세번째의 경우가 복잡하다. 간단하게 말로 설명하면, 왼쪽 서브 트리의 가장 큰 원소를 가진 노드 또는 오른쪽 서브 트리의 가장 작은 원소를 가진 노드를 삭제하고 삭제된 노드의 원소 값을 자신의 원소 값으로 하면된다.

 

 

첫 번째 삭제 케이스

두 번째 삭제 케이스

세 번째 삭제 케이스

Binary search tree의 순회방법과 정렬

 

Binary search tree의 순회는 뿌리는 먼저 타는 Preorder, 뿌리를 중간에 타는 Inorder, 뿌리를 나중에 타는 Postorder, 층별로 타는 Level order 등이 있다. 이것들을 구현하려면 재귀 호출을 이용하면 쉽게 구현할 수 있다.

예를들어 Inorder의 알고리즘을 간략하게 보면

1.     왼쪽 서브 트리를 방문한다. (재귀함수로)

2.     뿌리를 먼저 방문한다.

3.     오른쪽 서브 트리를 방문한다.(재귀함수로)

 

다른 방법들도 이와 비슷한 원리로 할 수 있다. 단 level order는 queue를 이용하여 나무를 타면된다.

Binary search tree의 정렬은 그 특징을 이용하면 쉽게 구할 수 있다. 트리의 왼쪽자식이 부모보다 작고 오른쪽자식이 부모보다 큰 값을 가지므로, Inorder 순회를 하면 정렬된 값을 얻을 수 있게 된다. 즉 이 과제에 있는 alphabetical 순서도 Inorder 순회를 이용하면 쉽게 구할 수 있다.

 

 

Binary search tree의 모든 노드 삭제 방법

 

Binary search tree에서 모든 노드를 삭제(파괴, 메모리 해제) 하는 방법은 재귀함수를 이용 하는것이다. 루트부터 시작하여 후위 순회법(postorder) 을 사용하여 삭제를 하여 주면 된다.

간단히 알고리즘을 보면

1.     왼쪽 서브 트리를 방문한다.(재귀함수로)

2.     오른쪽 서브 트리를 방문한다.(재귀함수로)

3.     메모리 해제

와 같이 해주면 된다.