카테고리 없음

[코딩 테스트 합격자 되기 - 6주차] 트리(Tree)

난쟁이 개발자 2024. 2. 10. 20:01
반응형

프로그래밍 분야에서 트리는 계층 구조를 표현하는 용도로 많이 사용됨.

  • 인공지능 : 인공지능의 판단 기준을 만들 때 의사 결정 트리를 사용. 이를 통해 외부에서 입력된 데이터를 분류하거나 상황을 예측하는 모델을 만들 수 있음.
  • 자동 완성 기능 : 트리는 문자열 처리에도 많이 활용됨. 검색 엔진에서 자동 검색어 추천 기능도 트리 구조를 활용한 것.
  • 데이터베이스 : 데이터를 쉽게 검색, 삽입, 삭제할 수 있도록 트리를 활용해서 데이터를 구조화하고 인덱싱함.

트리는 나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤집어 놓은 모양. 따라서 밑둥(root)는 맨 위에 있음.

파이썬 알고리즘 인터뷰

노드(Node)

  • 트리를 구성하는 기본 요소
  • 노드에는 데이터와 하위 노드에 대한 참조를 가지고 있다.(연결리스트와 유사하다.)
  • 그래프에서 정점과 비슷한 개념이다.

간선(Edge)

  • 노드와 노드를 잇는 선

루트 노드(Root Node)

  • 부모를 가지고 있지 않은 트리에서 최상위에 위치한 노드

부모 노드(Parent Node)

  • 자식을 가진 노드로써, 한 노드에 대해 상위에 있는 노드이다

자식 노드(Child Node)

  • 부모 노드의 하위 노드

형제 노드(Sibling Node)

  • 같은 부모를 가지는 노드.

리프 노드(Leaf Node) = 외부 노드(External Node) = 단말 노드(Terminal node)

  • 자식 노드를 가지고 있지 않은 노드.

내부 노드(Internal Node)

  • 리프 노드와 반대로 자식을 하나 이상 가진 노드

깊이(Depth)

  • 루트 노드에서 해당 노드까지 도달하는데 사용되는 간선의 수

높이(Height)

  • 루트 노드에서 리프 노드까지의 거리
  • 그 중 가장 큰 값이 트리의 높이이다.

레벨(Level)

  • 루트를 0으로 하여 아래로 내려갈수록 +1이 된다.

차수(Degree)

  • 노드의 자식 노드의 수

넓이(Width)

  • 레벨에 있는 노드 수

 

이진 트리

배열이나 포인터로 구현할 수 있다. 이진 트리는 최대 2개의 자식 노드를 갖는다. 

 

배열로 표현하기

배열 - 선형 자료구조

트리 - 계층 자료구조

  • 루트 노드는 배열 인덱스 1번에 저장
  • 왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 X 2 
  • 오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 X 2 + 1

이진트리 순회하기

순회란 어떤 데이터가 있을 때 그 데이터를 빠짐 없이 방문하는 것을 의미한다. 트리에서 데이터를 검색하려면 트리를 순회할 수 있어야 한다. 총 순회 방법은 3가지 방법이 존재한다. 

  • 전위순회(preorder) : 현재 노드를 부모 노드로 생각했을 때 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 방문
  • 중위 순회(inorder) : 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순으로 방문
  • 후위 순회(postorder) : 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드 순으로 방문

이진 트리 탐색하기

이진 트리에서 가장 중요한 것은 바로 탐색을 효율적으로 할 수 있도록 트리를 구축하는 것.

 

이진 탐색 트리 구축하기

이진 탐색 트리는 데이터 크기를 따져 크기가 작으면 왼쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치하는 독특한 정렬 방식을 가짐.

 

이진 탐색 트리의 시간 복잡도

이진 탐색 트리의 시간 복잡도는 트리 균형에 의존한다. 트리의 균형이 잡혔다는 건 각 노드의 차수가 비슷하게 유지되면서 각 노드의 자식 노드 수가 비슷하게 유지되는 것을 말한다. 균형이 유지되었다고 가정했을 때 삽입과 탐색 연산 시 이진 탐색 트리에 저장된 노드가 N개 라고 하면 시간 복잡도는 O(logN)이다. 

트리 순회하기 - 백준(1991)

더보기 
from typing import *
import sys
sys.stdin = open('input.txt', 'r')

N = int(input())
tree = {}

for n in range(N) :
    root, left, right = map(str, input().split())
    tree[root] = [left, right]


def preorder(root) :
    if root != '.' :
        print(root, end='')
        preorder(tree[root][0])
        preorder(tree[root][1])

def inorder(root) :
    if root != '.' :
        inorder(tree[root][0])
        print(root, end='')
        inorder(tree[root][1])


def postorder(root) :
    if root != '.' :
        postorder(tree[root][0])
        postorder(tree[root][1])
        print(root, end='')


preorder("A")    # ABDCEFG
print()
inorder("A")    # DBAECFG
print()
postorder("A")    # DBEGFCA

'''
7
A B C
B D .
C E F
E . .
F . G
D . .
G . .
'''

이진 트리 순회하기 - 문제 27번 (코딩 테스트 합격자 되기 파이썬편 p.292)

더보기 
# 노드 클래스 정의
class Node :
    # 노드 클래스 생성자
    def __init__(self, key) :
        self.left = None
        self.right = None
        self.val = key

# 이진 탐색 트리 클래스
class BST :
    # 초기에 아무 노드도 없는 상태
    def __init__(self) :
        self.root = None

    # 루트 노드부터 시작해서 이진 탐색 트리 규칙에 맞는 위치에 새 노드 삽입
    def insert(self, key) :
        # 루트 노드가 없는 경우 새로운 노드를 루트 노드로 추가
        if not self.root :
            self.root = Node(key)
        else :
            curr = self.root
            while True :
                # 삽입하려는 값이 현재 노드의 값보다 작은 경우 왼쪽 자식 노드로 이동
                if key < curr.val :
                    if curr.left :
                        curr = curr.left
                    else :
                        # 현재 노드의 왼쪽 자식 노드가 없는 경우 새로운 노드 추가
                        curr.left = Node(key)
                        break
                else :
                    # 삽입하려는 값이 현재 노드의 값보다 큰 경우 오른쪽 자식 노드로 이동
                    if curr.right :
                        curr = curr.right
                    else :
                        # 현재 노드의 오른쪽 자식 노드가 없는 경우 새로운 노드 추가
                        curr.right = Node(key)
                        break
    # 이진 탐색 규칙에 따라 특정값이 있는지 확인(루트 노드부터 시작)
    def search(self, key) :
        curr = self.root
        # 현재 노드가 존재하고, 찾으려는 값과 현재 노드의 값이 같지 않은 경우 반복
        while curr and curr.val != key :
            # 찾으려는 값이 현재 노드의 값보다 작은 경우 왼쪽 자식 노드로 이동
            if key < curr.val :
                curr = curr.left
            else :
                # 찾으려는 값이 현재 노드의 값보다 큰 경우 오른쪽 자식 노드로 이동
                curr = curr.right
        return curr

# lst에 있는 데이터를 활용하여 이진 탐색 트리 생성, search_lst 원소 탐색
def solution(lst, search_lst) :
    bst = BST()
    # 리스트의 각 요소를 이용하여 이진 탐색 트리 생성
    for key in lst :
        bst.insert(key)
    result = []
    # 검색 리스트의 각 요소를 이진 탐색 트리에서 검색하고, 검색 결과를 리스트에 추가
    for search_val in search_lst :
        if bst.search(search_val) :
            result.append(True)
        else :
            result.append(False)
    return result

 

반응형