트리

벌써 마지막 장에 와버렸습니다. 마지막은 트리에 대해서 공부합니다.

우선 트리는 루트, 리프, 비단말 노드, 자식, 부모, 형제, 조상, 자손, 레벨, 차수, 서브트리, 빈 트리 등의 용어를 사용합니다.
트리 구조는 다단계랑 비슷합니다.

루트: 다단계 맨 윗 사람

리프: 가장 마지막에 있는 사람

비단말 노드: 리프를 제외한 노드
자식: 아래쪽 노드

부모: 윗쪽 노드

형제: 부모가 같은 노드

조상: 윗쪽으로 가며 만나는 모든 노드
자손: 아래쪽으로 가며 만나는 모든 노드

레벨: 루트 레벨 0 -> 에서 아래쪽으로 가며 1씩 증가함

차수: 노드가 갖는 자식의 수
높이: 루트 -> 리프의 거리

서브트리: 한 노드를 루트로 한 새로운 트리
빈 트리: 노드, 가지가 없는 트리

 

순서트리: 형제 간 순서 관계가 있음.
무순서 트리: 형제 간 순서 관계가 없음.

 

순서트리의 검색

BFS(너비우선탐색): 레벨 순으로 스캔

DFS (깊이우선탐색): 가지 순으로 스캔

그리고 트리에서 전위, 중위, 후위 순회가 있는데, 아주 쉽게 판별하기 위해 루트노드의 탐색 순서를 보면 됩니다.

전위순회: 탐색에서 루트노드가 앞에 위치할 경우 
중위순회: 탐색에서 루트노드가 가운데 위치할 경우 
후위순회: 탐색에서 루트노드가 뒤에 위치할 경우 

 

백준 예제문제.

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

1991번: 트리 순회

 

풀이

import sys
sys.setrecursionlimit(10**4)
class Node:
    def __init__(self, data, left_node, right_node):
        self.data=data
        self.left_node= left_node
        self.right_node = right_node

#전위순회
def pre_order(node):
    print(node.data, end='')
    if node.left_node != ".":
        pre_order(tree[node.left_node])
    if node.right_node != ".":
        pre_order(tree[node.right_node])

#중위순회

def in_order(node):
    if node.left_node != ".":
        in_order(tree[node.left_node])
    print(node.data, end='')
    if node.right_node != ".":
        in_order(tree[node.right_node])
#후위순회

def post_order(node):
    if node.left_node != ".":
        post_order(tree[node.left_node])
    if node.right_node != ".":
        post_order(tree[node.right_node])
    print(node.data, end='')

n = int(input())
tree ={}

for i  in range(n):
    data, left_node, right_node = input().split()
    if left_node ==  ".":
        left_node = "."
    if right_node == ".":
        right_node = "."
    tree[data] = Node(data, left_node, right_node)


pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])

 

이진트리: 노드의 최대 자식수가 2인 트리구조

완전이진트리: 루트부터 왼쪽 레벨로 노드가 가득차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져있는 이진트리 (이전 포스팅에서 heap 구조와 같음) n개의 노드를 저장할 수 있는 완전 이진트리의 높이 -> log(n)

 

이진 트리 구조의 이해를 돕는 백준 예제 문제

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

11725번: 트리의 부모 찾기

풀이

from collections import defaultdict, deque

n = int(input())
tree = defaultdict(list)
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

parent = [0] * (n+1)
visited = set([1]) #방문체크
q = deque([1])

while q:
    node = q.popleft()
    for child in tree[node]:
        if child not in visited:
            visited.add(child)
            parent[child] = node
            q.append(child)

for i in range(2, n+1):
    print(parent[i])

 

이진 균형검색 트리 종류

- AVL 트리, 레드∙블랙 트리

특징: 구조가 단순, 중위 우선의 깊이 순위 탐색을 통해 노드값을 오름차순으로 얻을 수 있음, 이진 검색과 비슷한 방식으로 빠른 탐색 가능, 노드를 삽입하기 쉬움

 

이진이 아닌 균형 검색 트리 종류

- B 트리, 2-3 트리