[자료구조] 트리

그래프 형태의 계층적 구조를 나타내는 자료구조

 

하나의 루프노드에서 시작해 여러개의 자식노드로 뻗아나간다.

노드와 간선으로 이루어져 있으며 사이클이 없는 그래프이다. 

트리의 기본 용어

• 노드(Node): 데이터를 저장하는 기본 단위.
• 루트(Root): 트리의 시작점. 부모가 없음.
• 부모(Parent), 자식(Child): 노드 간 관계.
• 리프(Leaf): 자식이 없는 노드.
• 간선(Edge): 노드들을 연결하는 선.
• 서브트리(Subtree): 어떤 노드를 루트로 하는 트리.
• 레벨(Level): 루트에서부터의 깊이.
• 높이(Height): 루트에서 가장 깊은 노드까지의 거리.

 

위 사진과 같은 트리를 이진트리라고 한다. 각 노드가 최대 두 개의 자식을 가지는 트리이다.

노드가 존재 가능한 위치에 존재하지 않는다면 공집합노드가 있다는 것으로 여겨진다.

공집합 노드 또한 노드의 일부분으로 간주한다.

 

포화 이진 트리(Perfect Binary Tree)

모든 노드가 0개 또는 2개의 자식을 가짐.

노드 추가를 위해서는 레벨을 더 높여야 하는 트리구조

 

완전 이진 트리(Complete Binary Tree)

마지막 레벨을 제외한 모든 레벨이 꽉 차 있고 , 마지막 레벨은 왼쪽부터 채워짐.

 

 

 

배열기반의 트리 구현

 

연결리스트 기반의 트리 구현

 

 

 

이진트리 순회 방법

 

 

 

• 중위 순회(in-order traversal): 왼쪽 자손, 자신, 오른쪽 자손 순서로 방문하는 순회 방법. 이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있다. 이를 트리 정렬(Tree sort)이라고 한다.
• 전위 순회(pre-order traversal): 자신, 왼쪽 자손, 오른쪽 자손 순서로 방문하는 순회 방법.
• 후위 순회(post-order traversal): 왼쪽 자손, 오른쪽 자손, 자신 순서로 방문하는 순회 방법.

 

 

연산	평균 시간복잡도	최악 시간복잡도
탐색(Search)	O(log n)	O(n)
삽입(Insert)	O(log n)	O(n)
삭제(Delete)	O(log n)	O(n)