트리를 이용한 순회

• 트리 자료구조를 이용하여
  - 전위 : 루트 노드부터 시작하여 왼쪽 자식부터 하나씩 찍으면서 dfs내려가는것
  - 중위 : 루트부터 시작하여 왼쪽 자식까지 계속해서 내려간 다음, 더이상 내려갈 수 없으면 왼쪽 - 부모 - 오른쪽을 찍음
  - 후위 : 중위와 비슷한데, 왼쪽 - 오른쪽을 찍은 후에 부모를 찍음
  

• 트리 라는 자료구조가 보통 연결리스트 ->class 문법을 활용해야 하다 보니 조금 익숙하지 않았던 건 사실이다..(배열로도 가능하지만 뭔가 그 의미를 살리려면 연결리스트가 맞는것같음)

• 근데 사실 트리(엄밀하게 말하면 이진탐색트리)는 어려운 편은 아님. 어차피 연결되어있는 자식이 left 한개, right 한개이기 때문에 어찌보면 배열보다 더 직관적으로 자식 노드를 살펴볼 수 있는 느낌 (배열은 index로 접근해야 하기 때문에)

• 그래서 사실 트리는 그렇게 어려운 점은 없었던것 같다..

트라이를 이용한 자동완성 기능

• 과제를 다 마치고서도 고민했던 내용이 과연 '자동완성이 무엇인가'?? 였다...

• 내가 생각하는 자동완성은, 예를 들어 아 라는 단어를 검색했을 때 아이유 라던지, 아이스크림 이라던지 이런 완전한 단어를 하나 보여주는 게 맞다고 생각한다(네이버나 구글도 동일한 개념인거 같음)

• 그런데 또 생각해보면, 내가 아 라고 입력했으면 -> 아ㅇ , 아이 라고 입력했으면 아이ㅇ 이런식으로 과정을 보여줘야 되는건가? 싶기도했다 (트라이 자료구조를 이용하면 이 과정을 보여주는게 어렵지 않으니까..)

• 그래도 뭔가 내가 자동완성 이라는 기능을 만들어야 한다면, 전자로 만들 것 같아서 전자로 진행했다

• 완전한 단어라는 의미는 => 해당 Node에 children이 없어야함

• 약간의 의문점
  - abcde 라는 단어를 트라이 자료구조에 저장하고, 그 이후 abc라는 단어를 저장하게 되면 이미 abc 는 기존의 단어(abcde)를 저장하는 과정에서 저장되었기 때문에, 그냥 탐색만 하다 return할 뿐, 아무런 영향이 없음

    -  나중에 `ab` 라는 단어를 자동완성 한다고 하면 , `abcde`라는 단어만 나오게 됨(`abc`의 children에는 'd':children이 남아있기 때문에) 
     - 이런 경우를 대비해 생각한 게 `abc` 를 가지고 있는 노드 객체에 속성으로 표시를 해준 후, 자동 완성 기능을 가진 메서드에서 노드의 제일 끝까지 탐색할 때 해당 속성이 있는 노드를 만난다면 이 노드 또한 하나의 단어로 판별하도록 해줌(childrend이 존재해도) 

class Node {
  constructor(value = '') {
    this.value = value;
    this.children = new Map();
    this.isEndOfWord = false;
  }
}
class Trie {
  constructor() {
    this.root = new Node();
  }
  insert(string) {
    let currentNode = this.root;
    for (const char of string) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(char, new Node(currentNode.value + char));
      }
      currentNode = currentNode.children.get(char);
    }
    currentNode.isEndOfWord = true;
  }
  search(string) {
    if (!string.trim().length) {
      return;
    }
    let currentNode = this.root;
    for (const char of string) {
      if (!currentNode.children.has(char)) {
        console.log('찾는 단어가 없습니다');
        return false;
      }
      currentNode = currentNode.children.get(char);
    }
    return currentNode;
  }
  autoCompleteString(string) {
    let currentNode = this.search(string);
    if (!currentNode) {
      return;
    }
    const result = [];
    this.findCompleteString(currentNode, result);
    console.log(result);
  }
  findCompleteString(currentNode, result) {
    if (!currentNode.children.size) {
      result.push(currentNode.value);
      return;
    }
    if (currentNode.isEndOfWord) {
      result.push(currentNode.value);
    }
    for (const key of Array.from(currentNode.children.keys())) {
      this.findCompleteString(currentNode.children.get(key), result);
    }
  }
}

const trie = new Trie();
trie.insert('abcde');
trie.insert('abcd');
trie.insert('abc');
trie.insert('ab');

trie.autoCompleteString('a'); //result :[ 'ab', 'abc', 'abcd', 'abcde' ]

과정을 살펴보면
1. 트라이 자료구조에 새롭게 노드를 생성해야 한다면, 제일 마지막 노드의 isEndOfWord 속성은 true가 된다
2. 만약 모든 노드가 기존에 존재해서 생성할 필요가 없다면, 제일 마지막으로 탐색하는 노드의 isEndOfWord 속성을 true로 변경
3. 자동완성 기능 메서드에서는 isEndOfWord가 true인 노드의 value만 찾아주면 된다

• 속성을 추가하지 않았다면, 해당 함수의 리턴값으로는 abcd 만 나오게 됨

한글은 그럼 어떻게 저장할까?

• 한글 자음모음 분리 라이브러리
• 자음모음 분리 뿐만 아니라, 다양한 기능(해당 글자가 자음인지 모음인지, 된소리인지 등)을 제공하는 라이브러리

Github에 업로드하면서 알게된 점

• 이미 보낸 PR이 있으면 내가 해당 파일을 commit push하면 보낸 PR에도 알아서 해당 내용이 업데이트됨