TIL 7/10 Binary Tree

학습내용

오늘은 Binary Search Tree 에 대해서 학습했다. 이진 트리는 트리구조를 이해하는데 도움이 된다. 트리를 구현해보면서 어떻게 값이 추가되고 비교되고 값을 찾는지 구조를 보면 이해하기가 조금은 더 수월하다. 이진 트리를 class로 구현해서 살펴보자.

class BinaryTree {
  constructor(inputValue) {
    this.value = inputValue;
    this.left = null; // 초기에 null의 falsy 한 값을 준다.
    this.right = null;
  }
	
  push(inputValue) { // input이 value 보다 작은경우 큰경우를 나눈다.
    if (this.value > inputValue) { // 작은 경우는 왼쪽으로
      if (this.left === null) { 
        this.left = new BinaryTree(inputValue);
      } else {
        this.left.push(inputValue);
      }
    } else if (this.value < inputValue) { // 큰 경우는 오늘쪽으로 
      if (this.right === null) {
        this.right = new BinaryTree(inputValue);
      } else {
        this.right.push(inputValue);
      }
    }
  }
  
  isValue(searchValue) {
    if (this.value === searchValue) {
      return true;
    } else if (this.value > searchValue) {
      if (this.left !== null) { 
        return this.left.isValue(searchValue);
      }
    } else if (this.value < searchValue) {
      if (this.right !== null) {
        return this.right.isValue(searchValue);
      }
    }
    return false;
  }
}

효율적이고 멋진 좋은 코드는 아니어도 동작하는 코드다. 최대한 보기 쉽게 적는게 좋다고 생각한다. push 할때는 추가하려는 값이 현재 노드의 값과 비교해서 작으면 왼쪽에 넣고 크면 오른쪽에 넣는다. 그런데 값이 넣으려는 왼쪽 오른쪽에 있으면 이동하려는 노드의 push 함수를 재귀한다. 이렇게 작고 큰 경우를 왼쪽 오른쪽으로 나누어서 값이 추가된다. 이런 방식이면 항상 왼쪽은 부모노드보다 작고 오른쪽은 부모노드보다 큰 상태로 들어가게 된다. 이렇게 Tree 구조는 추가 할때 부터 정렬되어 들어간다. 그래서 검색이 다른 자료구조보다 빠르다.

느낀점

정말 어려웠던 자료구조중 하나다. 지금도 어렵고 적응하는데는 시간이 많이 걸릴 것 같지만 그래도 여러번 연습하면서 이전보다는 더 이해되는 부분이 있었다. 재귀의 방식도 조금 더 알게 되었다. 실제로 어떻게 구현되는지 코드로 써보니 구조와 목적이 조금 더 잘 보였다. 시간은 좀 걸려도 모르는 개념은 그리면서, 코드로 작성해보면서 공부하는 것도 좋은 방법이라는 것을 알았다. 너무 오래걸리지 않는 선에서 조절하면서 공부해야겠다. 오늘은 좀 오래걸렸다. ;;