- Published on
[자료구조] javascript 트리 (Tree)
- Authors
- Name
- piano cat
javascript 에서 트리 자료구조에 대해서 알아보자
트리구조의 특징
- 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
- 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
- 루트에서 특정 정점으로 가는 경로는 유일하다.
이진트리
- 이진트리 종류: 완전 이진트리, 포화 이진트리, 편향 트리
이진트리 특징
- 정점이 N개인 이진트리는 최악의 경우 높이가 N이 될수있다. (편향트리일 경우)
- 정점이 N개인 포화 또는 완전 이진트리의 높이는 log N 이다.
- 높이가 a인 포화 이진트리는 2ª - 1 개의 정점을 가진다.
- 일반적인 이진 트리를 사용하는 경우는 많지 않다. 다음 자료구조에 응용된다. (이진트리 탐색, 힙, AVL 트리, 레드 블랙 트리)
이진 탐색 트리 조건
- 부모 노드의 왼쪽 노드는 부모 노드보다 작아야 한다.
- 부모 노드의 오른쪽 노드는 부모 노드보다 커야 한다.
이진트리 구현
// 이진 트리 노드 클래스 정의
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// 이진 트리 클래스 정의
class BinaryTree {
constructor() {
this.root = null;
}
// 노드 삽입 메서드
insert(value) {
const newNode = new Node(value);
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
// 노드 삽입 보조 메서드
insertNode(node, newNode) {
if (newNode.value < node.value) {
if (node.left === null) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode);
}
}
}
// 트리 순회 메서드: 전위 순회 (루트-왼쪽-오른쪽)
preOrderTraversal(node) {
if (node !== null) {
console.log(node.value);
this.preOrderTraversal(node.left);
this.preOrderTraversal(node.right);
}
}
// 트리 순회 메서드: 중위 순회 (왼쪽-루트-오른쪽)
inOrderTraversal(node) {
if (node !== null) {
this.inOrderTraversal(node.left);
console.log(node.value);
this.inOrderTraversal(node.right);
}
}
// 트리 순회 메서드: 후위 순회 (왼쪽-오른쪽-루트)
postOrderTraversal(node) {
if (node !== null) {
this.postOrderTraversal(node.left);
this.postOrderTraversal(node.right);
console.log(node.value);
}
}
}
// 이진 트리 인스턴스 생성
const binaryTree = new BinaryTree();
활용 예시
계층적 데이터, 정렬된 데이터, 검색이 빈번한 데이터 등
- 계층적 데이터: 조직도, 디렉토리 구조 등
- 정렬된 데이터: 이진 탐색 트리, AVL 트리, 레드-블랙 트리 등
- 검색이 빈번한 데이터: 데이터베이스 인덱스 등