트리

트리(Tree)

• 그래프의 일종으로 두 노드 사이의 하나의 간선만 연결되어 있는, 최소 연결과 계층 형태의 비선형 자료 구조

• 노드(node) : 하나 이상의 값을 갖는 객체 단위

• 간선(edge) : 두 노드를 연결하는 선

• 루트 노드(Root node) : 부모가 없는 최상위 노드

• 단말 노드(Leaf node) : 자식이 없는 노드

• 부모 노드(Parent node) : 특정 Sub-Tree 내에서의 상위 노드

• 자식 노드(Child node) : 특정 Sub-Tree 내에서의 하위 노드

• 형제(Sibling) : 부모가 없는 최상위 노드

• 트리 특징

  • 주요 특징 : '최소 연결 트리'로 불림, 계층 모델, 방향 비순환 그래프(DAG: Directed Acyclic Graph) 한 종류
  • 트리 종류 : 이진 트리, 이진 탐색 트리, AVL 트리, 힙(Heap)
  • 노드 크기(size) : 자신을 포함한 모든 자손 노드의 개수
  • 노드 깊이(depth) : 루트에서 특정 노드에 도달하기 위한 간선의 개수
  • 노드 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
  • 노드 차수(degree) : 노드가 지닌 가지의 수
  • 트리 차수(tree degree) : 트리의 최대 차수
  • 트리 높이(height) : 루트 노드에서 가장 깊숙이 있는 노드의 깊이

• 트리 순회

  • 트리 구조에서 각각의 노드를 정확히 한 번씩 체계적인 방법으로 방문하는 과정
  • N(Node) : 해당 노드를 방문
  • L(Left) : 왼쪽 서브 트리로 이동
  • R(Right) : 오른쪽 서브 트리로 이동
  • 순회 방식
    • 전위 순회(Pre-order) : N-L-R
    • 중위 순회(In-order) : L-N-R
    • 후위 순회(Post-order) : L-R-N
    • 층별 순회(Level-order) : 낮은 Level부터 순차적으로 순회

이진 트리(Binary Tree)

• 각각의 노드가 최대 두개의 자식 노드를 가지는 트리 자료 구조

• 활용 방식

  • 검색과 정렬 : 이진 탐색 트리와 이진 힙 구현에 활용
  • 허프만 코딩 : 연관 분기 구조 위한 데이터 표현에 활용

• 이진 트리의 종류

  • 포화 이진 트리(Perfect binary Tree)
  • 완전 이진 트리(Complete binary Tree)
  • 정 이진 트리(Full binary Tree)
  • 편향 이진 트리(Skewed binary Tree)
  • 균형 이진 트리(Balanced binary Tree)

• 포화 이진 트리(Perfect binary Tree)

  • 모든 레벨의 노드가 가득 채워져 있는 트리
  • 특징
    • Leaf 노드를 제외한 모든 자식은 2개의 노드를 보유
    • 노드의 개수 n = 2^h - 1

• 완전 이진 트리(Complete binary Tree)

  • 마지막 레벨 전까지 노드가 가득 채워져 있고, 마지막 레벨은 왼쪽부터 순차적으로 채워져 있는 트리
  • 특징
    • 배열을 사용해 효율적인 표현 가능
    • 노드의 개수 : n < 2^h - 1

• 정 이진 트리(Full binary Tree)

  • 모든 노드가 0개 또는 2개의 자식 노드만 갖는 트리
  • 특징
    • proper 또는 plane 이진 트리라고도 불림
    • 노드의 개수 : n <= 2^h - 1

• 편향 이진 트리(Skewed binary Tree)

  • 왼쪽 혹은 오른쪽으로 편향되게 치우쳐 있는 트리
  • 특징
    • 각각의 높이에 하나의 노드만 존재
    • 노드의 개수 : h

• 균형 이진 트리(Balanced binary Tree)

  • 삽입/삭제가 이루어 질 때, 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차를 1 이하로 맞추는 이진 탐색 트리
  • 특징
    • 서브 트리 높이 차이가 항상 1 이하로 유지
    • 균형 트리 종류 : AVL 트리, Red-Black 트리, B트리, B+트리, B*트리

• 이진 트리 구현

// Node() : value와 left, right node 저장을 위한 생성자
function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

// BinaryTree() : 시작 노드인 root를 저장하기 위한 생성자
function BinaryTree() {
  this.root = null;
}

// _insertNode() : 재귀로 트리를 순회하면 노드 추가 (내부 사용)
BinaryTree.prototype._insertNode = function (node, value) {
  if (node === null) {
    node = new Node(value);
  } else if (value < node.value) {
    node.left = this._insertNode(node.left, value);
  } else if (value >= node.value) {
    node.right = this._insertNode(node.right, value);
  }
  return node;
};

// insert() : 노드 추가
BinaryTree.prototype.insert = function (value) {
  this.root = this._insertNode(this.root, value);
};

// _preOrderTraverseNode() : 재귀로 트리를 순회하며 전위 순회(내부 사용)
BinaryTree.prototype._preOrderTraverseNode = function (node, callback) {
  if (node === null) {
    return;
  }

  callback(node);
  this._preOrderTraverseNode(node.left, callback);
  this._preOrderTraverseNode(node.right, callback);
};

// preOrderTraverse() : 전위 순회하며 노드 출력
BinaryTree.prototype.preOrderTraverse = function (callback) {
  this._preOrderTraverseNode(this.root, callback);
};

// _inOrderTraverseNode() : 재귀로 트리를 순회하며 중위 순회(내부 사용)
BinaryTree.prototype._inorderTraverseNode = function (node, callback) {
  if (node === null) {
    return;
  }

  this._inOrderTraverseNode(node.left, callback);
  callback(node);
  this._inOrderTraverseNode(node.right, callback);
};

