Search

Tree and Binary tree

트리 tree

[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌 by 권오흠 교수님
•
계층적인 구조를 표현할 때 사용하는 자료구조이다.
•
그래프의 일종이라고 볼 수도 있다. 유입되는 라인이 1개이고, 방향성을 가지지 않는 그래프라고도 말할 수 있다.
•
사용
◦
가계도, 조직도, 디렉토리와 서브디렉토리 구조 등

구조

•
노드, 엣지 (링크, 브랜치라고도 부름)
•
제일 최상단의 노드를 루트 노드라고 부른다.
•
부트리, subtree : 전체 트리의 일부를 자른 트리
•
레벨 : 루트로부터의 거리
•
높이 : 전체 트리의 높이. 서로 다른 레벨의 개수

관계

•
부모 - 자식 : 상대적인 개념. 상하관계
•
형제 : 부모가 같은 노드들
•
리프노드 : 자식이 없는 노드
•
조상 - 자손 : 부모의 부모와의 관계

특징

•
노드의 개수가 n개인 어떤 트리는 반드시 n-1개의 엣지를 갖는다.
◦
노드의 개수가 4개이면, 반드시 3개의 연결선, 엣지를 갖는다.
•
루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일하다. (같은 노드를 두번 이상 방문하지 않는다는 전제 하에!)

종류

•
tree : 계층구조를 갖는 자료구조
•
binary tree : 이진트리. 최대 2개의 자식을 갖는다.
•
binary search tree
◦
이진탐색트리
◦
루트를 기준으로 루트보다 작으면 왼쪽, 크면 오른쪽에 위치한다.
•
complete binary tree
◦
마지막 레벨을 제외하고는 모든 노드가 꽉차있는 트리
◦
꽉 차있지 않은 마지막 레벨에서도 왼쪽부터 오른쪽으로 노드가 쌓여야한다는 특징이 있다.
•
full binary tree
◦
모든 노드가 0개 혹은 2개의 자식노드를 갖는 트리
•
perfect binary tree
◦
모든 노드가 2개의 자식을 갖는 트리
◦
모든 리프(맨 마지막 노드)들이 모두 같은 레벨에 있다.
◦
트리의 높이가 h일 때, 2^h -1 개의 노드를 갖는다.
•
참고
◦

이진트리, binary tree

•
각 노드는 최대 2개의 자식을 갖는다.
•
일반적으로 왼쪽 자식과 오른쪽 자식의 위치가 정해진다.
◦
부모와 자식의 구성이 같아도, 왼쪽 자식과 오른쪽 자식이 서로 다른 경우는 서로 다른 이진 트리로 간주한다.

expression tree

•
수식의 계산을 트리 구조로 표현한 것

huffman code

•
데이터를 압축하거나 인코딩하는 기본적인 알고리즘 중 하나
•
가변 길이를 인코딩할 때, 예를 들면, a부터 z까지의 알파벳으로 구성된 텍스트 파일 인코딩할 때, 해당 파일의 각 알파벳을 적절하게 인코딩 할 때, 파일 길이를 최소로 인코딩하는 곳에 사용된다.
◦
즉, 파일 압축을 최적화하는 곳에 사용된다.
•
위의 그림은 각 알파벳별로 주어진 이진코드로 압축하는 과정

full and complete binary tree

•
perfect binary tree : 모든 레벨에서 노드가 꽉꽉 차있는 트리
◦
높이가 h인 perfect binary tree 는 2^h-1개의 노드를 가진다.
•
full binary tree : 자식을 2개만 갖거나 아예 갖지 않는 트리
•
complete binary tree : 마지막 레벨을 제외하고는 노드가 가득 차있어야 하며, 비어있는 노드는 오른쪽에서부터 연속된 몇개의 노드만 해당된다.
◦
힙은 기본적으로 complete binary tree 여야 한다.
•
노드가 N개인 full or complete 이진 트리의 높이는 O(logN) 이 된다.
•
일반적인 이진트리는 높이가 최악의 경우 N이 될 수 있다.

이진 트리의 표현

•
연결구조 (연결리스트)로 표현한다.
•
각 노드에 현재 자신의 데이터 필드 + 왼쪽 자식노드 + 오른쪽 자식 노드 + 부모노드의 주소를 저장한다.
◦
하지만 부모노드의 경우는 반드시 필요한 경우가 아니면 보통은 저장하지 않는다.
◦
트리는 보통 위에서부터 아래로 내려가는 구조로 탐색하기 때문에 부모 주소가 크게 필요하지 않기 때문인데, 만약 부모의 주소를 기억하는 것이 중요한 경우라면, 이런 방식으로 저장하는 것이 꼭 필요하다고 할 수 있다.
•
첫번째 노드, 즉 루트 노드의 주소는 따로 보관한다.

이진 트리의 순회 (traversal)

•
순회 : 이진 트리의 모든 노드를 방문하는 일
•
중순위 순회, inorder : 왼쪽 -> 루트 -> 오른쪽
•
선순위 순회, preorder : 루트 -> 왼쪽 -> 오른쪽
•
후순위 순회, postorder: 왼쪽 -> 오른쪽 -> 루트
•
레벨 오더 순회, level-order : (루트가 존재하는) 1레벨 -> 2레벨 -> 3레벨 …

중순위 순회 in-order traversal

이진 트리를 루트 노드 r, 루트의 왼쪽 부트리인 T(L), 오른쪽 부트리인 T(R) 로 나누어서 생각한다.
1.
먼저 왼쪽 부트리를 inorder로 순회하고
2.
r을 순회하고
3.
T(R) 을 inorder 로 순회한다.
기본적으로 recursive 하다.
•
방문 순서는 : 2 -> 3 -> 5 -> 5 -> 7 -> 8
•
2 -> 3 -> 5 -> 5-> 7 -> 8
•
x의 왼쪽을 재귀함수로 호출하고, 현재의 노드 x를 출력한 뒤, 노드 x의 오른쪽 서브트리를 재귀로 다시 호출한다.

선순위순회 pre order와 후순위 순회 post order

•
pre order : 먼저 루트 방문 -> 왼쪽 서브 트리 -> 오른쪽 서브트리
◦
위의 예에서 보면, 5 -> 3 -> 2 -> 5 -> 7 -> 8
•
post order : 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트 방문
◦
위의 예시에서 보면, 2 -> 5 -> 3 -> 8 -> 7 -> 5

expression tree 의 순회

•
inorder 순회하면 아래와 같이 출력된다.
◦
x + y * a + b / c
◦
하지만 이렇게 출력될 경우, 곱셈이 먼저 실행되므로 의도했던 식과 달라지게 된다.
•
해결 - 각 부트리를 순회할 때, 시작과 종료 시점에 괄호를 추가하면 다음과 같이 출력될 수 있다.
◦
(x+y) * ((a + b)/c)
•
postorder 순회하면 후위 표기식이 출력 된다.
◦
x y + a b + b / *

level-order 순회

•
이진 트리를 레벨 순서로 방문하는 전략을 말한다.
•
동일 레벨에서는 왼쪽에서 오른쪽 순서로 방문하며,
•
큐를 이용하여 구현한다.
•
방문 순서는 아래와 같다.
◦
루트 노드이자 시작점인 3을 큐에 넣는다.
▪
큐 : 3
◦
큐에서 요소를 뽑는다. 제일 첫 요소인 3의 자식 노드를 다시 큐에 넣는다.
▪
방문 : 3
▪
큐 : 1, 5
◦
큐에서 1을 뽑고, 다시 1의 자식노드인 0과 2를 큐에 넣는다.
▪
방문 : 3, 1
▪
큐 : 5, 0, 2
◦
큐가 empty 가 될 때까지 위의 과정을 반복한다.
▪
방문 : 3, 1, 5, 0, 2, 4, 6, 7, 8