이진탐색트리

 

이진트리 - 가장 많이 사용되는 데이터 구조, 각 부모노드가 항상 최대 2개의 자식노드와 붙어 있음

이진 탐색 트리 : 이진 트리의 가장 일반적인 유형, 노드의 key 기준으로 정렬한 상태

- 정렬 기준

 

1. 노드의 왼쪽 서브트리에는 노드의 키보다 작은 키를 가진 노드만!
2. 노드의 오른쪽 서브트리는 노드의 키보다 큰 키를 가진 노드만!
3. 좌우 서브 트리도 각각 이진 탐색 트리

4. 각 노드에 중복 키(key)는 없음!

 

그래서..

가장 큰 키를 가진 노드는 가장 오른쪽 서브트리 말단(80)

가장 작은 키를 가진 노드는 가장 왼쪽 서브트리 말단(1)

 

이진탐색트리로 할 수 있는 동작은

1. 트리에 노드 추가

2. 노드 삭제

3. 노트 선택해 탐색하는 키가 존재하는지 확인