[자료구조] 이진 탐색 트리에서의 연산(탐색 연산, 삽입 연산, 삭제 연산)

 BST(Binary Search Tree)란 탐색을 효율적으로 하기 위한 자료구조이다.

 

BST(이진탐색트리)

이진탐색트리는 다음과 같은 특징을 가진다.

1) 이진트리이며 모든 원소는 서로 다른 유일한 키를 가짐

2) 왼쪽 서브트리의 key값< 루트의 key값< 오른쪽 서브트리의 key값

3) 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리

 

-이진탐색 트리의 연산

1) 탐색(searchBST()) 연산

 

루트에서 시작, 탐색할 키값 X를 루트노드의 키값과 비교한다. 키값이 루트노드의 키값과 같으면 탐색 성공, 크거나 작으면 각각 오른쪽, 왼쪽으로 위치시켜 다시 탐색연산 수행

-탐색 방법: 반복적 방법, 순환적 방법(재귀적으로 수행)

 

2) 삽입(insertBST())연산

 

탐색연산이 모두 완료된 이후에 진행된다. 탐색이 실패한 위치에 원소를 삽입하는 원리이다.

 

3) 삭제(deleteBST())연산

 

마찬가지로 먼저 탐색연산을 진행한 후에 진행시킨다. 탐색하여 찾은 노드를 삭제하는데, 이 떄 삭제할 노드의 차수에 따라 삭제 방법이 나뉜다. 

삭제 노드의 차수가 0이면 부모의 자식 필드를 NULL 처리 후 삭제, 차수가 1이면 삭제될 노드의 자식을 부모노드에 연결시킨 후 삭제, 차수가 2이면 후계자를 선택하여 자리를 물려주는 구조이다.(이 때 후계자는 왼쪽 서브트리중 가장 큰 원소 혹은 오른쪽 서브트리 중 가장 작은 원소가 된다)