[자료구조/알고리즘][Codestates] Tree

자료구조 Tree에 대해서 알아아보고, 이를 어떤 방식으로 사용하는지 알아본다.

코드스테이트 Lesson 내용의 일부와 윤성우의 열혈 자료구조 책을 참고하였다.

1. Tree

Tree란

• 데이터를 순차적으로 나열시킨 선형구조가 아닌, 하나의 데이터 뒤에 여러 개의 데이터가 있는 비선형 구조이다.
• 단방향 그래프이며 계층적 구조를 갖고 사이클이 없다.

용어 정리

• 깊이 (depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현한다. root node는 깊이가 0이고 밑으로 갈수록 Level 1, Level 2로 커진다.
• 레벨 (Level) : 같은 깊이를 갖고있는 노드를 묶어서 레벨로 표현한다.
• 높이 (Height) 리프 노드를 기준으로 루트까지의 높이 (height) 트리의 최고 레벨을 가리킨다. 부모 노드는 자식 노드의 가자 높은 Height 값에 +1 한 값을 높이로 가진다.
  • 각 리프 노드의 높이는 0으로 놓는다 (3,6,19는 높이 0)
  • 5,15는 높이가 1이다 (0+1)
  • 10은 높이가 2이다
• 서브 트리 (Sub tree) 트리 구조를 갖춘 작은 서브 트리. 위에서 5,3,6 도 서브트리이다.

Tree의 실사용

가장 대표적인 Tree 구조는 컴퓨터의 디렉터리 구조이다. 루트 폴더 (/)에서 시작되어 branch를 뻗어나간다.

파일 시스템 등에서는 트리 구조를 이용해 만들어져 있다. 또한, Dom의 구조와 JSON을 예로 들 수 있다.

주로 데이터 검색(탐색)에 사용되며 탐색 속도를 개선시킬 수 있다는 장점이 있다.

2. Binary Search Tree

• 이진트리는 자식 노드가 최대 두 개인 노드들로 구성된 트리이다.
• 이진트리의 조건 자체가 재귀적이다.
• 이진 트리의 조건
  • 루트 노드를 중심으로 두 개의 서브 트리로 나뉜다.
  • 나누어진 두 서브 트리 모두 이진트리어야 한다
  • 노드가 존재하지 않다면 공집합 노드(empty set)가 존재하는 것으로 간주한다.
• 왼쪽 자식의 값이 루트나 부모보다 작고 , 모든 오른쪽 자식 값이 루트나 부모보다 큰 값을 가진다.

Binary Search Tree의 종류

이진트리는 자료의 삽입, 삭제 방법에 따라 정이진 트리, 완전 이진트리, 포화 이진트리로 나뉜다.

Binary Tree의 종류

종류	설명
정 이진트리 (Full binary tree)	- 각 노드가 0개 혹은 2개의 자식 노드를 갖는다
포화 이진트리(Perfect binary tree)	- 정 이진트리이면서 완전 이진트리인 경우이다. - 모든 leaf 노드의 레벨이 동일하다. - 모든 레벨이 가능 채워져있다.
완전 이진트리(Complete binary tree)	- 마지막 레벨을 제외한 모든 노드가 가득 차있어야한다. - 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져 잇어야 한다.

Binary Search Tree의 시간 복잡도 (Big-O)

• 데이터 삽입 : n개의 데이터가 있을 때, 한 번 탐색을 할 때마다 1/2씩 탐색 범위를 줄여준다. 아래와 같이 계산을 하면 O(logN)의 복잡도가 나온다. (log는 밑이 2이다)
  
  
• 최악의 경우 O(n)이 될 수 있다.
  

  

  Binary Search Tree ADT의 정의

• BinarySearchTree : Object로 정의된 이진트리 그 자체
• left :노드보다 더 작은 값을 갖는 자식 노드
• right: 노드보다 저 큰 값을 갖는 자식 노드
• Binary Search를 대표하는 연산
  • insertNode(value) : Node를 삽입
  • contains(value) : Node 탐색
  • delete(value) : Node 삭제

ADT를 기반으로 구현을 해보자.

Binary Search Tree의 구현

• Class를 이용한 BST 구현

// Binary Tree ADT
// Tree : 객체로 정의된 Tree 그 자체
// left : Node의 자식 중 왼쪽 node
// Right : Node의 자식 중 오른쪽 node

// Tree를 대표하는 연산
// insertNode(value) : Node에 데이터를 저장
// search(val) : 값을 찾는다.


/* Pesudocode ---------------------------------------*/
//------------ insert(value)-------------------------//
// insertNnode(val)
    // if -> this.val >val
    // if -> this.left true -> this.left.insertNode(vel)
    // else -> new Tree(val)
    // else if -> this.val<val
    // if -> this.right true-> this.right.insertNode(val)
    // else -> new.Tree(val)

//------------ search(val)-------------------------//
// if this.value===value -> return true
// if this.value>value -> return this.left.search(value)
// else return this.right.search(value)

class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  insertNode(value) {
    if (this.value > value) {
      this.left
        ? this.left.insertNode(value)
        : (this.left = new BinaryTree(value));
    } else if (this.value < value)
      this.right
        ? this.right.insertNode(value)
        : (this.right = new BinaryTree(value));

    return " 이미 존재하는 값";
  }

  contains(value) {

    if (this.value === value) return true;
    if (this.value > value) {
      if (this.left)
        return this.left.value === value ?? this.left.contains(value);
    } else {
      if (this.right)
        return this.right.value === value ?? this.right.contains(value);
    }
  }
}

// 삭제 구현은 아직 하지 않음