Tree

Tree

• 노드들의 집합체이며 계층적인 관계를 나타내는 자료구조
• 첫번째 노드 루트라고 부르는 뿌리노드가 존재(A)
• 루트노드는 다양한 개수의 자녀들을 가질 수 있음
• 반대로 루트 노드를 제외한 각각의 노드는 정확하게 하나의 노드를
  부모노드로 가지게 됨.
  
• 실제 나무는 뿌리가 아래에 있고 잎이 위에 있지만, Tree는 그와 반대로 위치함.
• Tree구조를 쉽게 볼 수 있는 곳은 윈도우의 탐색기나 맥os의 Find 프로그램에 있는 디렉터리들.

Tree에서 사용되는 용어들

• degree(차수): 어떤 노드가 가지고 있는 자식노드의 수(i:3)

• sibling(자매) 노드: 같은 부모노르를 가지는 노드들(j,k,l)

• 자녀의 갯수에 따라 노드 구분
  

  • leaf 노드: 자녀가 없는(차수가 0인) 노드(j,k,l)
  • internel 노드: leaf노드를 제외하고 자식노드가 있는 모든 노드들(h,i)

• 자녀 순서의 유무

  • unordered: 자녀의 순서가 무시
  • ordered: 순서가 중요하다면(예) 가계도)
    -sequence: 경로, 바로 앞에 있는 노드가 그 다음 노드의 부모여야만 경로가 정의
    
  • B~G까지의 길이는 2이고 노드의 수는 3

• depth
  

  • tree는 반드시 어떤 한 노드와 루트 사이의 경로는 유니크하다.
  • root노드로부터 그 해당 노드까지의 경로의 길이
  • 여기서 E노드의 depth는 2, L노드의 depth는 3

• height

  • 모든 노드의 depth 가운데 가장 큰 것
  • root노드 밖에 존재하지 않는 경우는 0
  • 아무 노드도 없을 경우는 -1

• ancestor(조상), descendant(자손)

  • tree 내, A노드에서 B노드까지 경로가 존재했을때
  • A노드는 조상, B노드는 자손
  • 나는 나의 조상이냐? tree에선 노드 자신은 조상이면서 동시에 자손이라고 함.
    
  • root노드는 모든 노드의 조상

• tree는 linked-list 자료구조로 표현함
  

  • A노드는 자식노드로 B,C,D를 갖고 있기 때문에 3개의 포인터를 갖고 있으며, 각각의 포인터는 자식의 노드를 참조하고 있다.
  • B노드는 2개, C노드는 1개 D노드는 2개의 포인터를 갖고 있다.

• 트리 구현

class Tree {
  constructor(value) {
    // constructor로 만든 객체는 트리의 Node가 됩니다.
    this.value = value;
    this.children = [];
  }

  // 트리의 삽입 메서드를 만듭니다.
  insertNode(value) {
    // 값이 어떤 이름으로 만들어지고 어느 위치에 붙는지 떠올리는 것이 중요합니다.
    // 트리에 붙게 될 childNode를 만들고, children에 넣어야 합니다.
    const childNode = new Tree(value);
    this.children.push(childNode);
  }

  // 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
  contains(value) {
    // root vertex에서 값이 포함되어 있다면 true를 반환
    if (this.value === value) {
      return true;
    }
    // children 배열을 순회하며 childNode를 탐색해서 값이 있는 경우 true 반환.
    for (let i = 0; i < this.children.length; i++) {
      const childNode = this.children[i];
      if (childNode.contains(value)) return true;
    }

    // 전부 탐색했음에도 불구하고 찾지 못했다면 false를 반환합니다.
    return false;
  }
}

출처

• [집콕]인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고
• Javascript를 이용한 tree 구현