이진 탐색 트리(BST) 연습문제 풀이

이진 탐색 트리(BST)

[ Introduction to Algorithm Chap 12 연습문제 풀이 ]

Section 1)

12.1-1) 이진 검색 트리 조건을 만족하도록 아무거나 만들면 된다.

12.1-2) 이진 탐색 트리는 현재 노드에 대해 왼쪽 서브 트리보단 크거나 같고, 오른쪽 서브 트리보단 작거나 같다는 것으 보장하지만, 최소힙은 모든 자식 중에서 가장 작은 값만을 보장한다(왼쪽 오른쪽 구분이 없다). 따라서 정렬된 데이터를 얻고 싶을 경우, 최소힙은 선형 시간을 가진다고 보장할 수 없다.

12.1-3) [ TODO ]

12.1-4)

PREORDER-TREE-WALK(x)
	if x != NIL
		print(x)
		PREORDER-TREE-WALK(x.left)
		PREORDER-TREE-WALK(x.right)


POSTORDER-TREE-WALK(x)
	if x != NIL
		PREORDER-TREE-WALK(x.left)
		PREORDER-TREE-WALK(x.right)
		print(x)

12.1-5) BST를 구성하기 위해 최악의 경우 O(n lg n)이 걸린다고 가정해보자. 정렬된 데이터를 얻기 위해선 BST를 중위 순회한다. 세타(n)이 걸리기 때문에 이는 곧 제한 O(n lg n)을 초과하지 않고 정렬된 데이터를 얻을 수 있음을 알 수 있다.

Section 2)

12.2-1) c, e

12.2-2) [TODO]

12.2-3)

TREE-PREDECESSOR
if x.left != NIL
	return TREE-MAXIMUM(x.left)
y = x.p
while y != NIL and y.left == x
	x = y
	y = y.p
return y

12.2-4)

TREE-MINIMUM(x)
	if x.left != NIL
		return TREE-MINIMUM(x.left)
	else
		return x;

TREE-MAXIMUM(x)
	if x.right != NIL
		return TREE-MAXIMUM(x.right)
	else
		return x;

12.2-5) 특정 노드 x에 두 자식이 있다면 직후 원소는 오른쪽 서브 트리 안에 있다. 다라서 TREE-MINIMUM(x.right)를 호출함으로써 찾을 수 있는데, 이 것이 순회 노드 값이 NIL이 될 때까지 왼쪽 자식만을 따라간다. 따라서 찾은 노드가 왼쪽 자식이 NIL이 아니라면 이는 직후 원소를 찾은 것이 아니므로 모순이기에 왼쪽 자식이 없을 수 밖에 없다. 직전원소도 같은 방식으로 증명이 가능하다.

12.2-6) y가 x의 직후 원소에 대해 생각해보자. x의 직후 원소가 되는 후보는 x의 조상이어야만 한다. 만약 조상이 아니라 다른 서브 트리에 있다고 가정해보자. 그러면 z=LCA(x, y)라고 할 때, 이진 검색 트리 특성에 의해 x < z < y의 특징을 가지게 된다. 이는 y가 아예 후보가 될 수 없음을 나타낸다. 또 조상 중에 x를 포함하는 서브트리를 오른쪽 자식으로 두는 경우에는 y < x이므로 이 역시 후보에서 제외한다.

이제 남은 경우는 x의 조상이면서 x를 포함한 서브트리를 왼쪽 자식으로 두는 경우인데, depth(y1) < depth(y2)인 y의 후보 y1, y2를 생각해보자. 이진 트리 특성에 의해 x < y1 < y2 이므로 y은 x의 조상이면서 x를 포함하는 서브트리를 왼쪽 자식으로 두는 노드 중에 가장 depth가 높은, 가장 x와 가까운 노드로 결론이 난다.

12.2-7) 특정 노드 x를 출력하기 위해서 먼저 선행되어야 할 작업을 생각해보자. 바로 x.key보다 작거나 같은 왼쪽 서브 트리를 모두 출력하는 것이다. 그렇다면 x의 왼쪽 서브 트리의 최소값 부터 순회를 돌며 x의 직전 원소까지 x로 돌아오지 않는다. 이를 자세히 관찰해보면 x로부터 왼쪽 서브트리로 간선을 한 번, 또 순회를 끝내고 x로 돌아올 때 간선을 타고 오기 때문에 모든 간선을 단 두 번만 사용함을 알 수 있다. 트리는 n-1개의 간선을 가지므로 시간 복잡도는 세타(n)임을 알 수 있다.

