Tree (나무)

10 Jul 2019

Reading time ~4 minutes

Tree

Basics
Real Life Use Case
Implementation
Time Complexity

Tree Basics

alt

트리는 노드라는 단위로 이루어져 있는 자료구조다. 그리고 이 노드들 간의 계층적 구조가 존재한다.

트리의 노드는 고유의 정보를 가지고 있으며, 주변 노드와의 서열을 알 수 있는 reference 값을 가지고 있다.

트리에서 중요한 개념은 노드들 간에 서열이 있다는 점이다.

Root: 최상단에 위치한 노드는 root, 즉 뿌리라고 한다.
- 예: 위의 그림에서 1번노드가 root다.
Children & Parent: 노드는 여러 자식(children)노드을 가질 수 있으며, 자식노드가 존재하면 현재 노드는 부모(parent)노드가 된다. 즉, 자식과 부모관계가 되는 것이다.
- 예를 들어 1번 노드와 2번 노드를 보았을때 부모노드는 1번, 그리고 자식노드는 2번이라고 볼 수 있다.
- 1번의 자식 노드인 2번도 자식노드(4번,5번,6번)들이 있는데, 2번의 자식노드는 1번과는 부모자식 관계가 아니다.
Sibling: 같은 레벨, 같은 서열에 존재하는 노드들끼리의 관계는 형제/자매(sibling)이라고 한다.
- 4번노드, 5번노드, 6번노드, 7번노드 그리고 8번노드, 모두 서로 sibling 관계에 있다.
leaf: 자식이 없는 끝자락의 노드들을 가리킬 때는 잎사귀(leaf)노드라고 칭한다.
- 위의 그림에서 4번, 9번, 10번, 6번, 11번, 그리고 8번 노드가 leaf 노드다.

Real Life Use Case

File System On Computer
HTML Document Object Model (DOM)
Network Routing
Next Move In Games
Syntax Tree In Complier
Auto Corrector and Spell Checker

이와 같이 트리 자료구조는 엄청나게 다양하게 사용되고 있으며 매우 유용한 자료구조라고 볼 수 있다.

Tree Implementation

자 이제 트리를 코드로 구현해보자.

이 트리는 매우 간단한 형태의 트리이다.
여기의 트리 외에도 아주 많은 형태의 트리가 존재한다.

이번에 구현할 트리는 각각의 노드가 고유의 정보 값과 자식노드에 대한 레퍼런스값을 가지는 형태이다.

Constructing Tree/Node Object

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

Tree라는 생성자함수를 만들었고, value를 인자로 받는다.

생성자함수는 newTree라는 빈 객체를 리턴한다.

newTree 객체를 리턴하기전에 value 속성을 부여하고 인자로 받은 value를 값으로 할당한다.
그리고 children 이란 속성을 부여하고 빈 배열을 값으로 할당한다.

Modulizing Methods (메소드 모듈화)

트리에도 여러 method들이 존재한다. 이번에 구현할 method는 ‘addChild’와 ‘contains’ method이다.

위에서 만든 생성자 함수안에 value와 children 속성을 만든 것처럼 method들을 만들 수 있지만,
만약 method들을 생성자 함수와 분리해서 관리하고 싶을 때에는 method가 들어있는 객체를 만들고 생성자 함수안의 newTree의 값을 method가 들어있는 새로운 객체로 할당하면 된다.

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

var treeMethods = {};

treeMethods.addChild = function (value) {};

treeMethods.contains = function (target) {};

이렇게 하면 생성자함수와 method의 코드를 모듈화해서 관리할 수 있는 장점이 있다.

‘addChild’ Method Implementation

다음은 method들을 구현해볼 차례이다.

addChild는 말 그대로 노드를 만들어서 원하는 노드에 자식을 더하는 method이다.

위에서 children의 값을 배열의 형태로 주었기 때문에 자식을 더할때 array의 push method를 이용한다.

우선은 생성자함수를 이용해 노드를 만들고, 생성된 노드를 원하는 노드의 children 배열에 push 한다.

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

‘contains’ Method Implementation

contains는 트리안에 target 값이 존재하는지 판별하여 boolean을 리턴하는 method이다.

우선, 지금 children은 배열로 존재하고, children 노드들은 배열안의 칸에 Tree Object로 존재한다.

그렇기 때문에 우선 children 노드들을 하나하나 조사할 수 있도록 현재 노드의 children 수 만큼 판별한다.

자식노드의 value property의 값에 접근하고 target의 값과 비교하여 같다면 true 를 리턴하는 코드를 일단 적어보겠다.

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

자, 현재 노드의 자식노드 값을 비교해본 후 만약 찾지 못했다면, 그 다음은 자식노드들의 자식노드가 있는지 확인해보아야 한다.

자식노드의 자식노드에 찾는 target 값이 있을 수도 있으니 말이다.

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

else if (this.children[i].children.length) { //... }

자식노드들의 children property 값인 배열 길이가 1보다 크다면 자식이 존재하고 아니면 자식이 없는 걸로 판단하는 if 구문이다.

if (this.children[i].contains(target)) {
  return true;
}

자식노드의 자식이 있다고 판단되면, 그 다음은 그 자식노드들이 찾는 값을 알아볼 차례다. 그렇기 때문에 contains method를 현재 노드의 각각의 자식에 실행한다. 만약 true가 나오면 이 if 구문이 실행되면서 true를 리턴할 것이다.

return false;

만약 모든 노드를 찾아본 후에도 찾지 못했다면 for 문이 끝나고 false를 리턴한다.

Time Complexity

1. addChild

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

원하는 노드에 접근해서 바로 자식노드를 추가하는 것이므로 별다른 연산을 필요로 하지 않고, tree의 노드의 개수인 n 과는 무관한 작업이므로

addChild method의 time complexity는 O(1)이다.

2. contains

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

자식노드 하나하나 살피면서 값을 비교해보는 작업이므로, tree의 존재하는 노드의 개수인 n만큼의 시간이 소요되는 작업이므로

contains method의 time complexity는 O(n)이다.

Other types of tree

Binary Tree
Binary Search Tree
TRIE
Red Black Tree