제한된 자료구조의 매력, 이진트리(Binary Tree)

트리란

트리는 하나의 뿌리에서 뻗어 나가는 모양의 자료구조이다. 루트(root)로부터 시작해 간선(edge)으로 연결된 자식노드(node)들과 연결된 형태를 갖는다. 자식 노드가 없는 노드를 리프(leaf)라고 하며, 자식노드들은 작은 형태의 트리인 서브트리를 이룬다. 그 외에 루트로부터 멀어진 정도를 나타내는 레벨, 가장 먼 레벨에서 루트까지의 간선 수를 표기하는 높이 등을 활용하여 자료를 분석한다.

그래프와 트리의 차이

"트리는 순환 구조를 갖지 않는 그래프입니다."

트리는 우리가 어렵지 않게 그릴 수 있는 전형적인 그래프이다. 그렇지만, 전형적이면서도 구조적인 이 자료구조를 그리기 위해서는, 다음과 같은 조건을 지켜서 그려야만 한다.

• 루트를 가리키는 간선이 없어야 한다.
• 간선이 가리키지 않는 정점은 오직 루트 하나 뿐이다.
• 하나의 노드는 오직 하나의 간선에 의해 참조된다.

위의 세 조건은 트리가 나무를 뒤집어놓은 모양을 갖추기 위한, 조건이라고 할 수 있다. 사실 중요한 것은, 이 제한으로 인해 트리는 이전에 등장한 값을 다시 참조하지 않는 정말 제한된 형태의 그래프가 된다는 점이다. 그 덕분에 트리는 하나의 흐름을 따르는 형태의 자료구조로서 다룰 수 있고, 기존 자료구조의 트리화나 표기법의 함축을 이룩했다.

특히 우리가 가장 많이 접하게 되는 이진트리는 각 노드마다의 자식노드 수를 두 개로 한정하여, 특유의 직관성을 더욱 증대하는 방식으로 활용한다. 놀라운 점은 그래프를 접하기 이전의 핵심이었던, 배열 형태의 자료를 이진트리를 활용해 획기적으로 분석할 수 있다는 점이다.

이진트리

이진트리는 각 노드의 자식노드 숫자가 0개, 1개, 2개로 제한된 구조의 트리를 말한다. 이진트리의 효용은 작은 수에서 오는 직관성에 있다. 0진트리가 있다고 한다면, next값이 없는 단독적인 노드라고 할 수 있고, 1진 트리가 있다고 한다면, 노드 하나가 다음 노드를 가리키는 연결리스트와 정확히 일치한다고 할 수 있다. 때문에 이진트리라는 것은 연결리스트 즉 배열형태의 자료형에서의 발전이라고도 할 수 있다. 그렇지만, 이진트리의 효용은 배열을 다룰 때도 두드러진다.

완전이진트리

문맥상 이진트리와 배열의 관계에 대해서 설명해야할 것 같지만, 이진트리 중에서도 직관성을 극대화한 완전이진트리라면 그 설명이 더 원활할 것이다. 완전이진트리는 루트로부터 연결되는 자식노드의 숫자가 입력되는 순서가 명시된 이진트리다. 순서는 직관의 힘을 빌려서 얘기하면 "가장 왼쪽부터 채워 넣는다"고 한다. 하지만 왼쪽이라는 것이 존재하지 않는 데이터 상에서는 '각 노드가 입력된 순서에 따라, 앞의 노드부터 자식노드를 2개씩 입력한다'고 할 수 있다.

완전이진트리는 제한 조건이 정말 많은 그래프이고, 사실 그다지 그래프스럽지도 않다. 오히려 배열로 표현 가능할 정도이니 말이다. 앞서 말한 것처럼, 완전이진트리는 각 노드끼리의 연결 외에 순서를 규정한다. 가장 먼저 입력된 정보를 루트로 삼고, 그 다음부터 차례로 레벨 1단계의 자식노드 2단계의 자식노드가 되며, 각 단계에서도 1,2 / 1,2,3,4 의 순서가 생긴다. 때문에 일반적인 형태의 배열을 완전이진트리로 구현할 수 있으며, 완전이진트리도 배열로 표현할 수 있다.

lst = [3,5,8,9,6,1,2,7,4]

완전이진트리가 갖는 효용 중에 가장 일반적인 것은 높이를 활용해 요소의 수를 가늠하는 것이다. 높이가 h 일때, 마지막 레벨에 x개만큼의 노드가 채워지지 않았다면, 전체 요소수 N은 2h+1 - (x+1)로 알아낼 수 있다. 예시에서는 N = 23+1 - (6+1) = 16 - 7 = 9 이다.

완전이진트리 구현

완전이진트리를 파이썬으로 구현해보자.

# 트리노드 선언
class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# 트리화할 배열 선언
lst = [3,5,8,9,6,1,2,7,4]
idx = 0

# make_tree_by 함수 선언
def make_tree_by(lst, idx):
    
    # 현재 노드를 담을 변수 parent 선언
    parent = None
    
    # 배열의 모든 인덱스를 순회할 때까지 함수호출
    if idx < len(lst):
        # 해당 인덱스의 값, value에 저장
        value = lst[idx]
        # 만약 value 값이 없으면
        if value is None:
            # 재귀함수 종료
            return
        
        # parent에 현재 노드 저장
        parent = TreeNode(value)
        # parent의 left와 right로 새 노드를 저장하면서, 재귀함수 호출
        parent.left = make_tree_by(lst, 2*idx+1)
        parent.right = make_tree_by(lst, 2*idx+2)
        
    # 배열의 모든 인덱스를 순회하고 나면, 루트 반환하면서 함수 종료
    return parent

재귀함수를 통한, 이진트리의 구현 코드이다. 배열을 가지고 만든 트리이기 때문에 당연스레, 트리를 배열의 형태로 반환하는 코드도 구현 가능하다. 어떤 순서로 배치하고 싶은지에 따라, DFS나 BFS를 응용하면 쉽게 구현이 가능하다.

마무리

언젠가는 내 눈에도 푸른 상록수처럼 보일테지