트리

데이터의 계층 관계를 저장하는 자료구조이다.

여기서 계층은 상 - 하 관계에 해당 하는 데이터이다.

 

 

트리는 앞선 배열, 링크드리스트와 같은 선형 자료구조가 아닌 비선형 자료구조이다.

(트리를 순회하는 과정에서 선형 자료구조와 같이 데이터를 출력할 수 도 있다.)

링크드리스트와 같이 노드 라는 객체 단위의 데이터를 사용하여 관계를 저장한다.

 

트리에서의 노드는 하위 관계가 있는 노드들을 가르키는 레퍼런스를 갖는다.

class Node:
    """트리 노드를 나타내는 클래스"""

    def __init__(self, data):
        """트리 노드는 데이터와 두 자식 노드에 대한 레퍼런스를 갖는다"""
        self.data = data
        self.left_child = None
        self.right_child = None

---

트리 용어

- 루트 노드

트리의 시작(뿌리)가 되는 노드를 말함. (최상위 노드)

- 부모 노드

특정 노드의 직속 상위 노드

- 자식 노드

특정 노드의 직속 하위 노드

- 형제 노드

같은 부모를 갖는 노드

- leaf 노드(잎/말단)

자식 노드를 가지고 있지 않은 가장 하위 노드, 트리의 끝에 있다고해서 leaf(잎) 노드라고 부른다.

- 깊이

특정 노드가 루트 노드와 얼마나 떨어져 있는지에 대한 거리를 나타내는 지표.

- 레벨

깊이 + 1 로 깊이와 같은 개념으로 깊이에 1을 더해 특정 깊이의 노드를 묶어서 표현할 때 주로 사용한다.

(레벨1에 있는 노드들 : 깊이 2를 가지고 있는 노드를 말함)

- 높이

트리에서 가장 깊이 있는 노드의 깊이이다. (위의 깊이와는 다름)

- 부분 트리 (Sub_tree)

현재 트리의 일부분을 이루고 있는 더 작은 트리를 말함.

왼쪽 부분 트리, 오른쪽 부분 트리 등

---

이진 트리 (Binary_Tree)

각 노드가 최대 2개의 자식 노드만 가질 수 있는 트리

모든 노드가 2개, 1개, 0개의 자식 노드만 가지고 있다.

노드를 생성하고 각 노드를 연결하여 이진 트리를 구현할 수 있다.

---

이진 트리의 종류

1. 정 이진 트리 (Full_Binary_Tree)

2. 완전 이진 트리(Complete_Binary_Tree)

3. 포화 이진 트리 (Prefect_Binary_Tree)

4. 이진 탐색 트리 (Binary_Search_Tree) => 추후 포스팅 예정.

---

1. 정 이진 트리 (Full_Binary_Tree)

모든 노드가 2개 또는 0개의 자식을 갖는 이진 트리

---

2. 완전 이진 트리(Complete_Binary_Tree)

마지막 레벨의 직전 레발까지 모든 노드가 다 채워진 트리

이때, 조건 마지막 레벨에서는 노드가 다 채워질 필요가 없지만 왼쪽부터 오른쪽 방향으로 노드들이 채워져야 함.

 

완전 이진 트리에서의 높이

완전 이진 트리 안에 저장된 노드의 개수를 N이라 하면 높이는 항상 lg(N)에 비례한다.

최소한 현재 노드 수보다 노드 수가 2배 이상이 되었을 때 높이도 하나 더 올라간다는 것을 알 수 있다.

이 내용을 정리하면 완전 이진 트리의 높이는 결국 O(lg(N))라고 할 수 있습니다.

이건 완전 이진 트리의 속성에서 아주 중요한 내용이니 꼭 기억하도록 하자.

완전 이진 트리라고 할 수 없는 트리!

---

3. 포화 이진 트리 (Prefect_Binary_Tree)

모든 레벨에서 노드가 완벽하게 다 채워져있는 이진 트리

포화 이진 트리는 정 이진트리와 완전 이진트리의 특성을 모두 가지며

높이에 따라 노드의 수가 고정되기 때문에 그 높이나 노드의 수 둘 중 하나만 알아도 나머지 하나의 값을 바로 구할 수 있는 특성이 있다.

 

 

---

완전 이진 트리 => 파이썬의 리스트 자료구조로 구현하기

완전 이진 트리의 2가지 특성을 이용해 파이썬 리스트로 구현을 할 수 있다.

• - 마지막 레벨 직전의 레벨까지는 노드들로 가득 차 있음
• - 마지막 레벨은 왼쪽에서 오른쪽 방향으로 노드들로 가득 차 있어야 함(오른쪽은 비어있어도 되지만 왼쪽은 비어있으면 안 됨)

0번째 인덱스를 None으로 시작하여 1번째 인덱스를 루트노드로 왼쪽에서 오른쪽 방향 순으로 차례대로 리스트로 저장한다.

 

---

위와 같이 리스트로 저장하여 완전 이진 트리에서 특성을 이용하여

부모 노드를 찾거나 자식 노드를 찾는 탐색을 구현할 수 있다.

1. 자식 노드 찾기

2번째 노드(노드 5)의 왼쪽 자식 노드를 찾는 예를 보자

