이진탐색트리(Binary Search Tree)(임시)

이진탐색트리(Binary Search Tree)

효율적인 탐색을 위한 이진트리 기반의 자료구조이다.

 

이진탐색트리의 특징

 - 모든 트리는 유일한 키를 갖는다.

 - 왼쪽 서브 트리 키들은 루트 키보다 작다.

 - 오른쪽 서브 트리의 키들은 루트의 키보다 크다.

 - 왼쪽과 오른쪽 서브 트리도 이진탐색트리이다.

 

---

이진탐색트리의 추상자료형

 

연산

init(): 초기화

insert(): 새로운 원소 추가

delete(): 기존 원소 삭제

search(): 탐색

---

이진탐색트리의 연산

 

이진탐색트리의 탐색

키 값으로 key를 가지는 노드를 탐색하려 할 때 key와 루트 노드의 키값을 비교하며 결과는 아래 세 가지 중 하나다.

key가 루트 노드의 키값과 같으면 루트 노드가 찾는 노드이므로 탐색은 성공으로 끝난다.

key가 루트 노드의 키값보다 작으면 찾는 노드는 왼쪽 서브트리에 있으므로 루트의 왼쪽 자식을 기준으로 탐색을 다시 수행한다.

key가 루트 노드의 키값보다 크면 찾는 노드는 오른쪽 서브트리에 있으므로 루트의 오른쪽 자식을 기준으로 탐색을 다시 수행한다.

 

 

이진탐색트리의 삽입

이진탐색트리에서는 같은 키 값을 갖는 노드가 없어야하고 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치가 되기 때문에 먼저 탐색을 수행해야한다. 

이진탐색트리의 삭제