[뇌를 자극하는 알고리즘] 4.트리

1.트리 기초 다지기

트리(Tree): 나무를 닮은 자료구조.(뿌리, 가지, 잎) 

운영체제의 파일 시스템, 검색 엔진이나 데이터 베이스, DOM도 트리 자료구조에 기반해서 구현됨.

 

[트리의 구성요소] 실제로는 똑같은 노드, 트리 내의 위치에 따라 명칭만 다름.

-뿌리(Root): 가장 위의 노드

-가지(Branch): 루트와 잎 사이의 모든 노드

-잎(Leaf): 가지의 끝의 노드. 단말(Terminal)노드 라고도 부름.

[트리 구성요소의 관계]

-부모(Parent): B는 C,D의 부모

-자식(Children): C,D는 B의 자식

-형제(Sibling): C,D는 형제

경로(Path): 한 노드에서부터 다른 한 노드까지 이르는 길 사이에 놓여있는 노드들의 순서.   B,D,F를 B에서 F까지의 경로라함.

길이(Length): 출발 노드에서 목적지 노드까지 거쳐야 하는 노드의 개수.   B,D,F경로 길이는 2

깊이(Depth): 루트 노드에서 해당 노드까지의 경로의 길이. 루트의 깊이는 0.  G는 1, K깊이는 3.

레벨(Level): 깊이가 같은 노드의 집합. 레벨2=C,D,H,J

높이(Height): 가장 깊은 곳에 있는 잎 노드까지의 깊이. 레벨3이 가장 깊은 곳이니 높이는3.

차수(Degree): 그 노드의 자식 노드 개수.  A의 차수: 3 , B의 차수: 2 .... 트리의 차수: 3

      트리의 차수 = 자식 노드가 가장 많은 노드의 차수.

 

트리 표현하기

-중첩된 괄호(Nested Parenthesis)

: 같은 레벨의 노드들을 괄호로 같이 묶어 표현하는 방법. 읽기는 다소 어렵지만 트리의 하나의 공식처럼 표현할 수 있음.

-중첩된 집합(Nested Set)

:트리가 하위 트리의 집합이라는 관계를 잘 표현할 수 있음.

-들여쓰기(Indentation)

:자료의 계층적인 특징을 잘 나타냄. ex)윈도우 탐색기의 폴더 트리

노드 표현하기 

노드의 표현법: 부모와 자식,형제 토드를 서로 연결짓는 방법

-N링크(N-Link) 표현법

:노드의 차수가 N이라면,  노드가 N개의 링크를 가지고 있어서 이 링크들이 각각 자식 노드를 가리키도록 노드를 구성.

차수(자식 노드의 수)가 노드마다 달라지는 트리에는 적용하기 어려움.

-왼쪽 자식-오른쪽 형제(Left Child-Right Sibling) 표현법

:왼쪽 자식과 오르쪽 형제에 대한 포인터를 갖고 있는 노드의 구조.

언느 한 노드의 모든 자식 노드를 얻으려면 일단 왼쪽 자식 노드에 대한 포인터만 있으면 됨.

2.이진트리

이진트리(Binart Tree): 모든 노드가 최대 2개의 자식을 가질 수 있는 트리. 즉 노드의 최대 차수가 2.

일반 트리처럼 나무 모양의 자료를 담기 위한 자료구조가 아니라 컴파일러나 검색 등에 사용되는 특수 자료구조.

 

이진트리의 여러 형태

-포화 이진 트리(Full Binary Tree): 모든 노드가 자식을 둘씩 가지고 있는 이진 트리. 잎 노드들이 모두 같은 깊이에 존재.

-완전 이진 트리(Complete Binary Tree):잎 노드들이 트리의 왼쪽부터 차곡차곡 채워짐. 잎 노드들 사이에 빠져있으면 안됨.

-높이 균형 트리(Height Balanced Tree): 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1이상 차이나지 않음.

-완전 높이 균형 트리(Completely Height Balanced Tree): 루트노드 기준 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같음.

 

이진 트리의 순회

-전위 순회(Preorder Traversal)

:루트-왼쪽 하위 트리- 오른쪽 하위 트리 순으로 방문. ex) A-B-C-D-E-F-G.

이진 트리를 중첩된 괄호로 표현 가능. 루트부터 시작해 방문하는 노드의 깊이가 깊어질 때마다 괄호를 한 겹씩 두르면 됨.

-중위 순회(Inorder Traversal)

:왼쪽 하위 트리-루트-오른쪽 하위 트리 순으로 방문. 

응용되는 대표적 사레: 수식트리(Expression Tree)으로 중위 순회를 실행하면 중위 표기식이 나옴.

-후위 순회(Postorder Traversal)

:왼쪽 하위트리-오른쪽 하위 트리- 루트 순으로 방문. 후위 순뢰를 실행하면 후위 표기식이 나옴.

 

3.수식 트리(수식 이진트리)

수식트리(Expression Tree)는 수식 이진트리(Expression Binary Tree)라고 부르기도 하는 수식을 표현하는 이진트리임.

하나의 연산자가 두 개의 피연산자를 취한다. 피연산자는 잎노드,  연산자는 루트노드or가지노드 .

루트 노드와 가지 노드들은 모두 피연산자를 양쪽 자식으로 둠.

여기서 피연산자는 수(Number)일 수도 있고 또 다른 식(Expression)일 수도 있음.

하위 수식 트리(잎 노드)부터 계산 결과를 병합해 올라가는 과정을 반복하여 계산을 수행함으로 후위순회가 안성맞춤이다.

 

수식 트리의 구축

후위 표기식을 이용해 트리를 구축하는 것이 수월함.

[후위 표기식에 기반한 수식 트리 구축 알고리즘]

1.수식을 귀에서 앞쪽으로 읽어나감

2.수식의 제일 마지막에 있는 토큰= 루트노드. (후위표기식의 마지막 토큰은 항상 연산자임)

3.연산자는 가지 노드가 되고 그 다음에 오는 두개의 토큰은 각각 오른쪽 자식노드와 왼쪽 자식노드가 됨. 

연속해서 연산자인 경우 이 토큰으로부터 만들어지는 하위 트리가 완성된 이후 읽어낸 토큰이 왼쪽 자식노드가 됨.

4.숫자=잎노드

4. 분리 집합

분리 집합(Disjoint Set): 두개 이상의 집합이 서로 공통된 원소를 갖지 않는 집합들. 교집합은 없고 합집합은 가능.

서로 구분되어애 하는 데이터 집합을 다룰 때 아주 유용. 원소 또는 개체가 어느 집합에 소속되어 있는가를 바탕으로 알고리즘에 응용가능.

 

분리 집합의 표현

자식이 부모를 가리킴. 루트노드틑 집합 그 자체이고, 루트 노드 자신을 포함한 트리 내의 모든 노드들은 그 집합에 소속된다고 생각하면됨.

분리 집합 노드의 구조체에서는 자식노드에 대한 포인터는 없고 부모 노드에 대한 포인터뿐임.

분리 집합의 연산

-합집합(Union): 두 집합을 더하는 연산.

트리 내의 모든 노드들은 루트 노드가 나타내는 집합 안에 있음으로 오른쪽에 있는 집합의 루트 노드를 왼쪽에 있는 루트 노드의 자식 노드로 만듬. 즉 루트노드(5)의 부모 노드를 1로 지정.

-집합 탐색(Find): 원소가 속해 있는 집합을 찾는 연산. 루트 노드가 나타내는 집합이 곧 자신이 속해 있는 집합이므로 원소가 속해 있는 트리의 루트 노드를 찾으면 됨.