Tree(트리)와 Binary Tree(이진 트리)

Tree(트리)

트리는 어떤 속성을 만족하는 node(노드)와 방향 간선의 집합입니다. 또한, 하나의 노드가 root 노드를 가리키는 사이클 없는 그래프로 정의할 수 있습니다.

위키피디아

Tree Terminology(전문 용어)

• Root : 부모가 없는 노드(트리의 가장 상위 노드)
• Leaf : 차수가 0인 노드
• Root-to-leaf path(루트 경로) : 루트로부터 해당 노드까지의 유일한 경로
• Size of tree (트리의 크기) : 연결된 모든 node의 개수
• Subtree(서브 트리) : 자식 node 가 있을 때 이 노드를 root로 하는 tree (level 이 1 줄어듭니다.)
• Height of tree : 최장 루트 경로의 길이
• 단독트리 : 노드가 1개이고 높이는 0인 트리
• (NIL)공백트리 : 노드가 0개이고 높이는 -1인 트리로 정의
• Depth(노드의 깊이) : 어느 한 노드의 root 경로의 길이
• Path length of tree(트리의 경로 길이) : 트리에 있는 모든 노드에 대한 깊이의 합
• Width of tree(트리의 너비) : 최대 레벨의 크기
• Degree(or node's order)(노드의 차수) : 노드들의 차수 중에서 최대 차수 or 어느 한 노드의 서브트리의 개수
• full tree (포화 트리) : 모든 리프가 같은 레벨에 있고, 모든 노드가 같은 차수를 가지고 있는 트리
• Ordered Tree(순서 트리) : 정렬 트리를 의미하는 것이 아닙니다. '순서(ordered)'라는 용어는 트리의 구조와 관련 있습니다.

Tree Traversals(트리 순회)

• level order(레벨 순서) - 책을 읽는 것과 같은 형식으로 레벨별 좌에서 우로 방문합니다.
• inorder(중위순회) - root를 중간에 방문합니다. (left - root - right)
• preorder(전위순회) - root node를 우선 방문하고, 그다음 left 노드, right 노드 순서로 방문합니다.
• postorder(후위순회) - left 노드, right 노드를 우선 방문하고, 그 다음 root 노드를 방문합니다.

모든 전위, 후위 알고리즘은 모두 큐를 사용하여 구현한 레벨 순서 알고리즘과 마찬가지로 스택을 사용하여 반복 알고리즘으로 구현할 수 있습니다.

완전 순서 트리

어떤 순서 트리가 최하위 레벨의 노드 중 오른쪽 몇 개의 원소가 없는 것을 제외하고는 포화 트리와 같을 때 이것을 완전(complete) 하다고 정의합니다. 트리를 메모리나 디스크에 저장하기 위해서는 linearize(선형화, 노드 시이퀀스로 변환)시키는 것이 필요합니다. 이러한 과정을 serialization(직렬화)라고 부릅니다. natural index number(자연 매핑)라고 부르기도 합니다. 순서트리는 자연매핑으로 배열에 저장하는 것은 트리가 포화이거나 거의 포화이어야 효율적입니다. 이러한 트리는 모두 미사용 원소가 없이 배열에 저장될 수 있으며, 배열의 크기는 트리에 있는 노드의 개수와 같습니다.

참고 - java 에서 직렬화(serialization) 라는 용어는 객체를 디스크에 저장하거나 인터넷을 통해 전송하기 위해 byte stream으로 변환하는 과정을 지칭합니다.

순서 트리 공식

1. 차수가 d 인 포화 순서 트리의 레벨 l 에서 k = (d^l - 1)(d-1)일때, 노드의 자연 인덱스 번호가 k,k+1... k+(d^l) -1입니다.
2. 차수가 d 인 포화 순서 트리에서, 노드 i 의 경우 부모의 인덱스는 (i-1) / d 이 되고, 자식들은 di + 1, di + 2 ... , di + d 로 번호가 매겨집니다.

Binary Tree(이진 트리)

이진트리는 모든 내부 노드의 차수가 2인 순서 트리입니다. 공백 노드는 NIL node 라고 지칭합니다.

위키피디아

특성

1. 포화 이진트리의 크기 높이가 h 인 포화 이진 트리의 크기 n은 n = 2^(h+1) -1 입니다. 공백트리는 높이 h = -1 인 포화 이진 트리로 취급합니다.

   n = 2 ^ (h + 1) - 1
   

2. 이진 트리의 크기에 대한 범위 높이가 h 인 이진트리의 크기 n 은 h + 1 <= n <= 2^(h+1) - 1 입니다.

   h + 1 <= n <= 2 ^ (h + 1) - 1
   

3. 완전 이진 트리의 크기에 대한 범위 높이가 h 인 완전이진트리의 크기 n 은 2^h <= n <= 2^(h+1) - 1 입니다.

   2 ^ h <= n <= 2 ^ (h + 1) - 1
   

4. 이진트리를 자연 매핑 하였을 때 노드 i 의 부모의 인덱스는 (i - 1) / 2 이고, 자식은 2 * i + 1 과 2 * i + 2 입니다.

   (i - 1) / 2 // node i 's parent index
   2 * i + 1 // node i 's left child index 
   2 * i + 2 // node i 's left child index 
   

5. 자연 매핑을 사용하면 루트 경로에 있는 어떤 노드의 인덱스도 쉽게 계산할 수 있습니다. 어떤 리프로부터 루트까지 이동하는 것은 현재 인덱스 i 를 (i - 1) / 2 로 반복해서 교체하면 됩니다. 이와 유사하게, 루트로부터 리프까지 내려가는 것은 현재 인덱스 i 를 2 * i + 1 이나 2 * i + 2 로 반복해서 교체하면 됩니다.

   ex) 12 -> 5 -> 2 -> 1
   

