이번 주는 자료구조 공부를 했다. 제로초님 블로그의 알고리즘 란에 있는 lv1~lv3 문제들을 풀어야겠다 싶어서 풀다가 DP 유형에서 탁 막혔다. 아직 Tree나 DP 유형은 그 기초조차 공부한 적이 없다. 나오면 풀어보고 모르겠으면 공부해야 겠다는 생각이었지만 막상 나오니까 '모르면 손 조차 못 대는구나.' 하는 생각이 들었다. 그래서 일단 막힌 김에 다시 기초를 잡아야 겠다는 생각이 들어서 일단 Tree 자료구조를 공부했다.

너, 종류가 많구나?

힙 트리, 이진 트리, 이진 탐색 트리 등등 트리는 종류가 다양했다. 처음엔 뭘 공부하면 좋을까 고민을 했는데, 결국엔 트리구조에서 노드를 어떻게 삽입하는지, 탐색은 어떻게 하는지는 모두 유사했다. 그래서 기본적인 것을 알게 되면 나머지는 그때그때 맞춰서 해줄 수 있는 것이었다. 그래서 일단은 이진 탐색 트리를 만들어 보았고, 이해를 어느 정도 한 이후에 다른 트리에 대해 알아보았다.

1. 이진트리

이름부터가 두 개인 거 같은가? 그렇다면 이해를 다 한 것이다. 이진트리는 이름 그대로 최대 자식 노드 수가 두 개인 트리를 말한다.

같은 원리로 최대 노드 개수가 3개 라면 삼진 트리라고 부른다.

2. 완전이진트리

완전이진트리는 왼쪽의 빈 노드부터 차근차근 채워나가는 트리를 말한다.

이런 규칙 상 오른쪽 자식 노드가 있는 부모 노드는 왼쪽 자식 노드가 무조건 있다.

3. 힙 트리

힙 트리는 완전 이진 트리의 일종으로 부모 노드가 자식 노드들 보다 일정하게 작거나 크다. 힙은 최소 힙과 최대 힙이 있다. 최소와 최대를 나누는 기준은 부모 노드가 자식 노드들보다 큰 지, 작은 지이다.

이런 특징 때문에 힙 트리는 반 정렬된 상태이다.

3-1. 최소 힙

최소 힙은 부모 노드보다 자식 노드들의 값이 클 때를 말한다.

3-2. 최대 힙

최대 힙은 부모 노드보다 자식 노드들의 값이 작을 때를 말한다.

4. 이진탐색트리

이진 탐색 트리는 왼쪽 자식 노드는 부모 노드 보다 작고, 오른쪽 자식 노드는 부모 노드 보다 크다는 규칙이 있다.

클래스로 만들어 본 이진탐색트리

이진탐색트리는 조건이 있다보니 insert를 할 때 재귀를 통해서 계속 기존 노드들과 값을 비교해 내려가야 한다. 그런 부분에서 어쩌면 가장 까다롭다고 생각했고 그래서 이진탐색트리로 공부를 해두면 다른 트리도 쉽게 구현할 수 있으리라 생각을 했다.

아래는 class로 만들어 본 이진탐색트리이다.

class Node {
  constructor(data) {
    this.data = data;
    this.right = null;
    this.left = null;
  }
  // data가 해당 노드의 데이터 보다 작으면 왼쪽에 삽입을 하는 private method를 호출하고 아니면 오른쪽에 삽입을 하는 private method를 호출하면 된다.
  insert(data) {
    return data <= this.data ? this._insertLeft(data) : this._insertRight(data);
  }
  _insertRight(data) {
    return this.right ? this.right.insert(data) : (this.right = new Node(data));
  }
  _insertLeft(data) {
    return this.left ? this.left.insert(data) : (this.left = new Node(data));
  }
  // find를 했을 때 찾는 데이터가 노드의 데이터 보다 작으면 왼쪽으로 탐색하는 private method를 호출하고 크면 오른쪽으로 탐색하는 private method를 호출한다.
  find(data) {
    if (this.data === data) return this;
    return data <= this.data ? this._findLeft(data) : this._findRight(data);
  }
  _findRight(data) {
    return this.right ? this.right.find(data) : null;
  }
  _findLeft(data) {
    return this.left ? this.left.find(data) : null;
  }
}

이진탐색트리는 규칙이 명확하기 때문에 탐색시간이 길어 봤자 트리의 깊이, 즉 O(logn)이다.

마무리

트리도 내가 예전부터 공부해보려고 했던 부분인데 어찌 계속 손이 안가서 못하고 있었다가 이번에 하게 되었다. 생각해보면 C언어로 연결리스트와 스택을 공부한 뒤로 처음으로 공부하는 자료구조이다. JS로는 처음 공부하는 자료구조였다. 얼마나 그 동안 안한거야.. 반성을 해본다😢
사실 이런 기본적인 구현도 중요하지만 실질적으로 문제를 풀 수 있는 BFS, DFS도 중요하기 때문에 이제 시작이라 생각하고 계속 공부하고 있다.

참고자료
https://jomuljomul.tistory.com/entry/%EC%99%84%EC%A0%84%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%ACComplete-Binary-Tree%EB%9E%80
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
https://velog.io/@kimkevin90/Javascript%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-tree-%EA%B5%AC%ED%98%84