Notice
Recent Posts
Recent Comments
Link
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Tags
more
Archives
Today
Total
관리 메뉴

Nonamed Develog

[TIL][240729] Tree 본문

WHAT I LEARN/TIL

[TIL][240729] Tree

노네임드개발자 2024. 7. 29. 18:40
새로 알게 된 점은 무엇인가?

계층형 자료구조의 특징

  • Originated from one source.
  • One node is propagated into several nodes.
    *propagate: to produce a new plant using a parent plant.
  • No cycle path.

트리 Tree

비선형 구조. 원소 간 계층 관계를 가지며, 상위 원소에서 하위 원소로 내려가면서 확장되는 "나무 모양" 구조

  • There is a special designated node call the root.
  • Every pairs of connected nodes are in parent-child relationship.
  • There is no cycle in the nodes.
  • Reculsively defined self-referential date structure

용어 정리

  • Node(or Vertex): 트리를 구성하는 기본 요소
  • Edge: 간선. 노드와 노드 간의 연결(드물게 root와 leaf 사이의 모든 노드를 일컫기도 함)
  • Root node: 트리의 꼭대기에 있는 노드
  • Leaf node: 더 이상 자 노드가 없는 최하위 노드 
  • Internal node: 적어도 하나의 자식이 있는 노드
  • Parent node: 해당 노드 바로 위에 있는 부모 노드
  • Child node: 해당 노드 바로 아래에 있는 자식 노드
  • Sibling node: 같은 부모를 갖는 노드들의 집합
  • Ancester node: 간선을 따라 루트 노드까지 가는 경로상에 있는 모든 노드
  • Descendent node: 루트 노드로부터 간선을 따라 특정 노드까지 경로상에 있는 모든 노드
  • Subtree: 주어진 노드의 모든 하위 목록. 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
  • Degree of a node: 특정 노드가 가지고 있는 자식 노드의 수(차수)
  • Degree of tree: 트리 내에 있는 노드들의 차수 중 가장 큰 값
  • Depth of a node(Level): 루트에서 특정 노드까지의 간선의 수
  • Depth of a tree: 루트에서 가장 깊은 노드까지의 간선 수
  • Width of a tree: 각 레벨에서 노드의 최대 노드 

이진트리 Binary Tree

  • A tree whose degree is 2
  • The maximum degree of its node is 2
  • n개의 노드 가질 때 간선의 수? ➡️ n-1
  • i번째 레벨의 최대 노드 수?
    ➡️ 2^(i-1)(root level이 1인 경우) / 2^i(root level이 0인 경우) - O(N)
  • 깊이가 k인 이진트리의 최대 노드 수?
    ➡️ 2^k-1(root level이 1인 경우) / 2^(k+1)-1(root level이 0인 경우) - O(logN)
  • 깊이가 k인 이진 트리의 최소 노드 수? ➡️ k+1

이진 트리의 종류

번역보다 학술용어로 기억하는 것이 더 편하다.

  • 정 이진 트리 Full Binary Tree
    - 모든 노드가 0개 또는 2개의 자식 노드를 갖는다.
    - 노드의 수 = 2^(depth) - 1
  • 완전 이진 트리 Complete Binary Tree
    - 마지막 레벨을 제외한 모든 노드가 가득 차야 한다.
    - 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽은 채워져야 한다.
  • 포화 이진트리(Perfect Binary Tree)
    - Full Binary Tree 이자 Perfect Binary Tree
    - 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있다.

이진 트리 순회

  • Search(*탐색) == Traversal(*순회)
    - 어떤 값이 주어졌을 때 해당 값이 일치하는 노드가 있는지 탐색(모든 노드를 확인해야 함)
  • DFS(Depth-First Search): 트리의 한 경로를 끝까지 탐색한 후 다른 경로를 탐색한다.
    - 스택(stack) 또는 재귀(recursion)를 이용하려 구현할 수 있다.
  • 3가지 순회하는 방법이 존재한다. (Preorder / Inorder / Postorder)

이 트리를 순회해보자!

  • 트리의 구조: 3가지 순회 방법에 앞서 트리의 구조를 구현하면 아래와 같다.
class Node(object):
    def __init__(self, item):
        self.item = item  # 루트(노드)가 갖는 값을 저장
        self.left = self.right = None  # 각 루트의 자식 노드
        
class BinaryTree(object):
    def __init__(self):  Node 원소를 초기화
        self.root = None  # 빈 루트
  •  전위 순회 Preorder Traversal: 루트 ➡️ 왼쪽 ➡️ 오른쪽
def preorder(self):
        def _preorder(node):
            print(node.item, end=' ')  # 제일 먼저 루트를 프린트한다.
            if node.left:
                _preorder(node.left)
            if node.right:
                _preorder(node.right)
        _preorder(self.root)

순회: 1-2-4-8-5-3-6-7

  • 중위 순회 Inorder Traversal: 왼쪽 ➡️ 루트 ➡️ 오른쪽
def inorder(self):
    def _inorder(node):
        if node.left:
            _inorder(node.left)
        print(node.item, end=' ')  # 중간에 프린트가 있다
        if node.right:
            _inorder(node.right)
    _inorder(self.root)

순회: 8-4-2-5-1-6-3-7

  • 후위 순회 Postorder Traversal: 왼쪽 ➡️ 오른쪽 ➡️ 루트
def postorder(self):
    def _postorder(node):
        if node.left:
            _postorder(node.left)
        if node.right:
            _postorder(node.right)
        print(node.item, end=' ')  # 마지막 프린트
    _postorder(self.root)

순회: 8-4-5-2-6-7-3-1

  • 레벨 순회 Level Traversal
    - BFS(Breadth-First Search)로 트리를 레벨순으로 노드를 방문하는 방법
    - 큐(Queue)를 이용해 구현할 수 있다.
from collections import deque

def levelorder(self):
    q = deque([self.root])
    while q:
        node = q.popleft()
        print(node.item, end=' ')
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

순회: 1-2-3-4-5-6-7-8


무엇을 느꼈고 내일은 무엇을 할까?

과제로 나온 트리 순회 문제를 풀이 후 리스트를 이용해 2진 트리 구현