Javascript 자료구조

📌 트리(Tree)

트리는 1개 이상의 노드를 갖는 집합으로 노드들은 다음 조건을 만족한다.

1. 최상위 정점을 루트(root), 각 정점을 노드(node)라고 한다.
2. 루트 정점을 제외한 노드는 반드시 하나의 부모만을 갖는다.
3. 특정 노드로 가는 경로는 1개이다.

이미지 출처 : https://www.tutorialandexample.com/tree-in-ds/

---

📌 트라이(Trie)

트라이는 문자열의 집합을 표현하는 '트리 자료구조'이다.

1. 검색어 자동완성, 사전 찾기 등에 응용될 수 있다.
2. 문자열 집합의 개수와 상관 없이 찾고자 하는 문자열의 길이가 시간 복잡도가 된다.
   (문자열의 길이가 L이라고 한다면 시간 복잡도는 O(L))
3. 시간 복잡도는 상대적으로 낮은 대신 높은 공간 복잡도가 특징이다.

이미지 출처 : https://java2blog.com/trie-data-structure-in-java/

---

📌 힙(Heap)

힙은 완전 이진 트리의 일종으로 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

1. 트리 구조에서 우선순위가 높은 요소가 먼저 나가는 특징을 가진다.
2. 루트가 가장 큰 값이 되는 최대 힙, 가장 작은 값이 되는 최소 힙이 있다.
3. 힙의 시간 복잡도는 O(logn) 이다.

이미지 출처 : https://www.geeksforgeeks.org/heap-data-structure/

Javascript 최소 힙(Min Heap) 구현

// 최소 힙(Min Heap) 객체
class MinHeap {
  constructor() {
    this.heap = [null];
  }
  
  // 노드 추가 메서드
  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);

    // 추가하려는 노드가 부모 노드와 비교했을 때 더 작은 값을 부모 노드의 위치로 변경
    while (parentIndex !== 0 && this.heap[parentIndex] > value) {
      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[parentIndex];
      this.heap[parentIndex] = temp;

      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }

  // 노드 삭제 메서드
  pop() {
    // 최상위 노드인 루트를 변수에 저장하여 모든 과정이 끝난 후에 리턴해준다.
    const returnValue = this.heap[1];
    this.heap[1] = this.heap.pop(); // Leaf Node를 pop()후 리턴 값을 최상위 노드에 저장하여 리프 노드를 루트에 저장한다..

    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;
    
    // 부모 노드와 자식 노드를 비교했을 때 부모 노드가 더 크다면 자식과 위치를 변경하는 과정을 반복한다.
    while (
      this.heap[currentIndex] > this.heap[leftIndex] ||
      this.heap[currentIndex] > this.heap[rightIndex]
    ) {
      if (this.heap[leftIndex] > this.heap[rightIndex]) {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      } else {
        const temp = this.heap[currentIndex]
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      }
      leftIndex = leftIndex * 2;
      rightIndex = rightIndex * 2 + 1;
    }

    // 최초 변수에 담았던 루트 값을 리턴한다.
    return returnValue;
  }
}

---

📌 배운점

트리, 트라이, 힙 등 자료구조의 특징에 대해서는 어느 정도 들어서 간단하게 아는 정도였지만 이를 구현하는 것에는 관심을 가져본 적이 없었다. 각 프로그래밍 언어에서 빌트인으로 제공하거나, 자료구조를 모르더라도 지금까지의 코딩테스트 문제는 풀이가 가능했기 때문에 중요하게 생각하지 않았다. 코딩 테스트 문제 풀 때, 배열이나 객체를 이용해서도 충분히 문제를 풀어나갈 수 있었기 때문이다.(지금 생각해보면 쉽고 간단한 문제여서 그렇다고 생각한다.)

생소했던 자료구조인 트리, 트라이, 힙에 대해 학습하면서 아직 모르는게 너무 많다는 것을 느끼게 되었고, Javascript를 이용해 해당 자료구조를 구현하면서 Javascript의 문법에도 좀 더 익숙해진 것 같다. 코딩 테스트만을 위한게 아니라 이러한 과정을 통해 기본을 탄탄히하여 성장할 수 있을 것이라고 믿는다.

---

📌 앞으로

금일 최소 힙(Min Heap)을 구현하는 것을 학습했고, 만들어진 코드를 보지 않고 작성해 보았다. 항상 느끼는 거지만 구현하고 나서 코드들을 살펴볼 때는 이해도 잘되고 어렵지 않게 느껴지지만, 처음부터 작성해 나가면 중간중간 생각이 잘 안나서 시간이 꽤 오래 걸렸다. 작성되어 있는 코드를 보면 조금씩이어도 이해는 되기 때문에 이미 안다고 생각하기 쉬운데, 코드를 보지 않고 처음부터 직접 작성해가는 과정을 통해서 모르는게 무엇인지, 어디서 헷갈리는지를 알고 넘어가는게 매우 중요하다고 생각한다.

앞으로 아직 익숙하지 않은 자료구조들과 알고리즘에 대해서 학습을 하겠지만 지금같은 마음가짐을 이어서 안다고 넘어가지 말고 직접 구현해보고 모르는 것이 무엇인지 알고 넘어가는 과정을 거쳐야겠다.