알고리즘 3 이진탐색트리

리스트로는 이진탐색을 구현하기가 대개 어렵기 때문에,

트리기반으로 데이터를 적재하고 이진탐색을 구현하는 방법이다.

 

탐색 자체는 리스트보다 훨씬 수월해진다. 

문제는 관리 측면이다. 특히 관리 중에서도, 삭제가 그렇다.

 

특정 노드를 삭제하게 될 경우,

삭제되는 트리의 차일드 트리의 처리를 별도로 해줘야 하기 때문이다. 

1. 차일드가 없는 경우 -> 아무 문제 없다

2. 차일드가 하나 있는 경우 -> 차일드를 삭제한 노드 위치에 차일드를 붙인다.

3. 차일드가 둘 다 있는 경우 -> 우측 트리의 최솟값 노드를 삭제한 위치로 옮긴다

                                                 

3번의 경우, 최솟값노드의 차일드 처리도 해주어야 한다.

최솟값노드의 차일드는 1번째 아니면 2번째일텐데

(오른쪽 차일드를 가지거나 안거지거나 경우로 특정된다.

최솟값이 전제이므로 왼쪽 차일드는 있을 수가 없다) 

1번째인 경우, 그대로 알고리즘이 종료될 것인고,

2번째인 경우, 기존의 알고리즘이 다시 재귀로 호출되야 한다. 

 

GitHub - Sukmin-LanternK/Algorithm