📅 2025-11-03
➡️ 트리 알고리즘에 대해 새롭게 알게 된 것 또는 헷갈리는 부분 정리
🔎 학습 리마인드
📌 트리 (Tree)
💡 선형 구조
- 각 노드(또는 원소)가 앞뒤로 1:1 관계를 가지는 구조
- 데이터가 순차적으로 연결되어 있음
- 한 방향으로만 탐색 가능 (보통 앞 → 뒤)
💡 대표적인 선형 구조
배열 → 인덱스로 접근 가능한 연속적인 데이터 집합
연결 리스트 → 포인터로 노드를 연결한 비연속적 구조
스택 → 후입선출
큐 → 후입선출
📌 트리 자료구조
- 비선형 구조의 대표적인 형태로 계층적 관계를 표현할 때 사용
- 노드의 앞-뒤 관계가 1:N 또는 N:N
- 다수의 노드가 연결된 구조
- 하나의 노드가 다수의 하위 노드들을 참조할 수 있음. 다수의 노드가 하나의 상위 노드를 참조할 수 있음 → 비선형 구조의 특징을 가지고 있고 계층적인 자료 구조
📌 기본 구성 요소
- 노드(Node) : 트리의 기본 단위로, 데이터를 담고 있는 요소
- 루트(Root) : 트리의 최상단 노드이자 시작점 (예: A 노드)
- 엣지(Edge) : 노드와 노드를 연결하는 선
- 자식 노드(Child) : 어떤 노드의 하위에 있는 노드
- 리프(Leaf) : 자식이 없는, 가장 하위에 위치한 노드
💡 서브 트리 (Sub Tree)
- 트리 구조안에서 특정 노드를 루트로 하는 하위 트리
- 트리의 일부분이면서 동시에 또 하나의 트리인 구조
💡 형제 노드 (Sibling)
- 같은 부모 노드(Parent)를 공유하는 노드들을 의미
💡 크기 (Size)
- 트리 안에 포함된 모든 노드의 수(루트 포함)를 의미
💡 깊이 (depth)
- 특정 노드에서 루트까지의 거리(엣지의 수)를 의미
- 루트 노드의 깊이는 0이며, 루트 바로 아래 자식 노드는 깊이 1
- 깊이가 깊을수록 루트에서 멀리 떨어져 있는 노드
💡 높이 (height)
- 트리 전체에서 가장 깊은 노드까지의 거리를 의미
- 트리 안의 모든 노드 깊이 중 최대값
- 루트에서 가장 멀리 있는 리프 노드까지 도달하기 위해 거쳐야 하는 엣지(edge)의 개수
📌 이진 트리 (Binary Tree)
💡 이진 탐색 트리 (Binary Search Tree)
- 왼쪽 자식노드의 값 → 부모 노드보다 작아야 함
- 오른쪽 자식 노드의 값 → 부모 노드의 값보다 커야 함
💡 정 이진 트리 (Full Binary Tree)
- 모든 노드가 0개 또는 2개의 자식 노드만 가짐
- 한쪽만 있는 노드는 없음
- 모든 노드가 자식이 0개 (리프) 또는 2개(완전한 내부 노드)만 가지는 이진트리
자식이 1개인 노드가 절대 없다
💡 균형 이진 트리 (Balanced Binary Tree)
- 트리의 왼쪽 서브트리와 오른쪽 서브트리의 퐁이차이가 일정 이하로 유지되는 트리
- 트리가 한쪽으로 너무 기울지 않게 균형을 맞춘 상태
- 이진 트리 탐색의 평균 탐색 시간 O(), 트리가 한쪽으로 기울면 O(n)으로 떨어짐
💡 완전 이진 트리 (Complete Binary Tree)
- 왼쪽부터 순서대로 채워진 이진트리
- 트리의 모든 레벨이 꽉 차 있지만 마지막 레벨은 왼쪽부터 순서대로 채워져야 함
- 위에서부터 왼쪽에서 오른쪽으로 빠짐없이 노드를 채우는 형태
💡 연산별 시간 복잡도
삽입 → O(logn)
삭제 → O(logn)
트리 전체 순회 → O(n)
💡 포화 이진 트리 (Perfect Binary Tree)
- 트리의 모든 레벨이 완전히 채워진 이진트리
- 리프 노드가 전부 같은 깊이(레벨)에 있고 모든 내부 노드가 자식 노드를 2개씩 가진 트리
- 시간복잡도 → O()
💡 편향 이진 트리 (Skewed Binary Tree)
- 모든 노드가 한쪽 방향으로만 자식 노드를 가지는 이진트리
- 왼쪽 또는 오른쪽 한쪽으로 기울어진 형태의 트리
- 시간복잡도 → O(n)
📌 트리 순회 (Tree Traversal)
- 트리 구조에서 데이터를 어떤 순서로 방문할지가 중요함
- 트리는 배열처럼 인덱스로 접근할 수 없기 때문에, 모든 노드를 한 번씩 빠짐없이 탐색하기 위한 규칙적인 방법이 필요
💡 중위 순회 (in-order-traversal)
- left → root → right
- 예) 3 → 2 → 4 → 1 → 5
목적
- 정렬된 데이터 탐색
💡 전위 순회 (pre-order-traversal)
- root → left → right
- 예) 1 → 2 → 3 → 4 → 5
목적
- 정렬 트리 구조를 복사, 저장
실제 활용 예시
- 폴더 구조 탐색
- 데이터 직렬화(Serialization)
💡 후위 순회 (post-order-traversal)
- left → right → root
- 예) 3 → 4 → 2 → 5 → 1
목적
- 삭제, 정리
실제 활용 예시
- 폴더 삭제, 메모리해제
📌 실습
💡 정렬이 되어 있는 배열로 이진 검색 트리 구현
// 이진 트리의 노드 구조 정의
class Node {
constructor(data) {
this.data = data; // 실제 노드가 가진 값
this.left = null; // 왼쪽 자식 노드
this.right = null; // 오른쪽 자식 노드
}
}
// 이진 트리 클래스
class Tree {
constructor() {
this.root = null; // 루트 노드
}
makeTree(array, start = 0, end = array.length - 1) {
if (start > end) return null;
const mid = Math.floor((start + end) / 2);
const newNode = new Node(array[mid]);
newNode.left = this.makeTree(array, start, mid - 1); // 왼쪽 서브트리 생성
newNode.right = this.makeTree(array, mid + 1, end); // 오른쪽 서브트리 생성
this.root = newNode;
return newNode;
}
search(node, value) {
if (!node) return console.log('노드 없음');
if (value < node.data) {
// 왼쪽
console.log(`${value}값이 ${node.data}보다 작다 → 왼쪽으로 이동`);
this.search(node.left, value);
} else if (value > node.data) {
// 오른쪽
console.log(`${value}값이 ${node.data}보다 크다 → 오른쪽으로 이동`);
this.search(node.right, value);
} else {
// 데이터 찾음
console.log(`데이터(${value}) 찾음`);
}
}
}
const t = new Tree();
t.makeTree([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
// console.log(JSON.stringify(t, null, 4));
t.search(t.root, 6);💡 이진 탐색 트리(BST) 구현 및 순회
// 이진 트리의 노드 구조 정의
class Node {
constructor(data) {
this.data = data; // 실제 노드가 가진 값
this.left = null; // 왼쪽 자식 노드
this.right = null; // 오른쪽 자식 노드
}
}
class Tree {
constructor() {
this.root = null; // 루트 노드
}
// 노드 삽입
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
return;
}
const insertNode = (node, value) => {
if (!node) return newNode;
if (value < node.data) {
node.left = insertNode(node.left, value); // 왼쪽 서브트리에 삽입
} else if (value > node.data) {
node.right = insertNode(node.right, value); // 오른쪽 서브트리에 삽입
}
return node;
};
this.root = insertNode(this.root, value);
}
// 노드 탐색
search(node, value) {
if (!node) {
console.log('노드 없음');
return null;
}
if (value < node.data) {
console.log(`${value} 값이 ${node.data}보다 작음 → 왼쪽으로 이동`);
return this.search(node.left, value);
} else if (value > node.data) {
console.log(`${value} 값이 ${node.data}보다 큼 → 오른쪽으로 이동`);
return this.search(node.right, value);
} else {
console.log(`${value} 찾음`);
return node;
}
}
// 중위 순회 - Left → Root → Right
inOrder(node) {
if (!node) return;
this.inOrder(node.left);
console.log(node.data);
this.inOrder(node.right);
}
// 전위 순회 - Root → Left → Right
preOrder(node) {
if (!node) return;
console.log(node.data);
this.preOrder(node.left);
this.preOrder(node.right);
}
// 후위 순회 - Left → Right → Root
postOrder(node) {
if (!node) return;
this.postOrder(node.left);
this.postOrder(node.right);
console.log(node.data);
}
}
const t = new Tree();
t.insert(6);
t.insert(4);
t.insert(8);
t.insert(2);
t.insert(5);
t.insert(7);
t.insert(9);
console.log(t.root);
t.search(t.root, 5);
console.log('중위 순회 결과:');
t.inOrder(t.root);
console.log('전위 순회 결과:');
t.preOrder(t.root);
console.log('후위 순회 결과:');
t.postOrder(t.root);