이진 탐색 트리

왼쪽 자식 노드의 키는 부모 노드의 키보다 작음

오른쪽 자식 노드의 키는 부모 노드의 키보다 큼

각각의 서브 트리도 이진 탐색 트리를 유지

중복된 키를 허용하지 않음

이진 탐색 트리의 특징

이진 탐색 트리 규칙에 의해 데이터가 정렬됨

이진 트리에 비해 탐색 빠름 (균형 유지 필요)

-균형 상태 : O (log N)

-불균형 상태 : O (N)

이진 탐색 트리 -탐색

찾고자 하는 데이터를 루트 노드부터 비교 시작

대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동

찾는 데이터가 없으면 null을 반환

어떤 데이터를 찾더라도  최대 트리 높이만큼의 탐색이 이루어짐 

이진 탐색 트리 - 삽입

Root 부터 비교 시작(중복 키 발견 시 노드 추가하지 않고 종료)

삽입할 키가 현재 노드의 키보다 작으면 왼쪽으로 이동

삽입할 키가 현재 노드의 키가 크면 오른쪽으로 이동 

Leaf 노드에 도달 후 키 비교하여 작으면 왼쪽, 크면 오른쪽에 삽입

이진 탐색 트리 - 삭제(1)

 삭제 대상 노드가 Leaf노드인 경우

삭제 대상 노드 삭제

부모 노드의 해당 자식 링크 null로 변경 

삭제 대상 노드에 자식 노드가 둘인 경우 

1. 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드 선택 

2. 삭제 대상 노드의 오른쪽 서브트리에서 가장 작은 노드 선택 

1또는 2 에서 선택한 노드를 삭제 대상ㅇ 노드 위치로 올림 

위로 올리는 과정에서 다른 자식 노드들의 링크 연결 작업 진행

삭제 대상 노드 삭제