[자료구조] 트리

트리

트리란 상하 관계가 존재하는 자료구조이다.

 

링크드 리스트와 비슷하게 트리도 노드들을 가진다.
단, 각 노드는 데이터 정보뿐만 아니라, 자식에 대한 레퍼런스를 가진다.

 

이를 통해 계층적 구조를 구현할 수 있게 되어 다양한 컴퓨터과학의 문제를 해결할 수 있다.
물론, 트리도 자료구조이기 때문에 여러 추상 자료형을 구현할 수 있다.

 

트리구조 용어

• root 노드 : 가장 상위의, 즉 뿌리가 되는 노드
• 부모노드 : 어떤 노드의 직속 상위 노드
• 자식 노드 : 어떤 노드의 직속 하위 노드
• 형제 노드 : 같은 부모 노드를 가지는 노드
• leaf노드 : 어떤 자식도 갖지 않는, 즉 잎이 되는 노드
• 깊이(레벨) : root노드로부터 떨어진 거리(레벨은 깊이+1)
• 높이 : 가장 깊이 있는 노드(leaf노드)의 깊이
• 부분 트리 : 어떤 트리에서 일부분을 떼어낸 트리

이진트리

각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리. right chlid와 left child 두 개의 자식노드를 가진다. 구현이 용이해 트리의 개념을 이해하기 쉽다.

 

이진트리에도 종류가 있는데,

• 모든 노드가 0개 혹은 2개의 자식을 갖는 전 이진트리(Full binary tree)
• 모든 노드가 2개의 자식을 갖고, 마지막 레벨에서만 왼쪽에서 오른쪽으로 노드가 순차적으로 채워져 있는 완전 이진트리(Complete binary tree) (마지막 레벨은 모두 채워지지 않아도 된다.)
• 마지막으로 leaf node를 제외하고는 모두 2개의 자식을 가지는포화 이진트리(perfect binary tree)가 있다.

이진트리에서 높이와 노드갯수의 상관관계

여기서 완전 이진트리는 트리 안에 저장된 노드가 n개일 때 높이는 lg(n)에 비례한다. 왜냐하면 노드의 개수는 높이에 따라 정비례하는 모습을 보이는데 이는 1+2+4+... 와 같이 나타난다. 따라서 h의 높이를 가진 트리는 최소 (1+2+4+…+2^(h-1)+1)에서 최대 (1+2+4+...+2^h)의 노드 개수를 가진다. (트리를 직접 그려보면 이해가 빠르다.)

 

여기서 노드 개수를 n이라고 하면 노드와 높이의 관계는 '2^h <=n <=2^(h+1) 여기서 각 항에 lg를 취하면 h <=lg(n)<h+1의 즉, 노드 수가n개인 완전 이진트리의 높이는h<=lg(n)h <=lg(n)를 만족하는 정수 중 최대의 정수가 된다.

 

cf. 포화 이진트리의 높이는n=2^(h+1)−1의 관계식을 갖는다.

완전이진트리의 구현

완전 이진트리는 리스트로도 간단하게 구현할 수 있는데, 초기 설정은 [None, root노드,...]이다. 여기서 만약 특정 노드에서 왼쪽 자식에게 접근하고 싶으면 (현재 노드의 인덱스*2)를 해주면 된다. 오른쪽 자식에게 접근하고 싶으면 (현재 노드의 인덱스*2+1)을 해주면 된다.

 

(예 : 2번 노드에서 왼쪽 자식 접근 시 2*2 => 4번 노드로 접근
2번 노드에서 오른쪽 자식 접근 시 2*2+1 => 5번 노드로 접근)

 

참고로 부모 노드는 나누기의 몫으로 찾을 수 있다.

이진트리구현의 예

class Node:
    """이진 탐색 트리 노드 클래스"""

    def __init__(self, data):
        self.data = data
        self.parent = None
        self.right_child = None
        self.left_child = None


