트리(Tree)

트리의 정의

 

트리는 '계층적인 구조(Hierarchical Structure)'를 가지는 비선형 자료구조이다. 가장 상위 노드에서 시작하여 여러 노드가 사방으로 뻗어나가는 형태를 취한다. 또한 사이클이 없이 모든 정점이 연결되어있는 그래프이다. 사이클이 없는 그래프이므로 정점의 개수가 N개면 간선의 개수는 N-1개이다.

• 노드(Node) : 트리를 구성하는 하나의 데이터 단위
• 간선(Edge) : 노드와 노드를 잇는 선
• 루트(Root) : 부모가 없는 최상위 정점
• 부모(Parent) : 정점 A에서 정점 B로 가는 간선이 있을 때 A를 B의 부모라고 한다.
• 자식(Child) : 정점 A에서 정점 B로 가는 간선이 있을 때 B를 A의 자식이라고 한다.
• 형제(Siblings) : 같은 부모를 갖는 정점들
• 차수(Degree) : 정점의 자식의 개수
• 리프(Leaf) : 자식이 없는 정점. 단말 노드라는 용어로도 쓰인다.
• 깊이(Depth) : 루트에서 해당 정점으로 가는 최단 경로의 길이
• 레벨(Level) : 루트 노드(Level 0)를 시작으로 아래로 내려갈수록 1씩 증가하는 층을 의
• 높이(Height) : 정점들의 깊이의 최댓값
• 트리의 차수(Degree of tree) : 트리의 최대 차수 =  max(deg1, deg2, ... degn)
• 너비(Width) : 각 레벨에 속한 정점의 수의 최댓값
• 내부 정점(Internal vertex) : 차수가 2 이상인 정점
• 경로(Path) : 시작 정점에서 끝 정점에 이르는 길 사이에 있는 정점들의 순서. 일반적으로 하나의 간선을 두 번 이상 지나는 경로는 생각하지 않는다. 시작 정점과 끝 정점은 동일할 수도 있다.
• 경로의 길이(Length of path) : 경로가 지나가는 간선의 개수
• 서브 트리(Subtree) : 전체 트리의 일부분을 떼어낸 작은 트리 구조, 모든 트리는 또 다른 서브 트리의 집합이라 볼 수 있다.
• 포레스트(Forest) : 서로 독립인 트리들의 집합

트리의 종류

· 순서 트리 (Ordered Tree)

- 각 자식 노드에 순서가 부여되어 저장 위치가 고정되는 트리

- 통상, 좌측부터 순서 있게 위치 함

· 경사 트리 (Skew Tree)

- 모든 노드가 1개 자식 노드 만을 갖고, 경사지게 보이는 트리

· 이진 트리 (Binary Tree)

- 각 노드의 차수(자식 수)가 2 이하인 순서 트리

 

전 이진 트리 (Full Binary Tree)

- 모든 노드의 차수/자식이 0 또는 2 이어야 함

- 즉, 자식이 없으면 리프 노드, 자식이 있으면 반드시 2개 모두 있어야 함. 쉽게, 외동 자식이 없는 이진 트리.

 

포화 이진 트리 (Perfect Binary Tree)

- 모든 레벨이 빈틈없이 꽉 찬 이진 트리

- 모든 내부 노드가 자식 2개를 가지며, 모든 리프 노드가 동일한 레벨(깊이)에 위치한 트리

- 높이가 h일 때, 2^h - 1개 노드를 갖음

- 포화 이진트리는, 전 이진 트리이면서 동시에 완전 이진 트리이기도 함

 

완전 이진 트리 (Complete Binary Tree)

- 포화 이진 트리의 맨아래 단말 노드들을, 오른쪽부터 하나씩 제거하면, 얻어지는 트리

- 마지막 레벨을 제외한 모든 레벨이 꽉 차 있으며, 마지막 레벨은 왼쪽부터 연속적으로 채워지는 트리

- 중간에 빈 자리가 있으면 안됨

- 즉, 부모 → 왼쪽 자식 → 오른쪽 자식 순으로 꽉 채워짐

- 높이가 h일 때, h-1 레벨까지 2^(h-1) - 1개 노드를 갖음

- 쉽게, 왼쪽부터 빈틈없이 채워지는 이진 트리

 

이진 힙 (Binary Heap)

- 완전 이진 트리 구조를 기반으로 한 자료구조

- 부모와 자식 간에는 대소 관계가 유지됨

- 형제 노드 간에는 대소 관계가 정해지지 않음

- 최대 힙 (Max Heap) : 부모 ≥ 자식

- 최소 힙 (Min Heap) : 부모 ≤ 자식

- 따라서, 부분 순서 트리 (Partially Ordered Tree) 라고도 함

· 이진 탐색 트리 (Binary Search Tree, BST)

- 이진 트리 구조를 갖으나, 자료의 검색, 삭제, 삽입에 효율적이게 한 트리 자료구조

