[자바] 이진 탐색 트리 (Binary Search Tree)

 

이진 탐색 트리 구조

규칙

1. 왼쪽 자식 노드의 키는 부모 노드의 키보다 작아야 한다.
2. 오른쪽 자식 노드의 키는 부모 노드의 키보다 커야 한다.
3. 중복된 키는 허용되지 않는다. (노드 추가 과정에서 중복 키 발견 시 탐색이 종료된다.)
4. 서브트리도 모두 1, 2, 3번 규칙을 만족한다

 

특징

1. 중위순회로 순회하면 오름차순 정렬된다. (1, 10, 15, 20, 25, 30)
2. 자식 노드를 찾을 때 현재 노드와 값의 크기를 비교하여 기본 이진트리보다 빠르게 탐색할 수 있다.
단, 왼쪽과 오른쪽 노드간 death 크기가 균형을 이루어야한다. (균형상태: O(logN) / 불균형상태: O(N))
3. 찾는 데이터가 없으면 null을 반환한다.

(이진트리 순회 종류: https://imcoding.tistory.com/3)

 

 

 

노드삭제

삭제 대상 노드가 자식노드가 없는 Leaf노드인 경우이다.
Root 노드부터 차례로 탐색하여 찾고자 하는 값을 찾아서 null 값으로 바꾸기만 하면 된다.

 

 

 

삭제 대상이 자식노드 하나를 갖고 있는 경우이다.
삭제 대상의 자식노드를 자신의 부모노드와 연결해줘야한다.

 

 

 

삭제대상의 자식노드가 둘인 경우이다. 이진 탐색 트리의 성질을 유지하면서 해당 노드를 삭제하는 방법은 아래 두가지 중 하나를 고르면 된다.
1. 삭제 대상 노드의 왼쪽 서브트리에서 가장 큰 노드를 선택하고 삭제한 노드의 위치로 옮긴다. 이 경우에 다른 자식 노드의 링크도 옮긴 노드에 연결 해주어야한다.
2. 삭제 대상 노드의 오른쪽 서브트리에서 가장 작은 노드를 선택하고 삭제한 노드의 위치로 옮긴다. 1번과 동일하게 자식 노드의 링크를  옮긴 노드에 연결 해주어야한다.