자료구조 | 트리

yeonk·2022년 4월 2일

python

목록 보기

21/22

1. 트리(tree)

사이클이 없는 연결된 그래프(acyclic connected graph)

트리의 루트(root) 유무에 따라 의미하는 트리가 다를 수 있으니 주의해야 함
트리의 사용
- 이진 탐색 트리, 균형 이진 트리 - 언어에서 내부 구현으로 활용
- B트리 - 데이터 베이스를 구축하는 큰 틀

1-1. 노드

그래프에서의 정점을 트리에서는 노드라고 함

출처: https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

루트 노드(root node): 부모가 없는 노드
내부 노드(internal node): 루트 노드, 리프 노드를 제외한 노드
리프 노드(leaf node): 차수가 0인 노드
부모(parent) - 자식(child) 관계: 위 그림에서 노드 A(부모)와 노드 B(자식)과 같은 관계를 부모-자식 관계로 볼 수 있음
조상(ancestor) - 자손(descendant) 관계: 위 그림에서 노드 A(조상)과 노드 H(자손)과 같은 관계를 조상-자손 관계로 볼 수 있음
서브 트리(subtree): 어떤 노드의 자식이 이루는 트리

1-2. 차수(degree)

어떤 노드의 자식 노드 개수
트리의 차수는 트리에 있는 노드의 최대 차수를 의미

1-3. 레벨(level)

루트의 레벨을 1로 하고 자식으로 내려가면서 하나씩 더해지는 개념
어떤 트리의 깊이 혹은 높이는 트리가 가지는 최대 레벨을 의미
대체로 루트 레벨은 0 또는 1 로 설정한다.

루트를 가지지 않는 일반적인 트리에서 노드의 개수가 n, 에지의 개수가 e일 때 아래와 같은 식이 성립한다.

e = n-1

e > n-1이 되는 순간 트리에 사이클이 생긴다고 볼 수 있다.

1-4. 이진 트리(binary tree)

트리를 구성하는 노드의 자식이 최대 2개인 트리

자식이 없는 경우, 자식을 하나 가진 경우, 자식을 둘 가진 경우로 총 3가지를 고려할 수 있다.
왼쪽 자식, 오른쪽 자식으로 구분

레벨 L에서의 최대 노드 개수

2^{L-1}

높이가 h일 때 가능한 최대 노드 개수

2^{h}-1

최소 노드 개수: $h$ (높이)

포화 이진 트리(full binary tree): 높이가 $h$ 일 때 노드 개수가 $2^{h}-1$ 인 트리

완전 이진 트리(complete binary tree): 높이가 $h$ 일 때 레벨 $h-1$ 까지 노드 개수가 $2^{h-1}-1$ 이고 레벨 $h$ 에서는 노드가 왼쪽에서 오른쪽으로 채워지는 트리

편향 이진 트리(skewed binary tree): 왼쪽이나 오른쪽 서브 트리만 가진 트리

2. 이진 트리 순회

트리도 그래프의 일종이기 때문에 DFS, BFS를 이용하여 순회해본다.

DFS → 전위 순회, 중위 순회, 후위 순회
BFS → 레벨 순서 순회
트리 노드 구현

class TreeNode:
	def __init__(self, data=None):
    	self.__data = data
        self.__left = None
        self.__right = None
    
    def __def__(self):
    	print('data{} is deleted'.format(self.__Data))
        
    @property
    def data(self):
    	return self.__data
        
    @data.setter
    def data(self, data):
    	self.__data = data
    
    @property
    def left(self):
    	return self.__left

    @left.setter
    def left(self, left):
    	self.__left = left
        
    @property
    def right(self):
    	return self.__right

    @right.setter
    def right(self, right):
    	self.__right = right

2-1. 전위 순회(preorder traversal)

현재 노드 → 왼쪽 서브 트리 → 오른쪽 서브 트리

재귀 함수 구현

def preorder(cur):
	# 현재 노드가 empty node 라면
    if not cur:
    	return
    
    # 방문
    print(cur.data, end=' ')
    
    preorder(cur.left)
    
    preorder(cur.right)

스택 자료구조와 반복문 이용

def iter_preorder(cur):
	s = Stack()
    while True:
    	while cur:
        	print(cur.data, end=' ')
            s.push(cur)
            cur = cur.left
        
        cur = s.pop()
        if not cur:
        	break
            
        cur = cur.right

2-2. 중위 순회(inorder traversal)

왼쪽 서브 트리 → 현재 노드 → 오른쪽 서브 트리

재귀 함수 구현

def inorder(cur):
	# 현재 노드가 empty node 라면
    if not cur:
    	return
    
    inorder(cur.left)
    
    # 방문
    print(cur.data, end=' ')
    
    inorder(cur.right)

스택 자료구조와 반복문 이용

def iter_inorder(cur):
	s = Stack()
    while True:
    	while cur:
            s.push(cur)
            cur = cur.left
        
        cur = s.pop()
        if not cur:
        	break
            
        print(cur.data, end=' ')
        cur = cur.right

2-3. 후위 순회(postorder traversal)

왼쪽 서브 트리 → 오른쪽 서브 트리 → 현재 노드

재귀 함수 구현

def postorder(cur):
	# 현재 노드가 empty node 라면
    if not cur:
    	return
    
    postorder(cur.left)
    postorder(cur.right)
    print(cur.data, end=' ')

2-4. 레벨 순서 순회(levelorder traversal)

큐를 사용하는 순회 방법, BFS 일종

def levelorder(cur):
	q = Queue()
    
    q.put(cur)
    while not q.empty():
    	cur = q.get()
        # 방문
        print(cur.data, end=' ')
        # 현재 노드의 왼쪽 자식이 있다면 큐에 추가
        if cur.left:
        	q.put(cur.left)
        # 현재 노드의 오른쪽 자식이 있다면 큐에 추가
        if cur.right:
        	q.put(cur.right)