이진 탐색 트리
이진 탐색 트리는 binary search(이진 탐색)의 장점과 linked list(연결 리스트)의 단점을 보완하기 위해 만들어진 자료구조입니다.
연결 리스트는 자료의 삽입과 삭제는 빠른 시간 내에 할 수 있습니다. 하지만, 탐색은 앞의 노드에서 하나씩 탐색해야 하기 때문에 상대적으로 많은 시간이 소요됩니다.
이러한 연결리스트의 단점을 보완하기 위해 이진 탐색을 적용한 것이 이진 탐색 트리입니다.
현재 노드보다 값이 작은 노드는 왼쪽 노드로 나보다 값이 큰 노드는 오른쪽 노드로 붙여주는 간단한 아이디어를 적용하면 연결 리스트보다 빠르게 자료를 탐색할 수 있게됩니다.
이진 탐색 트리의 속성
-
1) 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.
-
2) 부모의 키가 왼쪽 자식 노드의 키보다 크다.
-
3) 부모의 키가 오른쪽 자식 노드의 키보다 작다.
-
4) 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
이진 탐색 트리의 탐색
이진 탐색 트리의 탐색은 세 가지 과정으로 이루어진다.
-
현재 노드의 값과 내가 원하는 값을 비교한다. 일치하면 종료된다.
-
현재 노드의 값이 내가 원하는 값보다 크다면 왼쪽 노드로 이동한다.
-
현재 노드의 값이 내가 원하는 값보다 작다면 오른쪽 노드로 이동한다.
위 세가지 과정을 반복하면 이진 탐색 트리에서 원하는 값을 찾을 수 있다. 이러한 탐색은 최대 트리의 높이만큼 이뤄진다.
이진 탐색 트리의 추가
이진 탐색 트리의 추가도 탐색과 유사한 과정으로 진행된다.
-
현재 노드가 비어있으면 그곳에 노드를 추가한다.
-
비어있지 않다면 값을 비교하여 추가하려는 값보다 현재 값이 작다면 오른쪽 노드로 이동한다.
-
반대로 추가하려는 값보다 현재 값이 크다면 왼쪽으로 이동한다.
이진 탐색 트리의 삭제
이진 탐색 트리의 삭제도 세 가지 과정으로 이루어진다.
-
삭제 할 노드가 리프 노드인 경우
- 부모 노드를 찾아서 그 노드와의 연결을 끊는다.
-
삭제 할 노드가 자식이 한 개인 경우
- 부모 노드를 찾아서 삭제할 노드의 자식과 연결해준다.
-
삭제 할 노드가 자식이 두 개인 경우
- 삭제 할 노드를 제외한 가장 작은 값을 가진 노드를 찾는다. (삭제 할 노드의 오른쪽 자식 노드에서 좌측 최하단 노드임.)
- 찾은 최소값 노드에 삭제할 노드의 자식들을 연결해준다.
- 원래 최소값 노드의 부모 노드를 찾아서 최소값 노드와의 연결을 끊어준다.
