Javascript 자료구조 05 : Tree

Tree, Binary Tree, Binary Search Tree(BST) 기초 + insert, search 기능을 구현

Tree(트리)

node(노드)와 branch(브랜치 | 가지)로 이루어진 나무 모양의 자료 구조. cycle(순환)이 없음.

용어 정리

• Node : 기본 저장 단위. data, branch 정보를 포함.
• Root Node : tree의 최상단 Node
• Level : branch의 깊이를 나타냄(일반적으로 Root - Node = Level0)
• Parent Node : 부모 Node
• Child Node : 자식 Node
• Leaf Node : Child Node가 없는 Node
• Depth : tree의 최대 Level

Binary Tree(이진 트리)

최대 branch가 2개인 node로 구성된 tree

Binary Search Tree(BST | 이진 탐색 트리)

"왼쪽 Child Node < Parent Node < 오른쪽 Child Node"

이진 트리의 조건에 더하여
왼쪽 node는 parent Node보다 항상 작은 값,
오른쪽 node는 parent Node보다 항상 큰 값을 저장함
*BST의 내부 구조는 Linked List의 성격을 띔

• 장점 : 데이터 검색/탐색에 유용함.
• 단점 : 복잡함.

• 시간 복잡도 : O($logn$)
• 한계 : 입력받은 값이 1, 2, 3, 4, 5 처럼 순서대로 쌓이면 Linked List와 같아진다.

Tree

// Node
function Node(data) {
  (this.data = data), (this.left = null), (this.right = null);
}
//
// Tree
function Tree() {
  this.root = null;
  this.insert = insert;
  this.search = search;
  this.remove = remove;
}

insert 구현

// insert(데이터 삽입)
function insert(data) {
  const node = new Node(data);
  let current = this.root;
  // root가 비어있을 경우 root에 node를 할당하고 return
  if (!current) {
    this.root = node;
    return node;
  }
  // root가 비어있지 않을 경우
  while (true) {
    // 새 data가 현재 비교할 node의 data보다 작을 경우
    if (data < current.data) {
      // current.left가 존재하면 current에 current.left를 할당하여 level을 높임.
      if (current.left) {
        current = current.left;
      } else {
        // current.left가 존재하지 않으면 current.left에 node를 할당하고 반복문 break;
        current.left = node;
        break;
      }
    } else {
      // 새 data가 현재 비교할 node의 data보다 크거나 같을 경우
      if (current.right) {
        current = current.right;
      } else {
        current.right = node;
        break;
      }
    }
  }
}

search 구현

// search 이진 탐색
function search(data) {
  let current = this.root;
  while (current) {
    if (current.data === data) {
      return true;
    } else {
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
  }
  return false;
}

테스트 코드

// tree 생성 및 데이터 저장
let tree = new Tree();
tree.insert(5);
tree.insert(8);
tree.insert(9);
tree.insert(3);
tree.insert(2);
console.log(tree);
//
root: Node
data: 5
  left: Node
  data: 3
    left: Node
    data: 2
      left: null
      right: null
    right: null
  right: Node
  data: 8
    left: null
    right: Node
    data: 9
      left: null
      right: null
//
// search
console.log(tree.search(6)); // false
console.log(tree.search(5)); // true

• 2020.04.11 최초 작성

댓글 환영 by.protect-me