Facebook Joinc 그룹
Joinc QA 사이트
Tweet
joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다.
Tweet
joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다.
1 Tree에 대한 정의
- tree는 0개 이상의 node의 집합이다.
- 노드의 수가 0개이면, tree는 비어있다(empty)라고 한다.
- 노드의 수가 1개 이상이면, 최상위(root)노드가 존재한다. 나머지 노드는 subtree라 한다.
- subtree의 루트는 전체 트리의 루트와 edge로 연결된다.
1.1 용어 정리
- T1, T2, ..., T3는 root인 r의 자식(child)라고 한다. r은 T1, T2,..의 부모(parent)가 된다. T1, T2는 서로의 sibling 라고 한다.
- node가 가지는 자식의 수를 단계(degree)라고 한다.
- degree가 0인 node를 잎(leaf)라고 한다.
- n1, n2, ..., nk인 일련의 노드들이 있고, ni가 ni+1의 부모노드일경우 이것을 path라고 한다.
- n1으로 부터 n2까지의 path가 존재하면 n1을 ancestor, n2를 decendent이라고 한다.
- 가장 긴 path의 길이를 트리의 높이(height)라고 한다.
1.2 구성
가장 간단하면서도 일반적인 구성은 모든 node가 child와 next sibling를 가리키는 2개의 포인터를 가지는 구성이다.
2 Binary Tree
모든 노드가 2개 이하의 자식을 가질 때, 이를 Binary(2진) tree라고 한다. 2진트리는 구성의 간단함으로 자료구조에서 가장 널리 사용되어진다. 다음과 같은 2진 트리의 응용이 있다.
- binary search tree: 모든 노드에서 left child < parent < light child를 만족하는 트리를 말한다. 가장 널리 사용되는 응용이다.
- expansion tree : 컴파일러가 표현을 해석하기 위해서 생성하는 tree다. 다음은 일반수식을 해석하기 위해서 생성된 expansion tree의 예이다.
2.1 탐색
데이터를 가져오기 위해서는 트리를 탐색해야만 한다. 탐색의 위치와 순서에 따라서 다양한 탐색방법이 존재한다.
- 깊이 우선 탐색(preorder) : left child->parent->right child 순으로 방문한다. 위의 binary tree의 경우 ++a*bc*+*defg 가 된다.
- 넓이 우선 탐색 (postorder) : left child->right child->parent child 순으로 방문한다. stack machine을 위한 compiler에서 code 생성을 위해서 사용한다.
- inorder: parent->left child->right child 순으로 방문한다. 일반적으로 수식을 표현하기 위해서 많이 사용한다. 위의 이진 트리의 경우 b*c+a+d*e+f*g 가된다.
3 Binary Search Tree
모든 노드에서 left child < parent < right child를 만족하는 이진 트리를 말한다. 이렇게 구성된 트리에서 특정 값을 찾고자 할경우 아래의 함수로 표현할 수 있을 것이다.
3.1 Search
search(x, T)
{
if (T==null)
return null;
else if(x<T.element)
return search(x,T.left);
else if (x>T.element)
return search(x,T.right);
else return T;
}
위의 함수에서 실행시간은 depth에 의해서 좌우된다.
linear tree일 경우 최악이 되며 O(n)시간이 소모된다. 완전 이진 트리인 경우 최상이 되면 O(longn)이 소모된다.
평균소모시간은 n개의 자료에 대해서 n!개의 가낭흔 insertion order에 대해서 고려를 해야 한다.
- Internal Path Length D(n)을 tree에 있는 모든 노드들의 깊이의 합으로 정의한다. D(0)=D(1)=0 이다.
- D(i)와 D(n-i-1)을 left와 right subtree의 Internal Path Length라고 하면, D(n) = D(i)+D(n-i-1)+(n-1)이다.
- D(i)와 D(n-i-1)의 평균값이다. 그러므로 아래의 공식이 성립한다.
- 이제 D(n)<4nlogn을 쉽게 정할 수 있을 것이다.
증명을 보다 쉽게 정리해 보았다.
- 자식 tree의 크기가 Best인 경우 n/2와 n/2로 나누어지고 worst인 경우 0과 n-1로 나누어짐진다.
- 그러므로 평균적으로 n/4와 3n/4로 나누어진다고 가정할 수 있다.
- 이중 가장 깊은 것(height가 가증큰)은 3n/4인 서브트리이므로
- H(1) = 0, H(n)=1+H(3n/4) 이다.
- 해서 H(n) = 2.4logn = O(long)을 유도할 수 있다.
3.2 Insert
다음과 같은 프로시져코드로 정의할 수 있다.
Insert(x,T)
{
if(T==null)
{
new T;
T.element = x;
T.left = t.right = null;
else if (x<T.element) T.left = insert(x,T.left);
else if (X>T.element) T.right = insert(x,T.right);
else "이미 존재";
return T;
}
}
위의 과정을 그림으로 나타내보았다.3.3 Delete
다음과 같은 프로시져코드로 정의할 수 있다.
delete(x,T)
{
if(T == NULL) "Error";
if (x<T.element) T.left = delete(X,T.left);
else if (X>T.element) T.right = delete(X,T.left);
// 2 child
else if (T.left && T.right)
{
// find min
repl = T;
while(repl.eft != null) repl = repl.left;
T.element = repl.element;
T.right = delete(T.element, T.right);
}
// 1 child
else
{
tmp = T;
if (T.left == null) repl = T.right;
if (T.right == null) repl = T.left;
free (tmp);
return repl;
}
}
4 AVL 트리
Binary 트리의 최대 단점은 노드의 깊이가 불균형해질 수 있다는 점이다. 이는 최악의 경우 O(n)의 시간이 소비될 수 있음을 의미한다. 그래서 트리의 균형을 맞추고자하는 시도를 하게되었으며, AVL은 최초로 고안해낸 균형(balance) 트리다.
AVL은 왼쪽과 오른쪽의 subtree의 높이가 1이상 차이나지 않으며 1962년 Adelson,velskii, Landis에 의해서 만들어 졌다.
AVL의 아이디어는 O(long)의 연산만으로 tree의 균형을 맞추는데 있다.
4.1 AVL의 height는 항상 O(logn)을 유지한다.
- N(h)를 높이가 h인 AVL에 존재할 수 있는 최소 노드의 갯수라고 정의하면
- N(0) = 1, N(1) = 2 이다.
- N(h) = N(h-1)+N(h-2)+1 이므로 아래의 공식이 성립된다.
- 그러므로 h=log_1.618^n=O(logn) 이 된다.
4.2 Rotate
4.3 회전(Rotate)
AVL 트리의 핵심은 결국 트리의 균형을 맞추는 것이라 할 수 있다. 일반적으로 트리의 균형은 트리에 새로운 node가 추가될 때 발생을 한다. 이러한 균형의 문제를 해결하기 위해서 Rotate를 이용한다.
다음은 Single rotation의 예이다.
Upload new Attachment "tree9.png"
다음은 double rotation의 예이다.
Upload new Attachment "tree10.png"
다음은 각각의 rotate를 프로시져 코드화 한 것이다.
single_rotate_left(n2)
{
n1 = n2.left
n2.left = n1.right;
n1.right = n2;
n2.height = max(n2.left.height, n2.right.height)+1;
n1.height = max(n1.left.height, n1.right.height)+1;
return n1;
}
docuble_rotate_left(n3)
{
n1 = n3.left
n3.left = single_roate_right(n3.right);
return single_roate_left(n3);
}
4.4 Insertion
삽입은 바이너리 트리와 기본적으로 같다. 그러나 삽입이 일어날 경우 균형이 깨질수 가 있는데, 이경우 roate를 해야 한다.
insert(x,T)
{
if(T == NULL) new T;
else if(x<T.element)
{
T.left = insert(x, T.left);
if((T.left.height - T.right.height) == 2)
{
if (x<t.left.element)
T=single_roate_left(T);
else
T=double_roate_left(T);
}
else
T.height = max(T.left.height, T.right.height)+1;
}
else if (x>T.element)
{
// 위코드와 동일
}
else "Error";
return T;
}