데이터 구조란?
- 데이터를 메모리에 저장할 때, 데이터의 순서나 위치 관계를 규정한 것 (자료구조, Data structure)
- 즉, 데이터를 효율적으로 사용할 수 있도록 정리하는 방법이다. → 결국 효율적인 데이터 구조로 메모리 사용 효율을 높인다.
- 종류
- 선형 구조 (Array, Dynamic Array, Linked List, Oueue, Stack, Hash Table)
- 비선형 구조 (Tree, Graph)
배열(Array)
- 배열은 데이터를 한 열로 연속해서 정렬하는 데이터 구조이다.
- 장점 : 원하는 데이터에 접근할 때 편리하다. → 인덱스가 존재하기 때문
- 단점 : 데이터를 추가하거나 삭제하려면 시간이 오래 걸린다.
배열 관련 코드 설명
const a = [Blue, Yellow, Red];
// 데이터 접근 방법 → 인덱스 활용
console.log(a[0]); // Blue
console.log(a[1]); // Yellow
console.log(a[2]); // Red
// 데이터 추가 및 삭제
// 추가
a.push('Green'); // [Blue, Yellow, Red, Green]
a.unshift('White'); // [White, Blue, Yellow, Red, Green]
// 삭제
a.pop(); // [White, Blue, Yellow, Red]
a.shift(); // [Blue, Yellow, Red]
- 메모리상 위치는 인덱스를 바탕으로 계산할 수 있고, 각 데이터에 직접 접근할 수 있다. (= 랜덤 접근)
- 위에서 예시로 보여줬던 추가, 삭제는 배열의 앞과 뒤에서 데이터를 다루는 것이고 중간 부분에 있는 데이터를 다루고 싶을 땐 slice() 메서드를 이용한다.
- 배열 메서드는 따로 다뤄보자.
계산 시간 : 배열 (O(1) or O(n))
- 배열에 저장되어 있는 데이터의 개수가 n이라면, 랜덤 접근이 가능하기 때문에 상수 시간 O(1)에 데이터에 접근할 수 있다.
- 반면, 데이터를 앞이나 중간에서 추가하거나 삭제할 때는 그 뒤에 있는 모든 데이터를 하나씩 뒤로 옮기거나 앞으로 옮기는 연산이 발생한다. 이렇게 배열의 앞이나 중간에서 추가, 삭제한다면 O(n)의 시간이 소요된다.
링크드 리스트(Linked List)
- 리스트는 데이터를 일직선으로 줄줄이 정렬한 데이터 구조이다.
- 장점 : 데이터의 추가, 삭제 쉬움
- 단점 : 원하는 데이터에 접근하는 시간이 오래걸림
- 각 데이터는 포인터를 가지고 잇어 다음 데이터의 메모리 주소를 가리킨다.
- 따라서, 리스트의 각 데이터는 메모리상에서 연속된 영역에 배치되어 있을 필요가 없다. 분산 배치 되어있다.
- 연속적으로 배치되어 있지 않고 개별적으로 저장되어 있기 때문에 특정 데이터에 접근하려면 데이터의 포인터를 따라가야 한다.
- 이를 순차 접근 혹은 시퀀스 액세스(suquential access)라고 한다.
- 데이터를 쉽게 추가, 삭제할 수 있는 이유는 추가하거나, 삭제할 위치의 앞에 있는 데이터의 포인터를 바꾸면 되기 때문이다.
링크드 리스트 관련 코드 설명
- 코드로 살펴보자.
- append : 리스트 가장 뒤에 값 추가
- prepend : 리스트 가장 앞에 값 추가
- delete : 원하는 값 삭제
- deleteFirst : 리스트 가장 앞에 있는 값 삭제
- deleteLast : 리스트 가장 뒤에 있는 값 삭제
- display : 리스트 출력
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
// 초기 값을 null로 해준 이유는 꼬리 tail부분에 있는 자료는 가르킴을 받는 자료가 뒤에 없기 때문
}// constructor
}// Node
class LinkedList {
constructor() {
this.head = null; // 처음에 데이터가 없다면 head는 null이다.
this.size = 0;
}// constructor
//append
insertBack(data) {
let newNode = new Node(data);
let current;
if (!this.head) {
this.head = newNode;
return
}
current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
this.size++;
}//insertBack
//prepend
insertFirst(data) {
this.head = new Node(data, this.head);
this.size++;
}//insertFirst
//delete
deleteData(data) {
let currentNode = this.head;
if (currentNode && currentNode.data == data) {
this.head = currentNode.next;
currentNode = null;
return
}
let prevNode = null;
while (currentNode && currentNode.data != data ) {
prevNode = currentNode;
currentNode = currentNode.next;
}
if (!currentNode) { return }
prevNode.next = currentNode.next;
currentNode = null;
this.size--;
}// deleteData
deleteFirst() {
if (this.head) {
this.head = this.head.next;
}
this.size--;
}//deleteFirst
deleteLast() {
if (!this.head) { return }
if (!this.head.next) { this.head = null; return }
let seconedLast = this.head;
while (seconedLast.next.next) {
seconedLast = seconedLast.next;
}
seconedLast.next = null;
this.size--;
}//deleteLast
display() {
let currentNode = this.head;
let viewDataStructure = '';
while (currentNode) {
viewDataStructure += `${currentNode.data}->`;
currentNode = currentNode.next;
}
console.log(viewDataStructure + "end");
}//display
}// LinkedList
const linkedSample = new LinkedList();
linkedSample.insertFirst(1);
linkedSample.insertFirst(2);
linkedSample.insertFirst(3);
linkedSample.insertBack(9);
linkedSample.display(); // 출력 : 3->2->1->9->end
linkedSample.deleteData(2);
linkedSample.display(); // 출력 : 3->1->9->end
linkedSample.deleteFirst();
linkedSample.display(); // 출력 : 1->9->end
linkedSample.deleteLast();
linkedSample.display(); // 출력 : 1->end
- 기본적인 리스트의 경우 마지막 데이터는 포인터가 없다. 하지만 마지막 데이터의 포인터가 맨 앞의 데이터를 가리키게 하면 원형 리스트 혹은 순환 리스트의 형태가 된다.
- 데이터의 맨 앞이나 맨 뒤라는 개념은 사라진다.
- 항상 일정한 개수의 최신 데이터를 보관해야 하는 상황에서 사용되곤 한다.
- 기본 리스트의 경우 각 데이터의 포인터가 하나인데, 각 데이터가 포인터 두 개로 앞뒤 데이터를 가리키게 만든 양방향 리스트도 있다.
- 리스트를 앞에서 뒤로, 뒤에서 앞으로도 검색할 수 있어 편리하다.
- 다만, 양방향 리스트는 포인터 수가 늘어난 만큼 데이터양이 증가하고, 데이터를 저장하기 위한 공간도 늘어난다는 단점이 있다.
계산 시간 : 링크드 리스트 (O(1) or O(n))
- 특정 원소를 조회할 때, 해당 노드까지 탐색해야하기 때문에 O(n)의 시간이 소요된다.
- 데이터를 앞이나 중간에서 추가하거나 삭제할 때는 포인터를 바꿔주면 되기에 O(1)의 시간이 소요된다.
배열(Array)과 링크드 리스트(Linked List)
접근 | 추가 | 삭제 | |
리스트 | 느림 | 빠름 | 빠름 |
배열 | 빠름 | 느림 | 느림 |
스택(Stack)
- 스택은 데이터를 한 열로 저장하지만, 서류를 쌓아 올릴 때처럼 마지막에 추가한 데이터에만 접근할 수 있다.
- 새로운 서류가 오면 가장 위에 놓고, 꺼낼 때도 맨 위에 있는 서류를 꺼내는 것이다.
- 따라서, 스택처럼 나중에 넣은 것부터 꺼내는 후입선출 구조를 Last In First Out, 줄여서 LIFO라고 한다.
Stack - 과정 설명
- (1) 현재 A라는 데이터만 저장되어 있다.
- (2) B 데이터를 푸쉬(추가)한다. 스택에 데이터를 추가하면 맨 위에 추가된다. (스택에 데이터를 넣는 작업을 푸시(Push)라고 한다.)
- (3) B 데이터를 팝(꺼냄)한다. 스택에서 데이터를 꺼낼 때는 가장 위에서 올린 즉, 가장 직전에 추가된 데이터부터 꺼낸다. (스택에서는 데이터를 꺼내는 작업을 팝(Pop)이라 한다. )
Stack 관련 코드 설명
// Stack
const stack = [];
stack.push("Apple"); // Enqueue [ Apple ]
stack.push("Banana"); // Enqueue [ Apple, Banana ]
stack.push("Orange"); // Enqueue [ Apple, Banana, Orange ]
stack.pop(); // Dequeue -> Orange 제거
// [ Apple, Banana ]
stack[stack.length-1]; // Peek -> Banana
const isEmpty = () => {
return stack.length == 0; // false
}
- 스택도 리스트나 배열처럼 데이터를 일렬로 저장하지만, 데이터의 추가와 삭제가 한쪽 끝에서만 이뤄진다.
- 또한, 맨 위에 놓인 데이터에만 접근할 수 있기 떄문에 중간에 있는 데이터를 접근하려면 해당 데이터가 스택의 맨 위에 놓을 떄까지 데이터를 팝해야한다.
- 그래서 스택이 가장 유용하게 쓰이는 상황은 항상 최신 데이터에 접근해야 할 때는 유용하게 사용된다.
- 우리가 다룰 알고리즘인 깊이 우선 탐색에서는 탐색 후보 중에서 항상 최신의 것을 선택해야 하기에 Stack을 사용한다.
Stack - 시간 복잡도
- 스택의 삽입과 삭제 연산은 항상 top에서만 일어나므로 삽입과 삭제에 소요되는 시간 복잡도는 O(1)로 고정된다.
- 삽입 - O(1)
- 삭제 - O(1)(pop)
- 검색 - O(n)
큐(Queue)
- 큐도 지금까지 알아본 데이터 구조처럼 데이터를 한 열로 저장한다. 그렇다면 차이점이 뭘까?
- 큐는 추가하는 쪽과 삭제하는 쪽이 반대이다. 즉 큐를 대기 행렬이라고도 하는데, 이름이 의미하듯 줄을 서 있는 행렬과 비슷하다.
- 새로 온 사람은 제일 뒤에 줄을 서고, 제일 앞에 선 사람부터 순서대로 처리된다.
- 큐처럼 먼저 넣은 것을 먼저 꺼내는 선입선출 구조를 First In First Out, FIFO라고 부른다.
Queue - 과정 설명
- (1) Stack과 동일하게 A라는 데이터만 큐에 저장되어 있다.
- (2) B 데이터를 인큐(큐에 데이터를 추가하는 작업, enqueue)한다. 그럼 맨 뒤에 저장된다.
- (3) 큐에서 데이터를 꺼낼 때 가장 오래된 즉, 가장 아래에 있는 데이터부터 꺼낸다. 따라서 A 데이터를 꺼낸다. 이 과정을 디큐(dequeue)라고 한다.
Queue 관련 코드 설명
// Queue
const queue = [];
queue.push("Apple"); // Enqueue [ Apple ]
queue.push("Banana"); // Enqueue [ Apple, Banana ]
queue.push("Orange"); // Enqueue [ Apple, Banana, Orange ]
queue.shift(); // Dequeue -> Apple
// [ Banana, Oragne ]
queue[0]; // Peek -> Banana
const isEmpty = () => {
return queue.length == 0; // false
}
- 큐도 스택과 마찬가지로 데이터를 조작할 수 있는 위치가 제한적이다.
- 스택은 같은 쪽에서 데이터를 제어하는 반면, 큐는 추가하는 쪽과 삭제하는 쪽이 반대이다. 따라서 스택과 마찬가지로 중간에 있는 데이터에 접근할 수 없고, 필요한 데이터가 나올 때까지 Dequeue해야한다.
- Queue는 오래된 데이터부터 차례로 처리하는 것은 지극히 자연스러운 방식이기에 폭넓게 사용되고 있다.
- 예를 들어, 너비 우선 탐색에서는 탐색 후보 중 항상 가장 오래된 것을 선택해야 하기 때문에 큐를 사용한다.
Queue - 시간 복잡도
- 큐의 삽입은 스택의 삽입과 같아 O(1)으로 고정되며, 삭제는 배열로 데이터 구조가 만들어져 있으면 맨 앞에 원소를 삭제시 뒤에 있는 원소들의 인덱스 위치값이 다 바뀌므로 O(n)의 시간복잡도를 가진다. → 이를 주의하여 문제를 풀어야한다.
- 삽입 - O(1)
- 삭제 - O(n)(shift) : 1,000초과 되는 경우에는 클래스를 활용하여 Queue 알고리즘을 구현하여 사용하는 것이 좋다.
- 검색 - O(n)
해시 테이블(Hash Table)
- 해시 테이블은 해시 함수를 활용해 만든 데이터 구조이다. 그리고 키(Key)와 값(Value)을 하나의 짝으로 저장하는 데이터 구조이다.
- 해쉬 테이블의 장점과 단점
- 장점 : 빠른 검색 및 삽입, 유연한 크기 조정 → 메모리 효율 좋음
- 단점 : 무작위성 (순서가 없다.)
- 일반적으로 키는 데이터의 식별자이며, 값은 데이터의 내용을 나타낸다. 자바스크립트에서는 해시 테이블과 같은 자료구조를 가진 객체가 있다.
- 객체는 Array, Map, Object 등을 포함한다. Array를 활용하여 해시 함수와 충돌 메커니즘을 직접 구현할 수 있는데 다음 글에서 직접 구현하며 돌아보려 한다. 이를 통해 작동 방식을 이해하는데 도움을 얻을 수 있다. 실무에서는 최적화된 Object나 Map 사용이 일반적이기 때문에 지금은 이 두개를 살펴보려 한다.
- 객체는 프로퍼티의 집합이며, 프로퍼티는 키와 값으로 구성된다.
- 프로퍼티 키 : 빈 문자열을 포함하는 모든 문자열 또는 심벌 값
- 프로퍼티 값 : 자바스크립트에서 사용할 수 있는 모든 값
해시 테이블 코드 관련 설명
// Object 객체 예시
const person = new Object;
person['name'] = 'Kim';
person.age = 25;
console.log(person);
// { name: 'Kim', age: 25 }
// Map 객체 예시
const map = new Map;
// 데이터 추가 set()
map.set('name', 'Kim');
map.set('age', '20');
console.log(map);
//Map(2) { 'name' => 'Kim', 'age' => '20' }
// 키 순회 for...of
for (let key of map.keys()) {
console.log(key);
}
// 값 순회 for...of
for (let value of map.values()) {
console.log(value);
}
// 키-값 쌍 순회 for...of
for (let [key, value] of map.entries()) {
console.log(key, value);
}
// forEach 사용
map.forEach((value, key) => {
console.log(key, value);
});
// 값 가져오기 get()
console.log(map.get('name')); // Kim
console.log(map.get('age')); // 20
// 키 존재 여부 확인 has()
console.log(map.has('name')); // true
console.log(map.has('addresss')); // false
// 키-값 쌍 삭제 delete()
map.delete('age');
// 맵 크기 확인 size
console.log(map.size); // 1
// 모든 요소 제거 clear()
map.clear();
- Map 객체는 고유의 용도와 특징을 가지고 있으며, 효율적이고 유연한 해시 테이블로서의 역할을 잘 수행한다.
그럼 Map 객체와 Object 객체의 차이는 무엇일까? Map과 Object의 차이점에 대해 알아보자.
new Map vs new Object
1. Key 타입
- Object : 반드시 문자열(String)이나 심볼(Symbol)
- Map : 문자열, 객체, 함수 등 모든 값 사용 가능
2. Key 순서
new Object | new Map | |
Key 타입 | 반드시 문자열(String)이나 심볼(Symbol) | 문자열, 객체, 함수 등 모든 값 사용 가능 |
Key 순서 | 키는 삽입 순서를 보장하지 않음 문자열 키는 순서 없이 저장, 숫자 키는 자동 정렬 |
키는 삽입된 순서대로 저장됨 |
크기 | 수동으로 키의 개수를 세어야 함 ex. Object.keys(object).length |
'size'라는 속성을 사용하여 쉽게 크기를 확인할 수 있다. ex. map.size |
성능 | 객체는 단순한 키-값 저장 및 조회에 최적화되어 있지만, 고성능 해시 테이블로 설계된 것이 아님 | 맵은 해시 테이블로 설계되어 빠른 조회, 삽입, 삭제 성능을 제공한다. |
반복 | 'for...in'루프 또는 Object.keys(), Object.values(), Object.entries()와 같은 메서드 사용 | 'for...of'루프와 keys(), values(), entries() 등의 메서드를 사용하여 간단히 반복할 수 있음 |
메서드 | 객체에는 Object.prototype의 메서드들이 있다. 이러한 메서드들이 키로 사용될 수 있는 위험이 있음 | 맵은 자체 메서드를 가지며, Map.prototype의 메서드들이 충돌할 위험이 없음 |
사용 사례 | 일반적으로 구조화된 데이터 저장 및 속성 접근에 적합 | 다양한 유형의 키를 사용해야 하거나, 삽입 순서를 유지해야 하는 경우 적합 |
- 메서드 예시 코드
let obj = {};
obj['toString'] = 'some value';
console.log(obj['toString']); // 'some value' (Object의 기본 메서드와 충돌 가능)
let map = new Map();
map.set('toString', 'some value');
console.log(map.get('toString')); // 'some value' (충돌 없음)
- 결론
- Object 객체는 기본적으로 해시 테이블 역할을 하지만, 특정 상황에서는 Map이 더 적합할 수 있다.
- 따라서 Object와 Map은 용도와 특성이 다르기 때문에, 필요에 따라 적절한 자료구조를 선택해야 한다.
Hash Table - 시간복잡도
- 평균 시간복잡도
- 삽입 : O(1)
- 삭제 : O(1)
- 탐색 : O(1)
- 최악의 시간복잡도
- 모든 키가 동일한 해시 값을 가질 때 해시 테이블은 연결리스트 처럼 동작하게 되어 O(n)의 시간 복잡도를 갖는다.
- Map은 다양한 타입의 키를 허용하고 성능이 최적화되어 있어, 일반적으로 해시 테이블의 용도로 더 많이 사용되고 있다.
힙(Heap)
- 힙은 그래프의 트리 구조 중 하나로 우선 순위 큐를 구현할 때 사용된다.
- 우선순위 큐는 데이터를 자유롭게 추가할 수 있지만, 꺼낼 때 항상 작은 데이터를 꺼낸다. 따라서 우선순위 큐(Priority Queue)를 구현할 때 주로 사용되는 자료구조이다.
- 노드 : 힙을 비롯한 트리 구조에서 각 정점
- 힙 : 이 노드에 데이터를 저장
힙의 기본 개념
- 최대 힙(Max Heap)
- 부모 노드의 값이 자식 노드의 값보다 크거나 값은 완전 이진 트리
- 최소 힙(Min Heap)
- 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리
힙 관련 코드 설명
class MinHeap {
constructor() {
this.heap = [];
}
getParentIndex(index) {
return Math.floor((index - 1) / 2);
}
getLeftChildIndex(index) {
return 2 * index + 1;
}
getRightChildIndex(index) {
return 2 * index + 2;
}
swap(index1, index2) {
[this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
}
insert(value) {
this.heap.push(value);
this.heapifyUp();
}
heapifyUp() {
let index = this.heap.length - 1;
while (this.getParentIndex(index) >= 0 && this.heap[this.getParentIndex(index)] > this.heap[index]) {
this.swap(index, this.getParentIndex(index));
index = this.getParentIndex(index);
}
}
remove() {
if (this.heap.length === 0) {
return null;
}
if (this.heap.length === 1) {
return this.heap.pop();
}
const root = this.heap[0];
this.heap[0] = this.heap.pop();
this.heapifyDown();
return root;
}
heapifyDown() {
let index = 0;
while (this.getLeftChildIndex(index) < this.heap.length) {
let smallerChildIndex = this.getLeftChildIndex(index);
if (this.getRightChildIndex(index) < this.heap.length && this.heap[this.getRightChildIndex(index)] < this.heap[smallerChildIndex]) {
smallerChildIndex = this.getRightChildIndex(index);
}
if (this.heap[index] <= this.heap[smallerChildIndex]) {
break;
}
this.swap(index, smallerChildIndex);
index = smallerChildIndex;
}
}
peek() {
if (this.heap.length === 0) {
return null;
}
return this.heap[0];
}
}
const minHeap = new MinHeap();
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(2);
minHeap.insert(7);
console.log(minHeap)
console.log(minHeap.peek()); // 2
console.log(minHeap.remove()); // 2
console.log(minHeap.peek()); // 3
메서드 설명
- insert()
- 새로운 요소를 힙의 마지막에 추가하며 heapiftUp()를 사용하여 힙의 특성을 유지함
- remove()
- 힙 루트 요소(최소 힙의 경우 최솟값) 제거, 힙의 마지막 요소를 루트로 이동시킨 후 heapityDown()를 사용하여 힙의 특성을 유지
- Heapify
- heapfiyUp : 삽입 후, 요소를 올려가며 부모와 비교하여 교환
- heapfitDwon : 삭제 후, 요소를 내려가며 자식들과 비교하여 교환
힙 - 시간복잡도
- 힙은 항상 가장 작은, 가장 큰 데이터가 맨위에 있기 때문에 최소/최대 값에 접근할 때는 데이터 개수와 상관없이 O(1)시간으로 최소값을 꺼낼 수 있다.
- 하지만 데이터를 꺼낸뒤 힙을 재구성할 때는 맨 끝에 있는 데이터를 맨 위로 옮긴 뒤 자식 노드와 비교하면서 밑으로 이동한다. 따라서 이 작업의 시간은 트리의 높이에 비례하다. 데이터의 수가 n이라면 계산 시간은 O(log n)이 된다. 데이터를 추가할 때도 마찬가지다.
- 삽입 : O(log n)
- 삭제 : O(log n)
- 최소/최대 값 접근 : O(1)
힙 활용
- 보관 중인 데이터의 최솟값, 최대값을 빈번하게 찾아야 하는 경우에 힙이 유용하다.
- 다익스트라 알고리즘은 매번 후보 정점들 중에서 최솟값을 선택하는데 이때 힙을 사용하기도 한다.
이진 탐색 트리 (BST, Binary Search Tree)
- 이진 탐색 트리는 그래프의 트리 구조로 각 노드에 데이터가 저장된다.
- 정렬된 데이터를 효율적으로 탐색, 삽입, 삭제할 수 있는 자료 구조이다.
특징
- 각 노드는 최대 두 개의 자식 노드를 가진다.
- 각 노드의 값은 왼쪽 가지에 있는 노드들의 값보다 크다.
- 각 노드의 값은 오른쪽 가지에 있는 노드들의 값보다 작다.
- 따라서 이진 탐색 트리의 최솟값은 제일 위에 있는 노드에서 왼쪽 트리만 탐색하면 찾을 수 있다. 반대로 최대값은 젤 위에 있는 노드에서 오른쪽 트리만 탐색하면 찾을 수 있다.
이진 탐색 트리 관련 코드 설명
노드 클래스
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
이진 탐색 트리 클래스
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new TreeNode(value);
if (this.root === null) {
this.root = newNode;
return;
}
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);
}
}
}
search(value) {
return this.searchNode(this.root, value);
}
searchNode(node, value) {
if (node === null) {
return false;
}
if (value < node.value) {
return this.searchNode(node.left, value);
} else if (value > node.value) {
return this.searchNode(node.right, value);
} else {
return true;
}
}
delete(value) {
this.root = this.deleteNode(this.root, value);
}
deleteNode(node, value) {
if (node === null) {
return null;
}
if (value < node.value) {
node.left = this.deleteNode(node.left, value);
return node;
} else if (value > node.value) {
node.right = this.deleteNode(node.right, value);
return node;
} else {
// 노드가 하나의 자식만 있거나 자식이 없을 때
if (node.left === null) {
return node.right;
} else if (node.right === null) {
return node.left;
}
// 노드가 두개의 자식이 있을 때
node.value = this.minValueNode(node.right).value;
node.right = this.deleteNode(node.right, node.value);
return node;
}
}
minValueNode(node) {
let current = node;
while (current.left !== null) {
current = current.left;
}
return current;
}
inOrderTraversal(node, callback) {
if (node !== null) {
this.inOrderTraversal(node.left, callback);
callback(node.value);
this.inOrderTraversal(node.right, callback);
}
}
}
const bst = new BinarySearchTree();
bst.insert(10); // (1)
bst.insert(1); // (2)
bst.insert(23); // (3)
bst.insert(8); // (4)
bst.insert(59); // (5)
console.log(bst.search(10)); // true
bst.inOrderTraversal(bst.root, value => console.log(value));
// Output : 1, 8, 10, 23, 59
이진 탐색 트리의 활용
- 데이터베이스의 인덱스 구조로 사용되어 효율적인 데이터 검색을 가능하게 한다.
- 다양한 정렬 및 검색 알고리즘의 기초로 사용된다.
- 텍스트 편집기와 같은 애플리케이션에서 빠른 문자열 검색을 지원
- 일정 관리 시스템에서 이벤트를 효율적으로 관리하고 검색할 수 있다.
이진 탐색 트리 - 시간 복잡도
- 데이터를 찾거나 추가할 때, 현재 위치의 데이터와 크기를 비교하여 왼쪽 혹은 오른쪽으로 진행하면서 노드의 위치를 찾는다.
- 비교 연산은 트리의 높이 만큼 수행하게 된다. 따라서 계산 시간은 O(log n)이 된다.
- 다만, 트리가 한쪽으로 치우쳐서 세로로 늘어진 모양이 되면 높이가 높아져 계산 시간이 O(n)이 된다.
이진 탐색 트리, 더 나아가기
- 균형 이진 탐색
- 트리가 한쪽으로 치우치면 형태를 수정하여 항상 균형을 유지하는 것, 검색 효율을 높인다.
- B 트리
- 이진 탐색 트리의 경우 각 노드의 자식 노드가 최대 두 개 였는데, 이를 m개(m은 미리 정해 둔 상수)로 확장하고 자식 노드 수에 자유도를 부여하여 트리의 균형을 맞춤
결론
이렇게 그림으로 이해하는 알고리즘 책을 통해 기본 자료구조를 정리할 수 있었다. 자료구조는 물론 알고리즘 모두 해당 개념의 원리를 잘 이해해야 응용할 수 있다고 생각한다. 이 자료구조 개념 정리를 통해 앞으로 기능 구현시 어떤 자료구조, 알고리즘을 활용하여 시간복잡도를 단축시킬 수 있고, 성능을 최적화할 수 있는지 고민하고 다양한 문제 해결 방법을 연구하고자 한다.
🔗 Reference
- 그림으로 이해하는 알고리즘 - 도서
- 모던 자바스크립트 Deep Dive - 도서
'Data Structure&Algorithm' 카테고리의 다른 글
[Algorithm] DP(다이나믹 프로그래밍) (0) | 2024.05.14 |
---|---|
[Algorithm] 이진 트리(Binary Tree)와 트리 순회(Tree Traversal) (0) | 2024.05.09 |
[Algorithm] 완전탐색 & 재귀 (0) | 2024.04.29 |
[Algorithm] 그리디 (1) | 2024.04.12 |
[Algorithm] 에라토스테네스의 체 (0) | 2024.04.04 |