이진 탐색 트리

이진 탐색 트리란

노드의 왼쪽에는 현 노드보다 작은 값, 오른쪽에는 큰 값이 저장되어 있는 자료 구조

이진 탐색 트리 조건

1. 왼쪽에는 작은 값

2. 오른쪽에는 큰 값

3. 공집합도 포함

 

삽입

위의 과정으로 위치를 찾아 삽입

 

삭제

1. 단말 노드일 경우 - 노드 삽입

2. 하나의 자식이 있는 경우, 본인 노드 지우고 자식을 자신의 자리에

3. 노드가 2개 있는 경우 - 오른쪽 서브 트리 중 가장 작은 값을 삽입

 

시간 복잡도

평균 O(logn)

최악의 경우 한쪽으로 치우친 트리일 경우 O(n)