Trees

오늘은 저녁에 놀아야 되니까, 좀 일찍 정리해보자 ㅋ 


Trees
 트리는 Graph부분에서도 나왔지만 자료구조에서도 매우 중요하게 다뤄지는 중요한 개념이라 그런지
따로 언급된다.

Graph부분에서는 트리는 acyclic connected graph라고 하였다.
또 다른 정의로써, tree는 모든 vertices의 쌍 사이에 유일한 path가 존재하는 ugraph이다.

또한 rooted tree는 지정된 root vertex를 가지고 모든 edge가 root로부터 directed away(?) 되는 트리이다.
directed away는 정확한  해석은 모르겠지만 루트로의 길의 일부분이 된다? 정도로 받아들이면 될 것 같다.
이 부분에서 헷갈려야 하지 말아야 하는 것이 rooted tree와 tree이다. 우리가 일반적으로 tree라고 말하면 rooted tree를 생각하기 쉬운데, 실제로 순수한 tree는 root를 언급조차 하지 않는다. 정하기 나름인 것이다. 
그러므로! tree의 정의를 명확하게 숙지하고 있도록 하자.

트리의 속성으로써 n개의 vertices를 가지는 트리는 e=n-1개의 edge를 가진다.
그리고 기타 속성들이 있지만.. 조금만 생각하면 알 수 있는 것들이므로 패쓰!


Application of Trees
트리의 몇가지 응용에 대해서 나온다. 자료구조에서는 더 다양한 종류에 대해서 나오겠지만
여기에서는 몇가지만 나온다.

첫째로 Binary Search Tree이다.
자신의 value보다 작으면 왼쪽 subtree에, 크면 오른쪽 subtree에 해당 값이 존재하거나 아니면 존재하지 않는다.
탐색할때 average case lg n으로써 좋지만, worst case일때 트리가 한 쪽 방향으로만 자라나는 문제가 있다.
그래서 문제를 해결한 것이 B-tree, AVL tree 등이다. B-tree는 균형이 맞도록 삽입이 일어나며 AVL tree는 balancing factor를 두어서 트리를 회전하는 방식으로 균형을 맞춰 삽입이 일어나도록 한다.
이건 생각나는대로 정리한거라 틀릴수도~

둘째로 Decision tree이다.
decision 과정을 tree의 internal node로 표현하고 leaf에 결정된 action을 표현하는 방식으로 사용하는 tree이며
인공지능의 Inductive learning에서도 사용한다.

셋째로 Prefix code를 표현하는데 트리를 사용한다.
프리픽스 코드는 어떠한 코드가 다른 코드의 prefix로 사용되지 않는것을 의미한다.
예를들어 1111 이라는 코드가 있으면, 1111xxxx... 이런 코드는 존재할 수 없다. 
이것을 이용한 것이 Huffman coding이다. Huffman coding은 Frequency * depth를 최소화 시키도록 하는 압축 알고리즘이다.
따라서 자주 등장하는 코드일 경우 root와 가까운 곳에 해당 코드가 존재하도록 한다.
이것을 표현하는 것이 prefix code이다. 각각의 노드가 0과 1을 나타내게 된다.

또한 마지막으로 절대 잊지 말아야 할 것이 Spanning tree 이다.
spanning tree의 수학적 정의는 어떠한 ugraph의 subgraph이면서 모든 vertex를 포함하는 트리이다.
당연히 tree이니까 tree의 성질에 따라 cycle은 없어야 할 것이고 모든 버텍스가 연결되어 있어야 할 것이다.
그리고 Minimum spanning tree는 각각의 edge가 weight를 가질 때 weight의 합이 최소가 되도록 하는
spanning tree를 말하며 그것을 구하는 알고리즘으로 Prim's algorithm, Kruskal's algorithm이 나온다.

간단히 기억을 되살려 보면
프림의 알고리즘은 인접한 버텍스 중 최소 weight를 가지는 edge로 연결된 버텍스를 추가시켜 나가는 알고리즘이며,
크루스칼 알고리즘은 엣지를 오름차순으로 정렬하고 버텍스들을 최소 엣지순서대로 엣지를 추가해나가며 스패닝 트리를 만드는 알고리즘이다. 이 두 알고리즘을 수행할 때 유의해야 할 것은 트리를 만드는 것이므로 사이클이 생기도록 해서는 안된다.