Data Structure - Tree

 Tree 

나무를 거꾸로 옮겨 놓은 듯한 모양의 자료구조로써,

루트 노드와 자식 노드로 이루어져 계층적 구조를 표현하는 비선형 자료구조다.

비선형 자료구조 : 하나의 자료 뒤에 여러가지 자료가 붙을 수 있는 자료구조

 

트리의 가장 위 노드를 루트라고 하며 , 그 아래 노드를 자식 노드라고 한다. 각 노드는 여러 자식 노드를 가질 수 있으며, 이러한 자식 노드는 자체 자식 노드를 가질 수도 있어 재귀적 구조를 형성한다.

이미지 출처 https://www.geeksforgeeks.org/introduction-to-tree-data-structure/

 

 Tree의 사용 

• 계층적 데이터: 파일 시스템, 조직 모델 등
• 데이터베이스: 빠른 데이터 검색
• 라우팅 테이블: 네트워크 알고리즘의 데이터 라우팅
• 정렬/검색: 데이터 정렬, 검색
• 우선순위 큐: 우선순위 큐의 구조는 일반적으로 이진 힙과 같은 트리를 사용

 

 Tree의 종류 

1. 이진트리 BinaryTree : 각 노드가 최대 두 개의 자식을 가지고 있는 트리 아래의 복잡한 트리의 기본 구조
2. 이진 탐색 트리 BST (Binary Search Tree ) :
   각 노드에서 왼쪽 자식 노드는 root보다 작은 값을, 오른쪽 자식 노드는 root보다 큰 값을 가진 트리 구조
3. AVL 트리 (AVL Tree) : 왼쪽과 오른쪽 서브 트리의 높이 차가 최대 1이 되도록 균형을 이루는 이진 탐색트리
4. 레드-블랙 트리 (Red-Black Tree) : 삽입/삭제 시 균형을 자동으로 유지하는 트리 
5. 힙 (Heap) : 최대힙과 최소힙이 있으며 부모 노드가 자식 보다 크거나 작도록 구성하는 트리다.
6. 트라이 (Trie) : 문자열이나 키의 집합을 저장하는 트리 기반 자료 구조
   ex ) 문자열 탐색이 많은 자동완성 기능 구현에 유용하다
7. B-트리 (B-Tree) 및 B+트리 : 데이터베이스, 파일 시스템에서 사용되는 균형 트리로, 노드에 여러 값을 저장하며, 자식이 여러 개다.

 

 JavaScript로 Tree구현하기 

/** Binary Search Tree 문제 //////////////////////////
 * 첫 번째 입력 리스트(lst)로 이진 탐색 트리를 생성합니다.
 * 두 번째 입력 리스트(searchList)에 있는 값들이 해당 트리에 존재하는지 탐색해야 합니다.
 * 결과는 searchList의 각 값이 트리에 존재하면 true, 없으면 false를 배열로 반환합니다.
 */
 
class Node {
  constructor(value) {
    this.left = null;
    this.right = null;
    this.value = value;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new Node(value);

    if (!this.root) {
      this.root = newNode;
      return;
    }
    let currentRoot = this.root;
    while (true) {
      if (value < currentRoot.value) {
        if (currentRoot.left === null) {
          currentRoot.left = newNode;
          return;
        }
        currentRoot = currentRoot.left;
      } else {
        if (currentRoot.right === null) {
          currentRoot.right = newNode;
          return;
        }
        currentRoot = currentRoot.right;
      }
    }
  }

  search(value) {
    let currentRoot = this.root;
    while (currentRoot !== null) {
      if (value === currentRoot.value) return true;
      currentRoot =
        value < currentRoot.value ? currentRoot.left : currentRoot.right;
    }
    return false;
  }
}

function solution(lst, searchList) {
  const bst = new BinarySearchTree();
  for (const list of lst) {
    bst.insert(list);
  }
  console.log("최종 트리 구조xx:", bst);

  let result = [];
  for (const searchItem of searchList) {
    result.push(bst.search(searchItem));
  }

  return result;
}

const lst1 = [5, 3, 8, 4, 2, 1, 7, 10];
const searchList1 = [1, 2, 5, 6];
console.log(solution(lst1, searchList1)); // [true, true, true, false]

 

 

---

Reference 

https://en.wikipedia.org/wiki/Tree_(abstract_data_type)

https://www.geeksforgeeks.org/introduction-to-tree-data-structure/

https://www.w3schools.com/dsa/dsa_theory_trees.php - Data Structures and Algorithms

https://www.tutorialspoint.com/data_structures_algorithms/tree_traversal.htm