TIL-2018-12-12-WED

드디어 컴퓨터 사이언스 부트캠프 with 파이썬의 1독이 끝났다.

다시 또 읽어가면서 내 코드로 만들 생각에 막막하지만 시간을 들이다보면 충분히 이해가 가능한 내용들이라 시간만 투자하면 될 것 같다.

오늘 읽은 내용은 14장. 이진 탐색 트리, 15장 알고리즘 파트.

(참고: 컴퓨터 사이언스 부트캠프 with 파이썬, 위키백과, 구글 등)

이진 탐색 트리(BST: binary search tree)의 특징

- 각 노드에 특정 값이 존재하며, 이진 탐색 트리는 각 노드를 비교해서 정렬시키기 때문에 중복값은 존재할 수 없다.

- 어떤 특정 노드를 선택했을 때 선택한 노드를 기준으로 좌측은 작은 노드(숫자) // 우측은 큰 노드(숫자)로 이루어져 있다.

출처: 위키백과 영문판

이진 탐색 트리의 삽입(insert 알고리즘)

삽입을 하기 전 검색 수행하며, 루트 노드의 데이터부터 크기 비교를 시작하여 작으면 왼쪽, 크면 오른쪽에 노드를 삽입한다.

이진 탐색 트리의 찾기(search 알고리즘)

대상 데이터(target)을 루트 노드부터 비교하면서 내려온다.

노드의 데이터가 대상 데이터와 같다면 노드를 반환하며, 빈 노드를 만날 때까지 대상 데이터와 같은 노드를 만나지 못한다면 None를 반환

즉, target 과 트리의 값을 비교해가며 작으면 왼쪽, 크면 오른쪽으로 이동하여 찾고자 하는 노드로 이동

이진 탐색 트리의 삭제(remove 알고리즘)

- 자식노드가 없는 경우

노드(리프 노드)는 단순히 삭제한다.

- 자식노드가 1개인 노드 삭제 

대상 데이터가 노드 데이터보다 작으면 대상 데이터를 가진 노드를 지운다(재귀함수 호출)

- 자식노드가 2개인 노드 삭제

삭제하고자 하는 노드의 값을 바로 삭제하지 않고 대체할 노드를 찾은 다음 대체 노드와 삭제 노드를 교체한 다음 해당 노드 삭제