이진 탐색 트리
•
탐색 작업을 효율적으로 하기 위한 자료구조
•
모든 원소는 서로 다른 유일한 키를 갖는다.
•
key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)
•
왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리다.
•
중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있다.
-이진 탐색 트리-
이진 탐색 트리 - 연산
탐색 연산
•
루트에서 시작한다.
•
탐색할 키 값 x를 루트 노드의 키 값과 비교한다.(키 값 x = 루트 노드의 키 값) : 원하는 원소를 찾았으므로 탐색연산 성공(키 값 x < 루트 노드의 키 값) : 루트 노드의 왼쪽 서브트리에 대해서 탐색연산 수행(키 값 x > 루트 노드의 키 값) : 루트 노드의 오른쪽 서브트리에 대해서 탐색연산 수행
•
서브트리에 대해서 순환적으로 탐색 연산을 반복한다.
-트리에서 13을 탐색하는 과정-
삽입 연산
•
먼저 탐색 연산을 수행삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인한다.탐색에서 탐색 실패가 결정되면 위치가 삽입 위치가 된다.
•
탐색 실패한 위치에 원소를 삽입한다.
-5를 트리에 삽입하는 과정-
