[Data-Structure] Tree (트리)와 Binary Search Tree (이진 탐색 트리) (1)Tree 구조란

오늘은 트리 구조(Tree)와 이진 탐색 트리(Binary Search Tree)에 대해서 공부해보았다.

트리 구조란 노드로 구성된 계층적 자료구조이다. 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 트리 구조를 구현할 수 있다.

트리 구조 예시

 

트리 구조와 관련하여 반드시 알아야 할 개념들이다. [정보통신기술용어해설] 참조

• A, B, C, D 등 트리의 구성요소를 노드(node) 라고 한다.
• 위 그림의 A처럼, 트리 구조에서 최상위에 존재하는 노드를 root이다.
• 루트를 기준으로, 다른 노드로의 접근하기 위한 거리를 depth 라고 한다.
• 같은 부모를 가지면서 같은 depth에 존재하는 노드들은 sibling 관계에 있습니다. (같은 부모를 가진 노드들의 집합)
• 그림에서 A는 B와 C의 부모(parent) 이고, B와 C는 A의 자식(child) 이다.
• 노드와 노드를 잇는 선을 edge 라고 한다.
• 자식이 없는 노드는 leaf 라고 한다.

여기서 depth와 height의 차이를 보자면 depth는  루트 노드에서 자신까지 가는 경로의 길이(루트 노드의 깊이는 0이다.)를 뜻하며
height는 그 노드와 단말 노드 사이의 경로의 최대 길이이다.(가장 긴 깊이)

배열을 이용해서 Tree를 간단하게 구현해 볼 수 있다. 

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

  // 트리에 노드를 추가
  insertNode(value) {
    let node = new TreeNode(); // 추가할 노드 생성
    node.value = value; // 노드의 값 변경
    this.children.push(node); // 현재 노드에 children 배열로 해당 노드를 추가
  }

  // 트리에 해당 노드가 존재하는지 여부를 반환
  contains(value) {
    if(this.value === value){ // 현재 노드의 value 값과 value값이 같다면 바로 리턴 true
      return true;
    }
    for(let el of this.children){ // children 배열에서 요소를 하나씩 꺼내서 비교
      if(el.children.length !== 0){ // el이 children을 가지고 있다면
        for(let childEl of el.children){
          let child = childEl.contains(value); // 재귀 형태로 value 값을 체크해주고
          if(child === true){ // 이 값이 true인지 비교 후 true가 아니면 다음 루프로 돌아가도록 해줌
            return true;
          }
        }
      }
      if(el.value === value){ // el이 children을 가지지않는데 value가 같다면
        return true;
      }
    }
    return false; // 모든 루프를 통과 후에도 같은 값이 없다면 false 리턴
  }
}

 

간단한 사용 예시를 보자면

let rootNode = new Tree(null); // rootNode 생성

rootNode.insertNode(5);
rootNode.insertNode(6);

rootNode.children[0].insertNode(7);
rootNode.children[1].insertNode(8);

rootNode.contains(7); // true
rootNode.contains(8); // true

// 구조
/*
   null -> rootNode
 5      6
7      8

*/

이렇게 된다. 

다음은 이진 탐색 트리(Binary Search Tree)에 대해서 알아보겠다.