- 좌측 자식 노드 값이 부모 노드 값 보다 작고, 우측 자식 노드 값이 무보 노드 값 보다 큼

- 각 노드는 2개의 자식 노드를 각각 가리키는 2개의 포인터를 갖음

· 균형 트리 (Balanced Tree)

- 이진 트리 구조를 갖으나, 하위 노드 구조가 좌우 대칭이 되도록 한 것

- 이진 탐색 트리를 보다 일반화시킨 트리 자료구조

- 탐색 성능 저하를 방지하기 위해 사용됨

· N항 트리 (N-ary Tree, N-way Tree)

- 일반적으로, 자식 노드 수(차수)가 3 이상일 때를 말함

- 한편, 자식 노드가 3 이상인 트리 구조를 총칭해서, 다중 트리 (Multi-Branch Tree)라고 함

 

트리의 사용 이유

• 빠른 검색, 삽입, 삭제 속도 : 데이터를 잘 정렬된 트리형태로 저장하면, 원하는 데이터를 찾을 때마다 탐색 범위가 절반씩 줄어들게 된다. 만약 정렬되어 있지 않다면 하나의 값을 찾기 위해서 값을 처음부터 하나한 비교를 하며 풀스캔을 해야한다. 하지만 정렬이 되어있다면 값을 찾기 위해 풀스캔을 하지 않아도 된다.

트리와 배열(Array)의 차이점

	배열(Array)	트리(Tree)
구조 형태	선형 구조 (데이터가 일렬로 연속적으로 배치)	비선형/계층 구조 (데이터가 위아래 부모-자식 관계로 배치됨)
관계 표현	앞과 뒤(1:1관계)의 순서만 존재	상위와 하위(1:N 관계)의 계층이 존재
데이터 접근 속도	인덱스(Index)로 즉시 접근	루트 노드부터 탐색
데이터 찾기(검색)	순서대로 다 찾아야 하므로 데이터가 많아질수록 느려짐	트리 구조를 타고 내려가므로 데이터가 많아도 빠름
크기 변경	처음에 크기를 정하면 늘리거나 줄이기 어려움 (정적)	필요할 때마다 새 노드를 연결하거나 끊으면 됨 (동적)
메모리 저장	연속적인 메모리 공간에 할당	메모리 내에 분산 저장 후 노드로 연결
주요 용도	순서가 중요하고, 데이터의 개수가 변하지 않는 단순 목록	정렬, 대용량 데이터 검색(데이터 베이스 인덱스), 계층 구조 표현

 

트리 순회 방식

예시를 위한 이진 트리

전위 순회 (Preorder)

• 순서 : 루트 노드 → 왼쪽 자식 → 오른쪽 자식
• 전위 순회한 결과 : A B D C E F G

중위 순회 (Inorder)

• 순서 : 왼쪽 자식 → 루트 노드 → 오른쪽 자식
• 중위 순회한 결과 : D B A E C F G

후위 순회 (Postorder)

• 순서 : 왼쪽 자식 → 오른쪽 자식 → 루트 노드
• 후위 순회한 결과 : D B E G F C A

트리 코딩 구현

 

위의 예시를 코드로 구현하면 다음과 같다.

# Node 클래스 생성
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 트리 클래스 생성
class Tree:
    def __init__(self):
        self.root = None              # 루트는 비워둔 채로 설정

    def preorder(self, node):         # 전위 순회는 루트 > 왼쪽 > 오른쪽 순
        if node is not None:
            print(node.value, end='')
            self.preorder(node.left)
            self.preorder(node.right)

    def inorder(self, node):          # 중위 순회는 왼쪽 > 루트 > 오른쪽 순
        if node is not None:
            self.inorder(node.left)
            print(node.value, end='')
            self.inorder(node.right)
    
    def postorder(self, node):        # 후위 순회는 왼쪽 > 오른쪽 > 루트 순
        if node is not None:
            self.postorder(node.left)
            self.postorder(node.right)
            print(node.value, end='')

# 트리 생성
root = Node('A')
nodeB = Node('B')
nodeC = Node('C')
nodeD = Node('D')
nodeE = Node('E')
nodeF = Node('F')
nodeG = Node('G')

# 노드 연결
root.left = nodeB
root.right = nodeC
nodeB.left = nodeD
nodeC.left = nodeE
nodeC.right = nodeF
nodeF.right = nodeG

# 전위 순회 테스트
test_tree = Tree()
print('전위 순회: ', end='')
test_tree.preorder(root)
print()

# 중위 순회 테스트
print('중위 순회: ', end='')
test_tree.inorder(root)
print()

# 후위 순회 테스트
print('후위 순회: ', end='')
test_tree.postorder(root)
print()

 

결과값

전위 순회: ABDCEFG
중위 순회: DBAECFG
후위 순회: DBEGFCA

# 이론상으로 계산했던것과 동일하게 결과가 나오는걸 확인할 수 있다