[D-10] 트리 알아보기 & 트라이

📍 트리(tree)

트리(tree)는 노드와 에지로 연결된 그래프의 특수한 형태이다.

 

✅ 특징

순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다.
루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.
트리의 부분 트리(subtree) 역시 트리의 모든 특징을 따른다.

 

✅ 구성 요소

구성 요소	설명
노드	데이터의 index와 value를 표현하는 요소
에지	노드와 노드의 연결 관계를 나타내는 선
루트 노드	트리에서 가장 상위에 존재하는 노드
부모 노드	두 노드 사이의 관계에서 상위 노드에 해당하는 노드
자식 노드	두 노드 사이의 관계에서 하위 노드에 해당하는 노드
리프 노드	트리에서 가장 하위에 존재하는 노드 (자식 노드가 없는 노드)
서브 트리	전체 트리에 속한 작은 트리

이미지 출처 : 나무위키, 트리 알고리즘 (https://namu.wiki/w/%ED%8A%B8%EB%A6%AC%28%EA%B7%B8%EB%9E%98%ED%94%84%29)

---

✅ 트리의 부모 찾기_백준11725

1. 인접 리스트로 트리 데이터를 구현한다.
2. DFS 탐색을 수행한다. 수행할 때는 부모 노드의 값을 정답 배열에 저장한다.
3. 정답 배열의 2번 인덱스부터 값을 차례대로 출력한다.

---

📍 트라이(trie)

문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조이다.
단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행한다.

 

✅ 핵심 이론

N진 트리 : 문자 종류의 개수에 따라 N이 결정된다. 예를 들어 알파벳은 26개의 문자로 이뤄져 있으므로 26진 트리로 구성된다.
루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지한다.

 

이미지 출처 : Training Ouputs, 트라이 (https://baek.dev/til/data-structure/trie)

✅ 특징

루트 노드는 공백을 유지한다.
노드는 기본적으로 N개의 공백 노드를 자식으로 가진다.
다음 단어를 삽입할 때는 루트 노드에서부터 검색한다.
검색 노드가 공백 상태일 경우 신규 노드를 생성하고, 공백 상태가 아니면 이동한다.
문자열의 마지막에 도달하면 리프 노드라고 표현한다.