트리(스캔 순서, 이진 검색 트리)

Devkty·2025년 3월 28일

크래프톤 정글(알고리즘 주차 WEEK 0 ~ 4)

목록 보기

28/58

트리

[참고 사이트]
https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
https://blog.encrypted.gg/1019
https://velog.io/@orcasuit/%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie
https://wikidocs.net/193702

데이터 사이의 계층 관계를 표현하는 트리 구조를 알아봅니다. 무방향이면서 사이클이 없는 연결 그래프입니다.

각 노드는 하나의 알파벳 문자를 가지고, 루트에서 임의의 노드까지 경로를 따라가면 해당 경로에 해당하는 문자열을 찾을 수 있습니다.

위와 같은 그림을 트리 구조라고 합니다.

용어

루트(root): 트리의 가장 위쪽에 있는 노드. 트리 하나당 1개 존재
리프(단말/외부 노드)(leaf): 가장 아래쪽에 있는 노드. 가장 밑에 위치한다는 의미가 아니라 가지가 더이상 뻗어갈 수 없는 마지막에 노드가 있다는 의미
비단말 노드(내부 노드)(non-terminal node): 리프를 제외한 노드.(루트까지)
자식(child): 어떤 노드와 가지가 연결 되었을 때 아래쪽 노드. 노드는 자식을 몇개라도 가질 수 있다. 당연하지만 가장 아래쪽 리프는 자식이 없다.
부모(parent): 어떤 노드와 가지가 연결되었을 때 위쪽에 있는 노드. 노드의 부모는 하나뿐.
형제(sibling): 부모가 같은 노드.
조상(ancestor): 어떤 노드에서 위쪽으로 따라가면 만나는 모든 노드.
자손(descendant): 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드.
레벨(level): 루트에서 얼마나 멀리 떨어져 있는지를 나타냄.
차수(degree): 각 노드가 갖는 자식의 수.
높이(height): 루트에서 가장 멀리 있는 리프까지의 거리. 리프 레벨의 최댓값
서브트리(subtree): 어떤 노드를 루트로 하고, 그 자손으로 구성된 트리.
빈 트리(None tree): 노드와 가지가 전혀 없는 트리

종류

순서 트리: 형제 노드의 순서관계가 있음.
무순서 트리: 형제 노드의 순서관계 없음.

특징

동적 집합 연산: 삽입, 삭제, 검색 등의 연산을 효율적으로 수행 가능
빠른 검색 속도: 문자열 검색에 보통 O(V)의 시간 복잡도를 가짐
접두어 검색: 접두어가 같은 문자열을 효율적으로 검색 가능
무방향이며 사이클이 없는 연결 그래프
사이클이 없는 연결 그래프이면서 임의의 간선을 추가하면 사이클이 생김
임의의 간선을 제거하면 연결 그래프가 아님
임의의 두 점을 연결하는 simple path가 유일한 그래프
V개의 장점을 가지고 V-1개의 간선을 가지는 Acycle(사이클 없는)그래프

문자열 검색, 자동완성, 문자열 집합 관리에 사용하면 효율적임.

트리 스캔 방법

여기서 노드를 스캔하는 방법은 크게 2가지 인데, 그것이 바로 BFS와 DFS이다.

트리 스캔 순서(전·중·후위)

스캔 순서에 따라 전위, 중위, 후위로 나뉜다. (아래 사진 순서의 주의)
이진 트리뿐 아니라 일반 트리도 사용한다.

전위 순회

노드방문 → 왼쪽 자식 → 오른쪽 자식

중위 순회

왼쪽 자식 → 노드 방문 → 오른쪽 자식

후위 순회

왼쪽 자식 → 오른쪽 자식 → 노드 방문

더 큰 크리는 밑에 그림을 참고하자.

파이썬에서의 트리 구현

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

이진트리

앞서 보여준 그림같이 노드가 왼쪽 자식과 오른쪽 자식 만을 갖는 트리를 이진트리라고 합니다.
두 개 이하의 자식 노드를 가지면 되므로 자식이 하나 없어도 이진 트리라고 합니다.

완전 이진트리

완전 이진 트리는 루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리를 완전 이진 트리라고 한다. 채우는 방식은 다음과 같다.
1. 마지막 레벨을 제외하고 모든 레벨에 노드가 가득 차 있다.
2. 마지막 레벨에 한해서 왼쪽부터 오른쪽으로 노드를 채우되 반드시 끝까지 채우지 않아도 된다.(오른쪽 노드는 비어도 된다)