이진 탐색 트리

• 탐색 작업을 효율적으로 하기 위한 자료구조
• 모든 원소는 서로 다른 유일한 키를 갖는다.
• key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)
• 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리다.
• 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

-이진 탐색 트리-

이진 탐색 트리 - 연산

탐색 연산

• 루트에서 시작한다.
• 탐색할 키 값 x를 루트 노드의 키 값과 비교한다.(키 값 x = 루트 노드의 키 값) : 원하는 원소를 찾았으므로 탐색연산 성공(키 값 x < 루트 노드의 키 값) : 루트 노드의 왼쪽 서브트리에 대해서 탐색연산 수행(키 값 x > 루트 노드의 키 값) : 루트 노드의 오른쪽 서브트리에 대해서 탐색연산 수행
• 서브트리에 대해서 순환적으로 탐색 연산을 반복한다.

-트리에서 13을 탐색하는 과정-

삽입 연산

• 먼저 탐색 연산을 수행삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인한다.탐색에서 탐색 실패가 결정되면 위치가 삽입 위치가 된다.
• 탐색 실패한 위치에 원소를 삽입한다.

-5를 트리에 삽입하는 과정-