6. 크기가 n인 완전 이진 트리에서 리프는 n/2 에서 n - 1 까지 번호가 매겨집니다.

7. 완전 이진 트리는 n/2 개의 내부 노드와 (n + 1) / 2 개의 리프를 가집니다.

Catalan Number(카탈랑 수)

이지 트리의 크기 n 이 주어졌을 때 서로 다른 이진트리의 개수를 구할 수가 있습니다. 크기 0 or 1일때 서로 다른 이진트리의 개수는 1로 정의하고, 나머지 크기에 따른 이진트리의 개수는 공식으로 구할 수 있습니다.

c0 = 1
c1 = 1
c2 = 1 * 1 + 1 * 1 = 2
c3 = 1 * 2 + 1 * 1 + 2 * 1 = 5
c4 = 1 * 5 + 1 * 2 + 2 * 1 + 5 * 1 = 14

Cn = (2n)! / n!(n+1)!

카탈랑 수 위키피디아

카탈랑 수 시각화

수식트리 및 수식트리의 중위표기

수식트리는 연산자(+,-,/,&,*) 와 피연산자(x,2,5,y) 등을 노드로 사용하여 트리를 연산에 우선순위에 따라 생성한 이진 트리입니다. (수식을 이진 트리로 생성하는 알고리즘은 생략합니다. 이때 괄호는 제거됩니다. )

이러한 트리를 트리 순회(inorder, postorder, preorder) 를 통하여 수식을 재생성할 수 있습니다. 그런데 중위표기(inorder)는 괄호가 사라진 상태라 수식의 우선순위가 애매해집니다. 이에 반해 전위 표기와 후위 표기 표현은 괄호가 없어도 모호하지 않습니다. 이항 연산을 표현하는 java 메소드는 전위표기 표현을 사용하고 있습니다.

sum(1, 2), product(3, 5) //  java 메소드의 전위 표기

후위표기 표현으로부터 수식을 계산

5 3 + 7 4 - 1 - / //(후위표현 수식) 

위와 같은 수식 계산에서 마지막을 제외한 각각의 반복은 피연산자를 스택에 삽입합니다. 유일한 차이는 토큰이 연산자(+,-,/)일 때, 두개의 피연산자 스택으로부터 삭제되어 리턴되며, 이 연산자와 결합된 새로운 피연산자를 만들어 스택에 삽입 한다는 것입니다.

참고 - forest(포리스트)

forest 는 트리의 집합입니다. 복잡한 포리스트 구조는 이진 트리와 자연적인 1 대 1 매핑이 존재합니다.

참고 - 자연매핑을 사용하여 포리스트를 이진트리로 표현하는 알고리즘

1. 첫 번째 트리의 root 를 이진 트리의 root 로 매핑합니다.
2. 만일 노드가 y가 x의 첫 번째 자식이고, x가 x`으로 매핑된다면 y를 x`의 왼쪽 자식으로 매핑합니다.
3. 만일 노드가 z가 x의 다음 형제이면, z를 x`의 오른쪽 자식으로 매핑합니다.

참고서적 - Java 를 이용한 자료구조 책(홍릉 과학출판사)