트리(Tree)

방향 그래프의 일종으로 정점을 가리키는 간선이 하나존재한다.

가장 상위의 정점을 Root, 각 정점을 Node, 더 이상 자식이 없는 정점을 Leaf Node라고 합니다.
이밖에도 Root로부터 몇번째 깊이인지를 표현하는 Level 한 정점에서 뻗어나가는 간선의 수를 Degree라고 표현합니다.
주로 조직도, 소프트웨어의 디렉토리 구조에 사용됩니다.

트리의 특징

루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 갖습니다.
따라서 정점이 N개인 트리의 간선 수 = N - 1 이 성립하고
루트에서 특정 정점으로 가는 경로는 유일합니다.

이진 트리 (Binary Tree)

이진 트리는 각 정점이 최대 2개의 자식을 가지는 트리를 말합니다.

완전 이진 트리: 마지막 레벨을 제외하고 모든 정점이 존재합니다.
포화 이진 트리: 완전 이진 트리의 마지막 레벨까지 모든 정점이 존재합니다.
편향 트리: 한 방향으로만 정점이 이어집니다.

이진트리의 특징

• 정점이 N개인 이진 트리는 최악의 경우 높이가 N
• 높이가 h인 포화 이진 트리는 2^h - 1개의 정점을 가진다.
• 정점이 N개인 포화/완전 이진트리는 높이가 logN

일반적인 이진 트리를 사용하는 경우는 많지 않지만 다음과 같은 자료구조에 응용됩니다.
이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리

JavaScript 구현

이진트리는 배열과 연결 리스트로 구현이 가능합니다.
다음 트리 구조를 구현해봅시다.

배열

배열의 경우
왼쪽 정점: index * 2,
오른쪽 정점: index * 2 + 1,
부모정점 = Math.floor(index / 2)가 성립합니다.

// 0번 index는 편의를 위해 비우는것이 좋다.
const tree = [
	undefined,
  	// 1
	9,
	// 1*2, 1*2+1
  	3, 8,
	// 2*2, 2*2+1, 3*2, 3*2+1
  	2, 5, undefined, 7,
	// 4*2, 4*2+1, 5*2, 5*2+1
	undefined, undefined, undefined, 4
];

연결 리스트

연결 리스트로 구현할때는 기존 연결 리스트의 노드에 next대신 left, right를 사용합니다.
그 다음 left와 right에 값을 연결하면 됩니다.

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

class Tree {
  constructor(node) {
    this.root = node;
  }

  display() {
    // Level Order
    const queue = new Queue();
    queue.enqueue(this.root);
    while (queue.size()) {
      const currNode = queue.dequeue();
      console.log(currNode.value);
      if (currNode.left) queue.enqueue(currNode.left);
      if (currNode.right) queue.enqueue(currNode.right);
    }
  }
}

const tree = new Tree(new Node(9));

tree.root.left = new Node(3);
tree.root.right = new Node(8);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(7);
tree.root.left.right.right = new Node(4);

큐 사용

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front++;
    return value;
  }
  peek() {
    return this.queue[this.front];
  }

  size() {
    return this.rear - this.front;
  }
}