이진 검색 트리 Binary Search Tree

저번 시간에는 탐색에 대해서 살펴봤는데, 특정 자료가 존재하는지 찾아보기 위해 매 번 트리를 탐색하는건 매우 비효율적인 방법이다.

그래서 만든 이진트리의 변형이 바로 이진 검색 트리다.
핵심은 각 노드에 들어갈 수 있는 값을 제한하는 것이다.
가령 부모 노드와 값을 비교해서 작으면 왼쪽, 크면 오른쪽 노드로 가게 한다던가 하는 등의 제한을 두는것.

검색 연산

(자연수 비교의 경우)

1. 루트 노드에서 시작해서 찾는 데이터가 노드의 데이터보다 작으면 왼쪽 노드로, 크면 오른쪽 노드로 이동.
2. 찾는 데이터가 노드의 데이터와 같으면 현재 노드를 리턴
3. 찾는 데이터를 리프노드에 도착할 때 까지 찾지 못하면 Null을 반환(리프노드의 모든 포인터는 다 null이기 때문에)
   

재귀 vs while 반복

재귀에 대한 수업때 설명한 내용이지만, 재귀호출은 일반적으로 스택메모리를 더 많이 사용하므로 공간 복잡도를 더 많이 필요로 한다. ($O(1)$ 과 $O(n)$)
그래서 위의 검색 예시에서도 다음과 같이 while 반복을 사용하면 같은 일을 훨씬 효율적으로 수행할 수 있다.

Node* search(Node* root, int target) {
    Node* current = root;

    while (current != NULL) {
        if (target < current->data) {
            current = current->left;
        }
        else if (target > current->data) {
            current = current->right;
        }
        else {
            return current;
        }
    }

    return NULL;
}

전임 후임 노드

중위 전임 노드, 후임 노드 :
모든 노드들을 오름차순으로 정렬했을 때, 해당 노드의 왼쪽과 오른쪽에 위치한 노드들을 말한다.
트리 구조안에서 자기 왼쪽, 오른쪽이 아니라.

삽입

검색 연산과 매우 비슷하다.
트리에 5를 넣고싶다면 5를 넣을 위치로 찾아가서 5가 없다면 그 자리에 삽입하면 끝.
그런데 주의할 점은, 새로운 노드를 삽입하면 부모 노드에게 새로운 노드 주소값을 전달해줘야 한다는 점이다.