자료구조 5. Tree

Tree

1.Tree

  트리는 노드로 구성된 계층적 자료구조로 나무를 거꾸로 세운 모습이다. 트리는 1개 이상의 노드로 구성되며, 최상위 노드인 루트로부터 시작하여 루트의 자식노드가 존재하고 그 자식노드의 자식노드가 존재하는 구조가 반복된다. 따라서 트리는 루트와 전체 트리의 부속트리로 구성된다고 말할 수 있다.

 

2.용어

• 노드의 차수(degree): 노드에 연결된 또 다른 노드의 갯수. 즉, 노드의 자식노드 갯수이자 부속트리 개수이다.
  • ex. 위 그림에서 노드 1의 차수는 2이고, 노드 2의 차수는 0이다.
• 관계에 따른 노드 구분
  
  • 부모 노드(parend node): 노드를 서브트리로 갖는 노드. 
    • ex. 위 그림에서 노드 4의 부모 노드는 노드 1이다.
  • 자식 노드(child node): 부모에 속하는 노드. 
    • ex. 노드 1의 자식 노드는 노드 4, 5이다.
  • 형제 노드(sibling node): 같은 부모를 갖는 노드. 
    • ex. 노드 1, 2, 3은 서로 형제 노드이다.
  • 조상 노드(ancestor node): 노드의 부모 노드들의 총 집합.
  • 자손 노드(descendant node): 노드의 부속트리에 있는 모든 노드들.
• 차수에 따른 노드 구분
  • 단말노드(left node): 차수가 0인 노드. 즉 트리의 맨 마지막에 존재하는 노드들이다. 
    • ex. 노드 4, 5, 6은 단말노드이다.
  • 비단말노드(non-terminal node): 차수가 1 이상인 노드.
• 깊이(depth of node): 루트로 부터 노드까지의 거리. 루트의 깊이는 0이다.
  • ex. 노드 4의 깊이는 2이다.
• 트리의 높이(height of tree): 트리에 속한 노드의 최대 레벨
  • ex. 트리의 높이는 2이다.
• 레벨(level): 루트로 부터의 노드의 깊이. 루트의 레벨은 1이다.
  
  • ex. 노드 4와 6은 모두 레벨이 3이다.

 

3. 구현

  트리에 삽입/조회 만 구현하였다.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  insertNode(value) {
    let node = new TreeNode(value);
    this.children.push(node);
  }

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

 

---

참고 사이트

트리 용어 [정보통신기술용어해설]