특정 부모의 왼쪽 또는 오른쪽 자식 녿드를 찾고 싶을때 부모 노드가 저장된 인덱스에 2를 곱해준 값을 인덱스로 생각하여 리스트에서 원하는 인덱스 값을 찾으면 왼쪽, 오른쪽 자식 노드를 찾을 수 있다.

왼쪽 자식 노드 => 인덱스 * 2

오른쪽 자식 노드 => 인덱스 * 2 + 1 위치에 위치하고 있음을 알 수 있다!

0의 경우 인덱스가 음수로 주어질 경우 None을 반환하기 위해 추가하였다.

def get_left_child_index(complete_binary_tree, index):
    """배열로 구현한 완전 이진 트리에서 index번째 노드의 왼쪽 자식 노드의 인덱스를 리턴하는 함수"""
    # 코드를 쓰세요
    number = index * 2
    if 0 < number < len(complete_binary_tree):
        return number
    return None

def get_right_child_index(complete_binary_tree, index):
    """배열로 구현한 완전 이진 트리에서 index번째 노드의 오른쪽 자식 노드의 인덱스를 리턴하는 함수"""
    # 코드를 쓰세요
    number = (index * 2) + 1
    if 0 < number < len(complete_binary_tree):
        return number
    return None

---

2. 부모 노드 찾기

비슷한 방식으로 주어진 인덱스에서의 부모 노드를 찾을 수도 있다.

부모 노드 => 인덱스 // 2 

0의 경우 인덱스가 음수로 주어질 경우 None을 반환하기 위해 추가하였다.

def get_parent_index(complete_binary_tree, index):
    """배열로 구현한 완전 이진 트리에서 index번째 노드의 부모 노드의 인덱스를 리턴하는 함수"""
    # 코드를 쓰세요
    number = index // 2

    if 0 < number < len(complete_binary_tree):
        return number
    return None

---

트리 순회

자료구조의 저장된 모든 데이터를 도는 것을 순회 라고 하는데, 

이전까지의 선형 자료구조에서는 앞 뒤 라는 순서에 대한 정보를 가지고 있었지만

트리에서는 이러한 계층 관련 정보가 저장되어 있으며, 재귀함수로 순회를 한다.

트리 자료구조에서 순회하여 데이터를 모두 출력해보는 방법을 알아보자.

 

트리에서는 순회의 기본적인 3가지 동작이 있다.

- 재귀적으로 왼쪽 부분 트리 순회

- 재귀적으로 오른쪽 부분 트리 순회

- 현재 노드 데이터 출력

이 3가지 동작을 어떻게 조합하느냐에 따라 순회 방식이 달라진다.

---

트리의 3가지 순회 방식

1. Pre_order

2. Post_order

3. In_order 

비선형 자료구조인 트리도 순회를 하면 앞과 뒤라는 선형적인 순서를 만들 수 있다.

트리의 노드들을 어떤 방식으로 저장하고 어떤 방식으로 순회하는지에 따라 선형적 관계를 만들고 이를 활용할 수 있다.

아래의 트리를 예시로 알아보도록 하자!

 

---

1. Pre_order

pre : ~ 하기 전에 라는 뜻의 접두사로 

부분 트리 순회를 하기 전에 현재 노드를 출력하는 순회 방식이다.

1번 현재 노드 데이터 출력

2번 재귀적으로 왼쪽 부분 트리 순회

3번 재귀적으로 오른쪽 부분 트리 순회

def traverse_preorder(node):
    """pre-order 순회 함수"""
    if node is not None:
        print(node.data)  # 데이터 출력
        traverse_preorder(node.left_child)  # 재귀적으로 왼쪽 부분 트리 순회
        traverse_preorder(node.right_child)  # 재귀적으로 오른쪽 부분 트리 순회
       

---

2. Post_order

post : ~ 한 후에 라는 뜻의 접두사로

부분 트리 순회를 한 후에 현재 노드를 출력하는 순회 방식이다.

1번 재귀적으로 왼쪽 부분 트리 순회

2번 재귀적으로 오른쪽 부분 트리 순회

3번 현재 노드 데이터 출력

def traverse_postorder(node):
    """post-order 순회 함수"""
    if node is not None:
        traverse_postorder(node.left_child)  # 재귀적으로 왼쪽 부분 트리 순회
        traverse_postorder(node.right_child)  # 재귀적으로 오른쪽 부분 트리 순회
        print(node.data)  # 데이터 출력

---

3. In_order 

in : ~ 안에 라는 뜻의 접두사로

부분 트리 순회하는 사이에 현재 노드를 출력하는 순회 방식이다.

1번 재귀적으로 왼쪽 부분 트리 순회

2번 현재 노드 데이터 출력

3번 재귀적으로 오른쪽 부분 트리 순회

def traverse_inorder(node):
    """in-order 순회 함수"""
    if node is not None:
        # node.left_child 의 결과로 None을 반환할경우 node is None이되어 아무것도 실행되지 않은 상태로 
        # 아래 재귀함수를 빠져놔와 print('2')를 실행한다.
        traverse_inorder(node.left_child)
        print(node.data)
        traverse_inorder(node.right_child)

 

 

출처 : 코드 잇(자료구조)

자료 구조 | 코드잇 (codeit.kr)