[ 자료구조 ] 트리란?(이진 트리, 파이썬 트리 순회 방법, 이진 탐색 트리)

트리(Tree)

---

• 스택, 큐와 같은 선형 구조가 아닌 비선형 자료구조
• 계층적 관계를 표현한다.
• 일반적인 틀에서 삽입, 삭제 연산의 시간 복잡도 : O(logN)

 

트리의 구성

---

• 노드(Node) : 트리를 구성하는 각각의 요소
• 간선(Edge) : 각각의 노드를 연결하는 선
• 루트 노드(Root Node) : 트리 구조에서 최상위에 있는 노드
• 단말 노드(Terminal Node = Leaf Node) : 하위에 다른 노드가 연결되어 있지 않은 최하위 노드
• 내부 노드, 비단말 노드(Internal Node) : 단말 노드를 제외한 모든 노드로 루트 노드도 포함
• 루트 노드를 제외한 모든 노드는 단 하나의 부모 노드만을 갖는다.
• 방향성이 있는 비순환 그래프로 Loop나 Circuit이 없다.
• 루트에서 어떤 노드로 가는 경로는 유일하다.

 

순회 방법

---

• 중위 순회(In-order Traversal) : 왼쪽 → 부모 → 오른쪽
• 전위 순회(Pre-order Traversal) : 부모 → 왼쪽 → 오른쪽
• 후위 순회(Post-order Traversal) : 왼쪽 → 오른쪽 → 부모
• 레벨 순회(Level-order Traversal) : 노드를 레벨 순서로 방문(BFS와 동일해 큐로 구현 가능)
• 파이썬으로 이진 트리 순회

import sys
def DFS(v):

	if v>7:
		return
	else:
		# 전위순회
		print(v, end=' ') # 출력
		DFS(v*2) # 왼쪽 자식 호출(탐색)
		DFS(v*2+1) # 오른쪽 자식 호출(탐색)

		# 중위순회
		DFS(v*2) # 왼쪽 자식 호출(탐색)
		print(v, end=' ') # 출력
		DFS(v*2+1) # 오른쪽 자식 호출(탐색)

		# 후위순회
		DFS(v*2) # 왼쪽 자식 호출(탐색)
		DFS(v*2+1) # 오른쪽 자식 호출(탐색)
		print(v, end=' ') # 출력

if __name__ == "__main__":
	DFS(1)

 

이진 트리(Binary Tree)

---

• 부모 노드가 두 개의 자식 노드를 갖는 형태
• 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 진다.
• 나뉘어진 서브트리 모두 이진 트리여야 한다.
• 레벨(Level) : 각 층별로 숫자를 매긴 것으로 0부터 시작하며 루트 노드의 레벨이 0인 것.
• 높이(Height) : 트리의 최고 레벨
• 포화 이진 트리(Full Binary Tree) : 모든 레벨이 꽉 찬 이진 트리
• 완전 이진 트리(Complete Binary Tree) : 왼쪽에서 오른쪽으로 순서대로 채워진 이진 트리
  • 오른쪽은 채워지고 왼쪽은 채워지지 않은 트리 → X
  • 왼쪽은 채워지고 오른쪽은 채워지지 않은 트리 → O
• 편향 이진 트리(Skewed Binary Tree) : 모든 노드가 부모의 왼쪽이로 편향되어 있거나 반대인 경우의 이진 트리
• 정 이진 트리(Full Binary Tree) : 단말 노드를 제외한 모든 노드가 자식 노드를 2개 또는 0개 가지는 이진 트리

 

이진 탐색 트리(Binary Search Tree)

---

• 이진 트리 형태로 효율적인 탐색을 위해 저장 규칙을 정한 트리
  • 숫자를 예로 부모의 노드는 왼쪽 자식 노드보다 크고 오른쪽 자식노드보다 작음
• 탐색에 효율적이지만 입출력 데이터에 따라 트리 구조가 편향되는 문제점이 있다.
• Rebalancing : 배열보다 많은 메모리를 사용했지만 시간 복잡도가 같게 되는 비효율적인 상황을 해결하기 위해 균형을 잡기 위한 트리 구조를 재조정하는 기법
  • AVL, Red-Black Tree 등