[자료구조] 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리

- 탐색에 유용하게 설계된 이진 트리를 말한다.

- 이진 트리

   : 자식 노드가 두개인 트리

- 설계 규칙

  1. 각 노드는 서로 다른 키를 가진다.

  2. 각 노드는 최대 2개의 자식 노드를 가진다(최대 두개 분기)

  3. 각 노드의 key는

     - left subtree의 모든 노드의 key보다 크고

     - right subtree의 모든 노드의 key보다 작다.

 

검색

search(r, x)
	if(r == null || r.item == x)
    		return r
	else if(r.item < x)
    		return search(r.left, x)
	else
    		return search(r.right, x)

- 시간복잡도 평균 theta(logn), 최악 theta(n)

 

삽입

insert(r, x)
//r : 서브트리의 루트, x : 삽입하려는 key
//x가 트리 내에 없을 때
	if(r==null)
    	r의 부모 아래 x 삽입
    else if(x < r.key)
    	insert(r.left, x)
	else
    	insert(r.right, x)

- 시간복잡도 평균 theta(logn), 최악 theta(n)

 

 

삭제

remove(x)
	node r = search(root, x)
	if(r이 리프 노드)
		r을 삭제(r의 부모가 null가리키게)
	else if(r의 자식이 하나)
		r의 부모가 r의 자식을 가리키게
	else
		r의 right subtree의 left-most(minimum) 원소 s find
		s를 r자리에 복사
		remove(s)

- 시간복잡도 평균 theta(logn), 최악 theta(n)

 

 

 

장단점

1) 장점

 - 배열과 비교했을 때 검색/삽입/삭제가 효율적이기 때문에 검색/삽입/삭제가 많이 일어나는 탐색작업에서 유용하다.

 

2) 단점

 - naive한 구현에서 skewed tree, 즉 worst case가 발생가능하다.

 

*Binary Tree에 관련된 Theorems

1. 이진 탐색 트리를 대상으로 inorder traversal을 하면 key가 정렬된 순서로 방문하게 된다.

    : 그래서 한번 inorder traversal한 다음 가운데 것을 root key로 잡으면 balanced가 된다.

2. 높이 h의 완전 이진 트리는 2^h-1개의 노드를 가진다.

3. n개 노드를 가진 이진 트리의 최소 높이는 ceil[log(n+1)]이다.

4. n개 노드를 가진 이진 트리의 IPL은 O(nlogn)이다.

    : IPL - Internal Path Length, 각 노드를 방문하는데 걸리는 비교 횟수의 합