[자료구조] 이진 탐색 트리

이진 탐색 트리는 Binary Search Tree 즉, BST라고 한다

각 노드의 자식 노드가 최대 2개인 트리

 

사용하는 이유는 

1. 데이터의 효율적인 정렬
2. 검색
3. 삽입
4. 삭제 

 

모두 가능하게 하는 구조가 있다 

 

자세한 이유

 

1. 정렬된 데이터의 효율적인 검색 

• 평균 O(log n) 시간 복잡도로 데이터를 검색할 수 있다

 

2. 동적 데이터 집합 관리

• 데이터가 계속 추가, 삭제되는 동적인 환경에서도 효과적
• 삽입, 삭제도 O(log n)의 시간 복잡도를 가진다

 

3. 중위 순회를 통한 정렬된 데이터 접근

• 중위순회는 항상 정렬된 순서로 데이터에 접근하게 해준다 
• 정렬된 데이터를 순차적으로 처리할때 유용하다

 

4. 범위 탐색 및 순차 접근 용이

• 특정 범위의 데이터를 빠르게 검색
• 범위 내의 데이터를 효율적으로 순차적으로 탐색하는데 적합하다

 

5. 유연한 구조

• BST는 노드의 삽입과 삭제 가 비교적 간단하다
• 트리의 구조를 유연하게 변경 할 수 있다

 

6. 메모리 효율성

• 각각의 노드는 자신의 데이터와 두개의 자식에 대한 참조만을 가지고 있어서 메모리 사용이 효율적이다

 

하지만!

 

BST의 성능은 사실 트리의 균형상태에 크게 의존한다

만약에 트리가 균형 잡히지 않고 한쪽으로 치우쳐져 있다면 검색, 삽입, 삭제의 시간 복잡도는 최악의 경우 O(n)이 된다

 

이러한 문제점을 해결하게 위해서 AVL 트리나 레드-블랙 트리 같은 자가 균형 이진 탐색트리가 개발되었다

 

 

이진 탐색 트리는 이진 트리의 일종이라 각 노드가 최대 두개의 자식을 가지고 왼쪽 자식은 부모노드 보다 작은 값을 가지고 오른쪽 자식은 부모 노드 보다 큰 값을 가진다

 

 

연산 

 

탐색 

 

1. 루트 노드의 키와 찾고자 하는 값을 비교한다 만약 찾고자 하는 값이라면 탐색을 종료

2. target 값이 루트 노드의 키보다 작으면 왼쪽으로 탐색을 진행

3. target 값이 루트 노드의 키보다 크면 왼쪽으로 탐색을 진행

 

 

삽입

 

1. 삽입할 값을 루트 노드와 비교한다 (만약 같다면? --> 오류 발생 -> 이유는? 중복 값을 허용하지 않기 때문)

2. 삽입할 값이 루트 노드의 값 보다 작으면 왼쪽으로 탐색하여 비어있으면 추가, 비어있지 않으면 다시 값을 비교하여 반복한다

3. 삽입할 값이 루트 노드의 값 보다 크면 오른쪽으로 탐색하여 비어있으면 추가, 비어있지 않으면 다시 값을 비교하여 반복한다

 

 

 

삭제

삭제는 삽입 보다 복잡하다 

3가지의 시나리오가 있다

 

1. 삭제하려는 노드가 자식이 없는 단말 노드일 경우

 

 

• 삭제할 노드의 부모 노드가 있다면 부모 노드의 자식 노드를 null로 만들고 삭제할 노드를 삭제한다

 

2. 삭제하려는 노드의 자식 노드가 하나인 경우

 

• 삭제할 노드의 자식노드를 삭제할 노드의 부모 노드가 가리키게 하고 해당 노드를 삭제한다

 

3. 삭제하려는 노드의 자식 노드가 2개 인경우

해당 삭제할 노드를 찾고 삭제를 한다

그 후 여기에서 아래와 같이 2가지 방법으로 나뉜다

 

 

삭제할 노드 왼쪽 중에서 가장 큰 노드를 해당 노드의 자리에 옮긴다

 

 

 

 

 

아니면 오른쪽 중에서 가장 작은 노드를 해당 노드의 자리에 옮긴다