💡Tree
📌Tree 개념
- 데이터의 상-하 관계(=계층적 관계)를 저장하는 자료구조
- 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아있다고 해서 트리 구조라고 함
- 컴퓨터 폴더 구조 등이 트리 구조의 예시에 해당
- 데이터를 순차적으로 나열한 선형 구조가 아니라, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있으므로 비선형 구조에 해당
- 계층적으로 표현이 되고 아래로만 뻗어나가므로 사이클 없음
- 여러 개의 정점으로 구성되어 있으며, 트리는 하위 관계가 있는 정점들을 가리키는 래퍼런스를 가지며 보통 이 래퍼런스를 화살표로 나타냄
- 상-하 관계로 나누어졌을 때 상에 해당하는 정점을 부모노드, 하에 해당하는 정점을 자식노드라고 표현하며,
이렇게 나뉜 상-하 관계를 부모-자식 관계라고 표현하기도 함
- 트리 구조에서 최상단에 존재하는 정점을 나무의 뿌리에 빗대어 root 노드라고 한다.
📌Tree 용어
Root노드
- 트리의 시작 노드로 즉, 뿌리가 되는 노드
- 보통 트리를 표현할 때 최상단에 존재
부모 노드
자식 노드
- 특정 노드의 직속 하위 노드로, 부모 노드와 반대되는 개념
형제노드
Leaf 노드
- 자식 노드를 가지고 있지 않은, 가장 말단에 있는 노드
- 트리의 끝에 있다고 하여 Root 노드와 반대로 Leaf 노드라고 표현
깊이
- 특정 노드가 Root 노드로부터 떨어져있는 거리
레벨
- 깊이 + 1
- 깊이와 거의 똑같은 개념으로, 특정 깊이인 노드들을 묶어서 표현할 때 사용하는 용어
높이
부분 트리
- 현재 트리의 일부분을 이루고 있는 더 작은 트리
- 하나의 전체 트리에는 여러 개의 부분 트리들이 존재하기도 함
📌Tree 활용
- 데이터 사이의 계층적 관계를 컴퓨터에서 나타낼 수 있도록 해주는 자료구조가 트리
- 정렬이나 압축과 같은 컴퓨터 과학의 다양한 문제들을 해결하는 데에 트리 구조가 유용
- 딕셔너리, 우선순위 큐, 세트 등 다양한 추상 자료형을 구현하는 데에 사용가능
📌Tree 순회
- 자료구조에 저장된 데이터를 하나씩 다 도는 것을 말함
- 트리를 순회할 때는 주로 재귀를 사용
- 트리 순회의 기본 동작 3가지
- 재귀적으로 왼쪽 부분트리 순회
- 재귀적으로 오른쪽 부분트리 순회
- 현재 노드의 데이터를 출력
pre-order
- 두 개의 부분트리 순회전에 노드의 데이터를 출력하는 순회방법
- 트리 순회의 기본 동작 3가지를 아래와 같은 순서로 진행
- 현재 노드의 데이터를 출력
- 재귀적으로 왼쪽 부분트리 순회
- 재귀적으로 오른쪽 부분트리 순회
post-order
- 두 개의 부분트리 순회 후에 노드의 데이터를 출력하는 순회방법
- 트리 순회의 기본 동작 3가지를 아래와 같은 순서로 진행
- 재귀적으로 왼쪽 부분트리 순회
- 재귀적으로 오른쪽 부분트리 순회
- 현재 노드의 데이터를 출력
in-order
- 데이터를 출력하는 동작이 두 개의 부분트리들을 순회하는 동작들 사이에 끼어있는 순회방법
- 트리 순회의 기본 동작 3가지를 아래와 같은 순서로 진행
- 재귀적으로 왼쪽 부분트리 순회
- 현재 노드의 데이터를 출력
- 재귀적으로 오른쪽 부분트리 순회
📌Tree 구현
class Tree {
constructor(value) {
this.value = value;
this.children = [];
}
insertNode(value) {
const childNode = new Tree(value);
this.children.push(childNode);
}
contains(value) {
if(this.value === value) {
return true;
}
for (let i = 0; i < this.children.length; i += 1) {
const childNode = this.children[i];
if (childNode.contains(value)) {
return true;
}
}
return false;
}
}