Tree

Tree 구조

나무를 뒤집어 놓은 것처럼 하나의 노드(root)로 부터 시작되어 자식 노드(child node)들이 가지를 치듯 뻗어 나가는 구조이다

아래 그림과 같이 HTML이 좋은 예이다. 루트로부터 시작해서 아래 자식 노드들이 뻗어 나가는 구조이다.

 

트리 구조 용어

• 루트(root): 부모가 없는 노드
• 리프(leaf): 자식이 없는 노드
• 내부 노드: 루트도 리프도 아닌 노드
• 엣지(edge) or 브랜치(branch): 부모와 자식이 이어지는 연결 선
• 형제(siblings): 부모가 같은 노드들
• path: 루트에서 자식 노드까지 가는 경로
• 노드의 높이: 루트에서 자식 노드 사이의 엣지(edge) 개수
• 노드의 깊이: 리프에서 해당 노드 사이의 엣지(edge) 개수
• 트리의 높이: 모든 노드의 높이 값 중 최대 값
• 트리의 깊이: 모든 노드의 깊이 값 중 최대 값
• 노드의 크기: 자기 자신을 포함한 그 노드가 가진 자식 노드의 수

Big o

• insertion: O(1)
• deletion: O(n)
• search: O(n)

 

javascript로 Tree 구현

 

아래는 tree를 구현한 자바스크립트 소스이다.
노드를 자식으로 추가해주고 노드가 포함되어 있는지 확인해주는 기능까지 구현한 소스이다.

 

const Tree = function (value) {
  var newTree = Object.create(treeMethods);
  newTree.value = value;
  newTree.children = [];
  return newTree;
};

const treeMethods = {};

treeMethods.addChild = function (value) {
  var node = new Tree(value);
  this.children.push(node);
};

treeMethods.contains = function (target) {
  var result = false;

  function recusion(node) {
    if (node.value === target) {
      result = true;
      return;
    }
    if (node.children.length > 0) {
      for (var i = 0; i < node.children.length; i++) {
        recusion(node.children[i]);
      }
    }
  }

  recusion(this);

  return result;
};

const tree = new Tree(3);
tree.addChild(2);

• 시간 복잡도
  • insertion: O(1)
  • deletion: O(n)
  • search: O(n)