[알고개념] 4. 트리

1. 트리의 기초 용어

• Internal node: nodes with at least one child 
• External node (Leaf): nodes without children 
• Ancestor of a node: parent, grandparent, grand grandparent, and so on (including itself)
• Descendant of a node: child, grandchild, grand grandchild, and so on (including itself)
• Sibling : nodes that have the same parent
• Subtree : a tree that consists of a node of the original tree as the root and all the descendants of the node
• Edge: A pair of nodes ( u , v )
• Path: A sequenc of nodes
• Depth: The number of ancestors to the root - 1 (excluding itself)
• Level: The set of all nodes at the same path
• Height: maximum depth of any external descendent of the node
• Degree: the number of children of the node

 

2. 트리의 순회

https://www.acmicpc.net/problem/1991

• 전위 순회(preorder)한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회(inorder)한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회(postorder)한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

void preorder(int curr) {
    cout << (char) (curr + 'A');
    if (left[curr] != -1) preorder(left[curr]);
    if (right[curr] != -1) preorder(right[curr]);
}

void inorder(int curr) {
    if (left[curr] != -1) inorder(left[curr]);
    cout << (char)(curr + 'A');
    if (right[curr] != -1) inorder(right[curr]);
}

void postorder(int curr) {
    if (left[curr] != -1) postorder(left[curr]);
    if (right[curr] != -1) postorder(right[curr]);
    cout << (char)(curr + 'A');
}

 

3. 트리의 종류

• 이진 트리: 최대 2개의 노드를 자식으로 갖는 트리, 즉 왼쪽 자식과 오른쪽 자식으로 나눠서 구현할 수 있다. Decision Tree 등에 활용할 수 있다. 이 때 인덱스를 접근할 경우 부모 인덱스는 $n/2$, 자식 인덱스는 $2n,\ 2n+1$로 나타낼 수 있다.
• 포화 이진 트리: 잎 노드를 제외한 모든 노드가 2개의 자식 노드를 가진 트리. 총 노드의 개수가 2^j - 1 꼴이다. 세그먼트 트리에서 활용된다.
• 완전 이진 트리: 높이가 k 일 때 레벨 1 부터 k 1 까지는 모두 차 있고 레벨 k 에서는 왼쪽 노드부터 차례로 차 있는 이진 트리. 
• 이진 검색 트리(BST): 각 노드에 (key, value) 엔트리 쌍을 가진 이진 트리로, 값을 검색할 때 사용하는 트리이다.
• AVL 트리: 이진 검색 트리의 한 종류로 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 항상 1 이하가 되도록 하는 트리이다.
• (2, 4) 트리: Multiway 검색 트리로 각 노드가 2~4개의 자식을 가질 수 있는 트리이다. 
• Red Black 트리: 이진 검색 트리의 한 종류이다. 자세한 내용은 https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC 참고..