[알고리즘] 7. 이진 탐색 트리

-이진 탐색 트리: 이진 탐색을 위한 이진트리이다.

 

??: "이진 탐색 알고리즘이 있는데 왜 이진 탐색 트리가 필요?"

-> 이진 탐색은 데이터 집합이 배열인 경우에만 사용가능하다.(사전에 정의된 크기의 데이터 닙합에 대해서만 사용이 가능하고, 동적으로 그 크기가 달라지는 데이터 집합(예를 들어 링크드리스트)에는 적용이 불가능하다)

 

-이진 탐색트리 노드 규칙

: 왼쪽 자식 노드는 나보다 작고, 오른쪽 자식 노드는 나보다 크다. 

 

1. 이진 탐색트리 노드 정의 

 

2. 함수 정의 

 

3. 이진탐색트리 생성 

 

4. 이진탐색트리 노드 삭제 

 

5. 이진탐색트리 삭제 

 

6. 이진탐색트리 노드 찾기 

 

7. 이진탐색트리 최소값 노드 찾기 

 

8. 이진탐색트리 노드 삽입 

: 이진 탐색트리에서 노드 삽입 연산은 '새 노드가 삽입될 곳은 어디인가'를 찾아내는 거시 핵심이다.

새 노드가 삽입될 곳을 이진탐색으로 찾아야한다. 

 

 

9. 이진 노드탐색 노드 삭제 

: 삭제 과정이 삽입 과정보다 더 복잡하다. 

과정 1) 삭제할 노드를 찾아야한다. 2) 노드를 트리에서 떼어낸다.(노드의 상황에 따라서 뒷정리하는 과정 달라짐. 첫번째는 양쪽 자식 노드를 모두 갖고 있는 경우, 다른 하나는 왼쪽/ 오른쪽 중 어느 한쪽 자식 노드만 갖고 있는 경우)

 

자식 트리가 있는 노드를 삭제할 때 그 빈자리에 무엇으로 채워야할까?

->삭제된 노드의 오른족 하위트리에서 가장 작은 값을 가진 노드를 삭제 노드의 위치에 옮겨 놓는다. 

 

10. 이진탐색트리 전위법?으로 출력