def print_inorder(node):
    """주어진 노드를 in-order로 출력해주는 함수"""
    if node is not None:
        print_inorder(node.left_child)
        print(node.data)
        print_inorder(node.right_child)


class BinarySearchTree:
    """이진 탐색 트리 클래스"""

    def __init__(self):
        self.root = None

    def search(self, data):
        """이진 탐색 트리 탐색 메소드, 찾는 데이터를 갖는 노드가 없으면 None을 리턴한다"""
        now_node = self.root
        while now_node is not None:
            if now_node.data == data:
                break
            elif now_node.data > data:
                now_node = now_node.left_child
            elif now_node.data < data:
                now_node = now_node.right_child
        return now_node

    def insert(self, data):
        """이진 탐색 트리 삽입 메소드"""
        new_node = Node(data)  # 삽입할 데이터를 갖는 노드 생성

        # 트리가 비었으면 새로운 노드를 root 노드로 만든다
        if self.root is None:
            self.root = new_node
            return

        temp = self.root  # 저장하려는 위치를 찾기 위해 사용할 변수. root 노드로 초기화한다

        # 원하는 위치를 찾아간다
        while temp is not None:
            if data > temp.data:  # 삽입하려는 데이터가 현재 노드 데이터보다 크다면
                # 오른쪽 자식이 없으면 새로운 노드를 현재 노드 오른쪽 자식으로 만듦
                if temp.right_child is None:
                    new_node.parent = temp
                    temp.right_child = new_node
                    return
                # 오른쪽 자식이 있으면 오른쪽 자식으로 간다
                else:
                    temp = temp.right_child
            else:  # 삽입하려는 데이터가 현재 노드 데이터보다 작다면
                # 왼쪽 자식이 없으면 새로운 노드를 현재 노드 왼쪽 자식으로 만듦
                if temp.left_child is None:
                    new_node.parent = temp
                    temp.left_child = new_node
                    return
                # 왼쪽 자식이 있다면 왼쪽 자식으로 간다
                else:
                    temp = temp.left_child

    def print_sorted_tree(self):
        """이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
        print_inorder(self.root)  # root 노드를 in-order로 출력한다

(by. python)

---

순회

자료구조에 저장된 데이터를 하나씩 다 돌아보는 것을 순회라고 한다.

기본적으로 트리의 순회는

1. root트리 기준으로 왼쪽 트리를 순회
2. root트리 기준으로 오른쪽 트리를 순회
3. 현재의 노드 데이터를 출력 (혹은 원하는 작업)

이렇게 3가지 단계로 구성이 가능하다.
이 순서에 따라 다양한 순회 방식이 존재한다. 먼저 pre-order 순회는

1. 노드 데이터 출력
2. 왼쪽 트리 순회
3. 오른쪽 트리 순회

의 단계를 가지는데, 이렇게 할 경우 데이터 출력은

[(부모 데이터), (왼쪽 트리 데이터들), (오른쪽 트리 데이터들)] 순서로 출력된다.
순서는 재귀적으로 이뤄짐을 상기하자.

 

다음으로 post-order 순회는

1. 왼쪽 트리 순회
2. 오른쪽 트리 순회
3. 노드 데이터 순회

의 단계를 가진다. 이 경우 데이터의 출력 순서는

[(왼쪽 트리의 데이터들) , (오른족 트리의 데이터들), (부모데이터)] 가 된다.
순서는 재귀적으로 이뤄짐을 상기하자.

 

다음으로 in-order 순회는

1. 왼쪽 트리 순회
2. 노드 데이터 출력
3. 오른쪽 트리 순회

의 단계를 가진다. 이 경우 데이터 출력의 순서는

[(왼쪽트리의 데이터들), (부모 데이터), (오른쪽 트리의 데이터들)] 가 된다.
순서는 재귀적으로 이뤄짐을 상기하자.

 

순회가 중요하고 유용한 이유는 트리에서도 데이터(노드) 간의 선형적 관계를 만들 수 있기 때문이다.