Data Structure를 정리해보자. // Part3

Data Structure,

여러 데이터들의 묶음을 어떻게 사용하고 저장할지 정의한 것.

5. Tree

Node로 이루어진 계층적인 형태를 갖는 자료구조.
많은 양의 정보를 보기 쉽게 정리할 때 유용하다.

족보나 컴퓨터의 디렉토리 구조나 조직도와 같은 형태를 생각하면 된다.

위 그림을 보면서 Tree에 대해서 살펴보자.

Tree는 각 Node들로 구성이 되어있고 최상위에는 Root Node라는 시작점이 있다.
이 각 Node들은 관계에 따라 Parent Node가 될 수도 있고 Child Node가 될 수도 있다.
물론, 둘다 될 수도 있고.

제일 처음 Root Node를 만들고 Child Node를 추가할 수 있다.
Root Node만이 Childe Node를 만들 수 있는 것이 아니라 각 Node들은 모두 Child Node를 가질 수 있다.

루트를 기준으로 다른 Node에 접근할 수 있는 거리를 Depth라고 한다.

Node와 Node를 잇는 선은 Edge라고 한다.

아래는 Tree의 기본적인 메소드들.

class TreeNode {
  constructor(value) {
    this.value = value; 
    this.children = [];
  }

  insertNode(value) {
    let newTreeNode = new TreeNode(value);
    this.children.push(newTreeNode);
  }

  contains(value) {
    if(this.value === value) {
      return true;
    } else {
        for(let i = 0; i < this.children.length; i++) {
          if(this.children[i].contains(value)) {
            return true
          }
        }
      }
    return false;
  }
}

6. BinarySearchTree(BST), 이진탐색구조

Tree의 한 형태지만 각 Node는 최대 2개의 Childe Node를 가질 수 있다.

BST의 특징은,
Parent의 왼쪽 하위의 값이 Parent의 값보다 작아야하고,
반대로 Parent의 오른쪽 하위의 값이 Parent의 값보다 커야한다.

BST를 탐색하는 방법은
1. 깊이 우선 탐색(DFS, Depth-First Searching)
: Root를 시작으로 점차 깊이 들어갔다가 가장 깊은 Depth까지 도달했을 때 나왔다가 다시 가장 깊은 Depth로 들어가면서 Tree를 탐색하는 방법.
2. 너비 우선 탐색(BFS, Breath-First Searching)
: 하나의 Depth의 각 Node들을 먼저 탐색하고(Sibling을 탐색한다고도 한다) 다음 Depth로 들어가면서 전체 Tree를 탐색하는 방법.

아래는 BST의 기본적인 메소드들.

class BinarySearchTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null; 
    this.right = null;
  }

  insert(value) {    
    if (value > this.value) {
      if(this.right === null) {
        let newNode = new BinarySearchTreeNode(value);
        this.right = newNode;
      } else {
          this.right.insert(value);
      }
    }
    if (value < this.value) {
      if(this.left === null) {
        let newNode = new BinarySearchTreeNode(value);
        this.left = newNode;
      } else {
          this.left.insert(value);
        }
    }
  }

  contains(value) {
    if(this.value === value) {
      return true;
    } else {
        if(this.value > value) {
          if(this.left === null) {
            return false;
          } else if(this.left.contains(value)) {
            return true;
          }
        } else {
          if(this.right === null) {
            return false;
          } else if(this.right.contains(value)) {
            return true;
          }
        }
      }
      return false;
  }
}