- 트리(Tree)
트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조.
[ 관련 용어 ]
- 루트 노드(root node) : 트리의 최상위 노드 (부모 x)
- 단말 노드(leaf node) : 자식이 없는 노드
- 크기(size) : 트리에 속한 노드의 총 갯수
- 깊이(depth) : 최상위 노드로 부터의 거리 ( 루트 노드에서 해당 노드까지 )
- 높이(height) : 깊이 중 최댓값
- 차수(degree) : 각 노드의 (자식 방향) 간선의 갯수
트리의 크기가 N 이면, 전체 간선의 수는 N - 1 개 입니다.
- 이진 탐색 트리 (Binary Search Tree)
이진 탐색이 동작 가능하도록 고안된 자료구조의 일종, 효율적인 탐색이 가능함.
[ 특징 ]
구조 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
Q. 이진 탐색 트리가 구성되어 있는 상태에서 특정 데이터(37)를 조회해라.
Step1. 루트 노드 방문 후 탐색 시작
현재 노드(루트 노드)와 찾는 원소(37)을 비교 → 찾는 원소가 30보다 더 크므로 오른쪽 방문
Step2. 현재 노드와 값을 비교
현재 노드와 찾는 원소(37)을 비교 → 찾는 원소가 30보다 더 작으므로 왼쪽 방문
Step3. 현재 노드와 값을 비교(탐색 종료 전까지 반복)
현재 노드와 찾는 원소(37)을 비교 → 원소(37)을 찾았으므로 탐색 종료
[ 한계 ]
왼쪽과 오른쪽이 균형이 잡힌 경우와 같이 이상적인 경우에만 효과적이다.
이상적인 경우에 데이터 탐색시 log N에 비례한 연산이 소요된다.
- 트리의 순회(Tree Traversal)
트리 자료구조에 포함된 노드를 특정한 방법으로 "한 번"만 방문하는 방법 (트리의 정보 시각적 확인)
[ 순회 방법 ]
- 전위 순회(pre-order traverse) : 루트를 먼저 방문
- 중위 순회(in-order traverse) : 왼쪽 자식 방문 후 루트 방문
- 후위 순회(post-order traverse) : 오른쪽 자식 방문 후 루트 방문
[ 트리 순회 코드 ]
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 != None:
pre_order(tree[node.left_node])
if node.right_node != None:
pre_order(tree[node.right_node])
# 중위 순회
def in_order(node):
if node.left_node != None:
in_order(tree[node.left_node])
print(node.data, end=' ')
if node.right_node != None:
in_order(tree[node.right_node])
# 후위 순회
def post_order(node):
if node.left_node != None:
post_order(tree[node.left_node])
if node.right_node != None:
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 == 'None':
left_node = None
if right_node == 'None':
right_node = None
tree[data] = Node(data, left_node, right_node)
print("전위순회")
pre_order(tree['A'])
print()
print("중위순회")
in_order(tree['A'])
print()
print("후위순회")
post_order(tree['A'])
예시의 입력값을 위의 코드 실행 후 입력하면 결과는 아래와 같습니다.
[ 참조 ]
이코테 2021 강의 (이것이 취업을 위한 코딩 테스트다 with 파이썬)