// inOrderTraverse() : 중위 순회하며 노드 출력
BinaryTree.prototype.inOrderTraverse = function (callback) {
  this._inOrderTraverseNode(this.root, callback);
};

// _postOrderTraverseNode() : 재귀로 트리를 순회하며 후위 순회(내부 사용)
BinaryTree.prototype._postOrderTraverseNode = function (node, callback) {
  if (node === null) {
    return;
  }

  this._postOrderTraverseNode(node.left, callback);
  this._postOrderTraverseNode(node.right, callback);
  callback(node);
};

// postOrderTraverse() : 후위 순회하며 노드 출력
BinaryTree.prototype.postOrderTraverse = function (callback) {
  this._postOrderTraverseNode(this.root, callback);
};

// Queue 객체 추가
function Queue(array) {
  this.array = array ? array : [];
}
Queue.prototype.isEmpty = function () {
  return this.array.length == 0;
};
Queue.prototype.enqueue = function (element) {
  return this.array.push(element);
};
Queue.prototype.dequeue = function () {
  return this.array.shift();
};

// levelOrderTraverse() : 층별 순회하며 노드 출력
BinaryTree.prototype.levelOrderTraverse = function (callback) {
  let q = new Queue();
  let node;
  q.enqueue(this.root);
  while (!q.isEmpty()) {
    node = q.dequeue();
    callback(node);
    if (node.left !== null) q.enqueue(node.left);
    if (node.right !== null) q.enqueue(node.right);
  }
};

이진 탐색 트리

• 현재 노드를 기준으로 왼쪽에는 작은 값, 오른쪽에는 큰 값으로 정렬해 놓는 이진 트리 기반 자료 구조

// Node() : value와 left, right node 저장을 위한 생성자
function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

// BinarySearchTree() : 시작 노드인 root를 저장하기 위한 생성자
function BinarySearchTree() {
  this.root = null;
}

// _inOrderTraverseNode() : 재귀로 트리를 순회하며 중위 순회(내부 사용)
BinarySearchTree.prototype._inorderTraverseNode = function (node, callback) {
  if (node === null) {
    return;
  }

  this._inOrderTraverseNode(node.left, callback);
  callback(node);
  this._inOrderTraverseNode(node.right, callback);
};

// inOrderTraverse() : 중위 순회하며 노드 출력
BinarySearchTree.prototype.inOrderTraverse = function (callback) {
  this._inOrderTraverseNode(this.root, callback);
};

// _insertNode() : 재귀로 트리를 순회하면 노드 추가 (내부 사용)
BinarySearchTree.prototype._insertNode = function (node, value) {
  if (node === null) {
    node = new Node(value);
  } else if (value < node.value) {
    node.left = this._insertNode(node.left, value);
  } else if (value >= node.value) {
    node.right = this._insertNode(node.right, value);
  }
  return node;
};

// insert() : 노드 추가
BinarySearchTree.prototype.insert = function (value) {
  this.root = this._insertNode(this.root, value);
};

// _minNode() : 반복문으로 트리를 순회하며 최솟값 노드 탐색
BinarySearchTree.prototype._minNode = function (node) {
  if (node === null) {
    return null;
  }

  while (node && node.left !== null) {
    node = node.left;
  }

  return node.value;
};

// _maxNode() : 반복문으로 트리를 순회하며 최댓값 노드 탐색
BinarySearchTree.prototype._maxNode = function (node) {
  if (node === null) {
    return null;
  }

  while (node && node.right !== null) {
    node = node.right;
  }

  return node.value;
};

// min() : 최솟값 노드 탐색
BinarySearchTree.prototype.min = function () {
  return this._minNode(this.root);
};

// max() : 최댓값 노드 탐색
BinarySearchTree.prototype.max = function () {
  return this._maxNode(this.root);
};

// _searchNode() : 재귀로 트리를 순회하며 값을 만족하는 노드 탐색
BinarySearchTree.prototype._searchNode = function (node, value) {
  if (node === null) {
    return false;
  }

  if (node.value === value) {
    return true;
  } else if (node.value > value) {
    return this._searchNode(node.left, value);
  } else if (node.value < value) {
    return this._searchNode(node.right, value);
  }
};

// search() : value 노드 탐색
BinarySearchTree.prototype.search = function (value) {
  return this._searchNode(this.root, value);
};

// _finMinNode() : 반복문으로 트리를 순회하며 최솟값을 보유한 노드 탐색
BinarySearchTree.prototype._findMinNode = function (node) {
  while (node && node.left !== null)
    node = node.left;

  return node;
};

// _removeNode() : 재귀로 트리를 순회하며 값을 만족하는 노드를 찾고 삭제
BinarySearchTree.prototype._removeNode = function (node, value) {
  if (node === null)
    return null;
  if (node.value === value) {
    // case 1 : leaf node
    if (node.left === null && node.right === null) {
      node = null;
    }
    // case 2 : 1 child node
    else if (node.left === null) {
      node = node.right;
    } else if (node.right === null) {
      node = node.left;
    }
    // case 3 : 2 child node
    else {
      let aux = this._findMinNode(node.right);
      node.value = aux.value;
      node.right = this._removeNode(node.right, aux.value);
    }
  } else if (node.value > value) {
    node.left = this._removeNode(node.left, value);
  } else if (node.value < value) {
    node.right = this._removeNode(node.right, value);
  }
  return node;
};

// remove() : 노드 삭제
BinarySearchTree.prototype.remove = function (value) {
  root = this._removeNode(this.root, value);
};