12.2-8) 실제 방문하는 노드는 부모로 부터, 왼쪽 자식, 오른쪽 자식으로 간선을 타기 때문에 최대 3k번 방문한다.

y를 x로부터 k번째 직후원소라고 할 때, x.key와 y.key 사이값을 가지지 않는 노드에 대해서 생각해보자. z = LCA(x, y)라고 할 때, x~z와 y~z에 해당하지 않는 노드가 최악의 경우 h개의 노드가 있을 수 있다.

[그림]

∴ 3k + 2h => O(k+h)

12.2-9) 

1. x.key < y.key

  1. x를 포함하는 서브트리를 왼쪽 자식으로 갖는 노드의 집합 A의 원소는 모두 x.key보다 크다.

  2. 최상위 루트는 x를 포함하므로 루트 오른쪽 서브트리는 모두 x.key보다 크다. 하지만 오른쪽 서브트리의 노드들은 루트의 키보다 크므로 x.key보다 크긴하지만 가장 작은 값이 존재할 수 없다.

  따라서 1.과 루트 관계에서 루트의 왼쪽 서브트리는 작은값을 가지기 때문에 귀납적으로 y.key가 x.key보다 큰 값중 가장 작은 값이 된다.

2. x.key > y.key

  비슷한 방법으로 증명이 가능하다.

Section 3)

12.3-1)

TREE-INSERT-REC(y,x,z)
	if x!= NIL
		if(z.key < x.key)
			TREE-INSERT-REC(x, x.left, z)
		else
			TREE-INSERT-REC(x, x.right, z)
	z.p = y
	if y == NIL
		T.root = z
	else if z.key < y.key
		y.left = z
	else
		y.right = z

12.3-2)

1. 삽입하는 노드는 반드시 leaf 노드가 된다.

2. 삽입 과정은 1의 위치를 찾기 위해 자식이 NIL인 경우에 반환한다. 즉, 부모 높이까지만 확인하고 종료한다. 반면 삽입되는 데이터 검색의 경우 노드를 찾거나 NIL일 때까지 검사하므로 삽입된 데이터도 검사하기 때문에 딱 1만큼 차이가 난다.

12.3-3) 삽입은 O(h)가 걸린다. 노드가 n개라고 하면 총 O(nh)가 걸린다. 순회는 세타(n)이 걸리기 때문에 시간은 총 O(nh)가 걸린다.

최악 -> O(n^2), 최적 ->O(n lg n)

12.3-4) y는 두 자식이 있고 왼쪽 자식을 x, 오른쪽 자식을 z라고 하자. x는 자식이 없고, z는 왼쪽 자식이 있는 경우(y의 직후 원소는 z가 아님) x->y 순으로 삭제하려고 한다. 그렇다면 x를 삭제하고 나면 y는 자식이 하나만 남으므로 z가 루트로 올라온다. 반대로 y->x인 경우 y의 직후 원소를 y위치에 두므로 이미 root가 달라지므로 다른 트리가 생성된다.

12.3-5) 굳이 하고싶지 않음..

12.3-6) 단순히 TREE-MAXIMUM(z.left)로 바꾸면 된다. 우선순위는 depth가 더 높은 서브트리를 선택한다.

Section 4)

12.4-1) 

12.4-2) 완전이진트리에서 하나의 leaf 노드에 c(n) 길이를 가지는 chain이 죽 늘어져 있는 트리를 생각해보자. 완전이진트리의 높이 k=log(n - c(n))이 된다.

평균 높이는 다음처럼 계산된다.

c(n)의 상한은   을 이용하여 결정할 수 있으므로 상한은 이 된다.

12.4-3) 전자는 이미 만들어져 있는 상태에서 구성하기 때문에 선택하여 랜덤하게 구성하는 것과 다르다.

12.4-4)

 이므로 x1 < x2에 대해 항상 f'(x1) < f'(x2)를 만족하므로 볼록하다.

12.4-5) [못해먹겟음..]