IMMERSIVE

트리

본 장 이해 후, 다음 프로젝트를 해보세요: https://drive.google.com/drive/folders/1ljJLJQsosmDDH6RY3_tesgMM-WRlnw9S?usp=sharing

일반적인 트리 자료 구조는 자식 노드를 지닌 노드들로 구성된다. 즉 계층형 데이터 관리 구조이다. 첫 번째이자 가장 상위 노드를 루트 노드(root node)라고 한다. 한 노드의 하위에있는 노드를 child node라고하고, child node의 상위 노드를 parent node라고 한다. 트리형 자료구조의 가장 대표적인 것이 이진탐색트리이다. 이번 시간에 이진탐색 트리를 알아보고, 구현하보도록 하겠습니다.

트리의 속성 중 가장 중요한 것이 '루트노드'를 제외한 모든 노드는 단 하나의 부모노드를 갖는다는 특징이 있다. 이 속성에서 파생적으로 나오는 특징이 있는데

임의의 노드에서 다른 노드로 가는 경로는 유일하다.
사이클이 존재하지 않는다.
모든 노드는 서로 연결되어 있다.
노드 연결선(가지)을 자르면 트리가 2개로 분리된다.
노드 연결선(가지)의 수는 노드의 수 - 1이다.

이진트리

각 부모에 연결된 노드의 수가 최대 2개인 트리를 이진트리라고 한다. 이러한 이진트리에 조건이 투가된 것이 이진탐색트리이다. 이진 트리는 많은 양의 노드를 낮은 높이에서 관리할 수 있다는 점에서 데이터 효율성이 높아진다. 데이터 저장 및 탐색 등의 다양한 목적으로 사용할 수 있다.

포화 이진 트리

맨 마지막 자식 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리

완전 이진 트리

모든 노드들이 왼쪽부터 차례로 채워진 트리

높이 균형 트리

왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이상 차이 나지 않는 트리

형항 이진 트리

노드가 한쪽으로만 치우친 트리의 형태.

탐색빙법: 이진(탐색)트리를 순회하는 대표적인 방법들이다.

1. 깊이우선: 가장 자식노드부터 탐색하기 시작

1. In-order

left -> root -> right
4 -> 2 -> 5 -> 1-> 3

2. Pre-order

Root -> Left -> Right
1 -> 2 -> 4 -> 5 -> 3

3. Post-order

Left -> Right -> Root
4 -> 5 -> 2 -> 3 -> 1

2. 너비우선: 부모노드부터 차례로 탐색하기 시작

이진탐색트리(Binary Search Tree)

이진탐색트리는 이진탐색과 링크드 리스트를 결합한 자료구조의 일종이다. 효율적인 탐색 능력을 유지하면서, 자료 입력과 삭제를 가능하게 만들어졌다.

이진탬색트리의 기본적인 모습은 하나의 노드에 두개의 자식이 있다. 왼쪽 자식의 경우 부모보다 작은 수, 오른쪽 자식의 경우 부모보다 큰 수가 들어간다. 또한 중복된 노드가 없어야하고, 작게보면 각각 노드들 자체도 모두 이진트리의 모습을 하고 있다.

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

  insert(value) {
    if (value <= this.value) {
      if (!this.left) {
        this.left = new BST(value);
      } else {
        this.left.insert(value);
      }
    } else if (value > this.value) {
      if (!this.right) {
        this.right = new BST(value);
      } else {
        this.right.insert(value);
      }
    }
  }

  contains(value) {
    if (value === this.value) {
      return true
    } else if (value < this.value) {
      if (!this.left) {
        return false;
      } else {
        return this.left.contains(value);
      }
    } else if (value > this.value) {
      if (!this.right) {
        return false;
      } else {
        return this.right.contains(value);
      }
    }
  }
  depthFirstTraversal(iterator, order) {
    if (order === 'pre-order') {
      iterator(this.value);
    }
    if (this.left) {
      this.left.depthFirstTraversal(iterator, order);
    }
    if (order === 'in-order') {
      iterator(this.value);
    }
    if (this.right) {
      this.right.depthFirstTraversal(iterator, order);
    }
    if (order === 'post-order') {
      iterator(this.value);
    }
  }
  breadthFirstTraversal(iterator) {
    const queue = [this];
    while (queue.length) {
      let treeNode = queue.shift();
      iterator(treeNode);
      if (treeNode.left) {
        queue.push(treeNode.left);
      }
      if (treeNode.right) {
        queue.push(treeNode.right);
      }
    }
  }
  getMinimun() {
    if (this.left) {
      return this.left.getMinimun();
    } else {
      return this.value;
    }
  }

  getMaximum() {
    if (this.right) {
      return this.right.getMaximum();
    } else {
      return this.value;
    }
  }
}

const bst = new BST(1);
bst.left = new BST(2);
bst.right = new BST(3);
bst.left.left = new BST(4);
bst.left.right = new BST(5);

// console.log(bst);

bst.depthFirstTraversal(console.log, 'post-order');

트리