5.Binary Search Tree에 대해서 알아보자.
09 Sep 2016자료구조 이진탐색트리와 그 표현에 대해서 알아보자.
이전 포스팅에서 트리에 대해서 알아보았다. 이번에 알아볼 이진탐색트리의 정의는 다음과 같다.
정의
- Binary Tree
- Node의 key값은 왼쪽 subtree 보다 크고 오른쪽 subtree보다 작다.
이진 탐색 트리는 트리 의 한 종류이며 tree의 정의를 만족해야한다. Binary Tree 즉, 이진 트리라 함은 한 부모가 최대 두개의 자식을 가질 수 있음을 의미한다.
위 정의를 바탕으로 이진 탐색 트리는 다음과 같은 성질을 갖는다.
- 모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다.(모든 노드의 키값은 다르다.)
- 왼쪽 서브트리의 있는 키가 존재한다면, 키들은 그 루트의 키보다 작다.
- 오른쪽 서브트리의 있는 키가 존재한다면, 키들은 그 루트의 키보다 크다.
- 왼쪽 서브트리와 오른쪽 서브트리 모두 이진탐색트리이다.
탐색
root에서 시작
key값과 비교
반복 {
찾으려는 값보다 작으면 왼쪽 child로 이동
크면 오른쪽 child로 이동
같으면 성공
}
만약 leaf까지 도달 할 때까지 찾지 못하면 실패
이진탐색트리에서 탐색 연산의 시간복잡도는 O(h)이다. logN 이 아닌 트리의 높이임을 주의하자.
삽입
이진트리의 데이터 삽입은 search연산과 같이 이루어진다.
search 실패시
그자리에 node 생성
따라서 삽입의 시간복잡도는 O(h) + O(1)이 된다.
삭제
시간복잡도 O(h)
만약 중간 노드가 삭제되면 어떻게 할까? 노드의 삭제가 이루어져도 트리의 정의를 항상 만족해야한다. 따라서 다음과 같은 연산을 해야한다.
- 삭제된 노드의 왼쪽 서브트리로 내려간다.
- 서브트리의 오른쪽 서브트리로 계속 내려간다.
- 오른쪽 서브트리가 없을경우 현재 노드를 삭제된 노드로 이동한다.
- 삭제된 노드의 왼쪽 서브트리는 삭제된 노드의 부모의 오른쪽 서브트리로 이동한다.
이렇게 하면 중간의 노드가 삭제되어도 이진탐색트리의 정의를 계속 유지할 수 있다. 1, 2단계에서 왼쪽으로 한번 내려가고 오른쪽으로 계속 내려가는 이유는 삭제된 노드보다 작은것 중에 가장 큰 노드를 찾기 위함이다.
만약 삭제된 노드의 왼쪽 자식이 없다면 해당 노드보다 작은 key값을 갖는 노드가 없으므로 큰 것중에 가장 key값이 가장 작은 노드 를 찾아 이동하면 된다.
구현
이진 탐색트리의 구현은 여러가지 방법으로 할 수 있다. LinkedList, 인접리스트, 인접행렬, 해쉬테이블 등등으로 구현할 수 있다. 가장 간단한 방법은 배열로 구현한는 방법이다.
문제점
데이터의 크기 순서대로 삽입연산을 수행하면 linked-List가 되어버린다. 따라서 탐색시간이 logN이라는 시간이 보장되지 않고 트리의 높이만큼의 시간이 보장된다.