트리(Tree)

• 무방향 그래프이 한 구조로 하나의 뿌리로부터 사방으로 뻗은 형태의 자료구조
• 두 노드 사이의 하나의 간선만 연결되어있는 최소 연결과 계층 형태
• 이진 트리, 이진 탐색 트리, AVL 트리, 힙(Heap) 의 트리 종류가 존재
• 트리의 순회: 트리 구조에서 각각의 노드를 정확히 한 번씩 체계적인 방법으로 방문하는과정
• 순회 종류에는 전위, 중위, 후위, 층별 순회가 존재
  • 전위 순회(Pre-order): N - L - R ⇒ 주로 트리를 복사할 때 사용
    
  • 중위 순회 (In-order) : L - N - R ⇒ 이진 탐색 트리에서 정렬된 순서대로 값을 가져올 때 사용
    
  • 후외 순회 (Post-order) : L - R - N ⇒ 주로 트리 삭제에 사용
    

⏱️ 시간복잡도

이진트리 기준

• 균형이 유지되었을 경우: O(logN)
• 균형이 유지되지 않았을 경우: O(N)

🔠 용어

	설명
노드(Node)	트리 구조를 이루는 모든 개별 데이터
간선(Edge)	두 노드를 연결하는 선
루트(Root)	트리 구조의 시작점이 되는 노드
부모 노드(Parent Node)	두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 부모 노드
자식 노드(Child Node)	두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
형제 노드(Sibling Node)	같은 부모 노드를 갖는 노드
단말 노드(Leaf)	트리 구조의 끝지점이고 자식 노드가 없는 노드

	설명
크기(Size)	자신을 포함한 모든 자손의 노드 개수
깊이(Depth)	트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(Depth)를 표현
레벨(Level)	트리의 특정 깊이를 가지는 노드의 집합
높이(Height)	루트 노드에서 가장 깊숙히 있는 노드의 길이
노드 차수(Node Degree)	노드가 지닌 가지의 수
트리 차수(Tree Degree)	트리의 최대 차수

⌨️ 구현하기

이진 탐색 트리 기준

class BinarySearchTree {
    //BST의 constructor를 구현
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
    
    // 트리에 value를 추가
    insert(value) {
      // 인자의 value가 this.value보다 작을 경우, 왼쪽 노드에서 진행
      if (value < this.value) {
        // this.left에 아무것도 없을 경우, 새로운 자식 노드를 추가
        if (this.left === null) {
          this.left = new BinarySearchTree(value);
        }
        // this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용
        else {
          this.left.insert(value);
        }
      }
      
      // 인자의 value가 this.value보다 클 경우, 오른쪽 노드에서 진행
      else if (value > this.value) {
        // this.right에 아무것도 없을 경우, 새로운 자식 노드를 추가
        if (this.right === null) {
          this.right = new BinarySearchTree(value);
        }
        // this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용
        else {
          this.right.insert(value);
        }
      }
    }
    
    
    // 트리의 value값을 탐색
    contains(value) {
      // 찾는 값이 노드의 value와 일치한다면, true를 반환
      if (value === this.value) {
        return true;
      }
      // 찾는 값이 노드의 value 보다 작다면, 왼쪽에서 contains의 재귀를 진행
      if (value < this.value) {
        return !!(this.left && this.left.contains(value));
      }
      // 찾는 값이 노드의 value 보다 크다면, 오른쪽에서 contains의 재귀를 진행
      if (value > this.value) {
        return !!(this.right && this.right.contains(value));
      }
    }
    
    
    // 전위 순회
    preorder(callback) {
      callback(this.value);
      if (this.left) {
        this.left.preorder(callback);
      }
      if (this.right) {
        this.right.preorder(callback);
      }
    }
    
    // 중위 순회
    inorder(callback) {
      if (this.left) {
        this.left.inorder(callback);
      }
      callback(this.value);
      if (this.right) {
        this.right.inorder(callback);
      }
    }
    
    // 후위 순회
    postorder(callback) {
      if (this.left) {
        this.left.postorder(callback);
      }
      if (this.right) {
        this.right.postorder(callback);
      }
      callback(this.value);
    }
  }

📍 참고

• 코딩테스트 합격자 되기 JS 편
• https://medium.com/quantum-ant/트리-tree-cec69cfddb14