이진 탐색 트리

이진 탐색 트리 (Binary Search Tree)

특징

• 이진 탐색 트리에서 부모 노드는 왼쪽 자식 노드보다는 크고 오른쪽 자식 노드보다는 작다

  값의 크기 비교 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

• 탐색 속도를 극대화할 수 있는 구조이다.
• 한 번 확인할 때 마다 탐색할 노드의 개수가 절반씩 줄어든다.
• 완전 이진 탐색 트리에서 실행할 경우 O(logN)의 시간복잡도를 가진다.

탐색

• 트리 내의 데이터를 탐색한다.
• 탐색하고 싶은 노드를 부모 노드와 비교한다.

  부모 노드보다 클 경우

  • 오른쪽 자식 노드에 포함되므로 오른쪽으로 이동한다.

부모 노드보다 작을 경우

• 왼쪽 자식 노드에 포함되므로 왼쪽으로 이동한다.

삽입

• 삽입하고 싶은 데이터를 부모 노드와 비교하여 탐색 프로세스와 같이 이동하며 적절한 위치에 값을 삽입한다.

삭제

1. 자식 노드가 없는 노드의 삭제

• 데이터를 탐색하여 삭제한다.

2. 1개의 자식 노드가 있는 노드의 삭제

• 삭제할 노드의 자리에 자식 노드를 삽입한다.

3. 2개의 자식 노드가 있는 노드의 삭제

• 삭제할 노드 다음으로 큰 노드를 삭제할 노드의 위치에 삽입한다.