[자료구조] 트리, 이진탐색트리

Creating the dots·2022년 1월 21일
자료구조
0

자료구조

목록 보기
2/4
post-thumbnail

트리의 특징

  • 트리구조는 데이터를 선형이 아닌 계층으로 정렬한다.
    • Height는 해당 노드부터 리프노드까지의 거리를 의미한다.
    • Depth는 노드의 계층(level)을 의미한다.
      • 위 예시에서 A의 Height와 Depth는 각각 3, 0이고, I는 0, 3이다.
  • 트리는 뿌리에 해당하는 루트노드를 기준으로 구성된다.
  • 상위노드는 부모노드에 해당하며, 하위노드는 자식노드이다.
  • 자식노드는 하나의 부모노드만을 가지며, 여러개의 부모노드를 갖는 자료구조는 그래프이다.
  • 더이상 자식노드를 갖지 않는 노드는 말단노드 또는 리프노드라고 한다.
  • 노드 하나와 그 자식노드로 구성된 트리를 하위트리 또는 서브트리라고 한다.
  • 트리에서 노드를 연결하는 선을 에지(edge)라고 한다.
  • 노드에는 데이터를 저장하며, 이때 저장된 데이터를 식별하는데 사용되는 키와 값(데이터)을 포함할 수 있다.

트리 적용하기

다음과 같이 value와 descendants를 갖는 노드를 생성할 수 있고, descendants에 각 노드를 푸시해서 계층을 만들 수 있다.

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

//트리의 노드 생성하기
const A = new TreeNode('A');
const B = new TreeNode('B');
const C = new TreeNode('C');
const D = new TreeNode('D');

A.descendants.push(B,C,D);

const E = new TreeNode('E');
const F = new TreeNode('F');
B.descendants.push(E, F);

console.log(A);

A를 콘솔에 찍어보면, 다음과 같이 A.descendants에 각각 B,C,D를 value로 가지는 노드들이 저장되어있고, B.descendants에도 E,F를 value로 가지는 노드들이 저장되어있다.

이진트리

이진트리는 가장 많이 사용되는 데이터 구조라고 할 수 있으며, 각 부모노드는 최대 2개의 자식노드와 연결되어 있어서 붙여진 이름이다. 이진트리의 유형으로는 Full, Complete, Perfect 등이 있다.

  • full binary tree

    • 각 노드가 0개 또는 2개의 자식노드를 가진 경우 (1개의 자식노드를 가진 경우는 해당안됨)

  • complete binary tree

    • 리프노드를 제외하고 모든 레벨의 노드들이 0개 또는 2개의 자식노드를 가진 경우 (즉, 리프 노드를 제외하고 모든 레벨의 노드가 full binary tree인 경우)
    • 만약 위의 예시에서 회색 노드를 지우면, full, complete binary tree이지만, perfect는 아니다.

  • perfect binary tree

    • 리프노드 포함 모든 레벨의 노드이 full binary tree이고, 리프노드가 모두 같은 레벨인 경우
    • k는 트리의 Height이고, 1부터 시작할때, 약 (2^k)-1개의 노드를 갖는다.

이진 탐색 트리

이진 탐색 트리는 왼쪽 자식노드의 값이 항상 부모노드보다 작고, 오른쪽 자식노드의 값이 항상 부모노드보다 큰 이진트리이다.
(부모노드와 같은 값을 삽입할 경우, 오른쪽 자식노드의 추가하는 경우도 있는데, 이러한 중복값을 추가하는 케이스는 다음에 다루도록 하고, 이번에는 중복값은 허용하지 않는 경우로 살펴보도록 하자.)

이진트리 값 삽입하기

현재 노드를 기준으로 크기를 비교한다.

  • 현재 노드 === 삽입할 노드
    리턴한다

  • 현재 노드(A) > 삽입할 노드(X)
    왼쪽 자식노드(B)의 값이 Null이라면 B에 삽입한다.B에 값이 있다면, B를 기준으로 다시 크기를 비교한다.

  • 현재 노드(A) < 삽입할 노드(X)
    오른쪽 자식노드(C)의 값이 Null이라면 C에 삽입한다. C에 값이 있다면, C를 기준으로 다시 크기를 비교한다.

이진트리 값 삭제하기

값을 삭제하는 경우는 세가지가 있다.

  • 삭제할 노드가 리프 노드인 경우
    삭제할 노드를 Null로 바꿔준다.
  • 삭제할 노드가 하나의 자식노드를 가진 경우
    삭제할 노드를 자식노드와 위치를 바꿔준 후, 자식노드(원래 삭제할 노드였던 값)를 Null로 바꿔준다.
  • 삭제할 노드가 두 개의 자식노드를 가진 경우
    트리를 중위순회를 했을때 삭제할 노드 다음값(항상 리프노드)과 위치를 바꿔주고, 리프노드(원래 삭제할 노드였던 값)를 Null로 바꿔준다.

이진트리 순회방법

//다음과 같은 트리가 있을때, 트리를 순회하는 방법은 다음과 같다.
	 10
       /    \
      5      30
    /       /  \
   4       15   40
 /
3

전위순회 Preorder Traversal (DFS와 순서동일)

  • 부모 -> 왼쪽 서브트리 -> 오른쪽 서브트리
  • 서브트리 방문했을때에도, 왼쪽 노드부터 먼저 순회
  • 10, 5, 4, 3, 30, 15, 40

중위순회 Inorder Traversal

  • 왼쪽 서브트리 -> 부모 -> 오른쪽 서브트리
  • 3, 4, 5, 10, 15, 30, 40

후위순회 Postorder Traversal

  • 왼쪽 서브트리 -> 오른쪽 서브트리 -> 부모
  • 3, 4, 5, 15, 40, 30, 10

구현

class treeNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

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

  insert(data) {
    let node = new treeNode(data);

    // 루드가 설정되어 있지 않다면 루트를 node로 만들어 준다. node는 treeNode()에서 뼈대를 받아온다.
    if(!this.root) {
      this.root = node;
      return this;
    }

    // 비교를 위해 current 를 설정해 준다.
    let current = this.root;

    // current가 true 라면 while문을 돌면서 data와 지금 현재 data인 current data를 비교한다.
    while (current) {
      // 중복된 값은 어떤 결과를 리턴하지 않는다.
      if(data === current.data) {
        return;
      }
      // data가 기준 data(current data) 보다 작다면 왼쪽에 넣어준다.
      if(data < current.data) {
        if(!current.left) {
          current.left = node;
          break;
        }
      // 이제 current data(기준)는 왼쪽의 data로 잡힌다.
        current = current.left;
      }
      // data가 기준 data(current data) 보다 크다면 오른쪽에 넣어준다.
      if(data > current.data) {
        if(!current.right) {
          current.right = node;
          break;
        }
        // 이제 current data(기준)는 오른쪽 data로 잡힌다.
        current = current.right;
      }
    }
  }

  // BFS(너비 우선 탐색)
  bfs() {
    let node = this.root;
    let queue = [node];
    let finalData = [];

    while(queue.length) {
      node = queue.shift();
      if(node.left) {
        queue.push(node.left);
      }
      if(node.right) {
        queue.push(node.right);
      }
      finalData.push(node.data);
    }
    return finalData;
  }

  // DFS(깊이 우선 탐색)
  // Pre-Order traversal(전위 순회)
  preOrder() {
    const finalData = [];
    function traverse(node) {
      finalData.push(node.data);
      if(node.left) {
        traverse(node.left);
      }
      if(node.right) {
        traverse(node.right);
      }
    }
    traverse(this.root);
    return finalData;
  }
  
  // In-Order traversal(중위 순회)
  inOrder() {
    let finalData = [];
    function traverse(node) {
      if(node.left) {
        traverse(node.left);
        finalData.push(node.data);
      }
      if(node.right) {
        traverse(node.right);
      }
    }
    traverse(this.root)
     return finalData;
  }

  // Post-Order traversal(후위 순회)
  postOrder() {
    let finalData = [];
    function traverse(node) {
      if(node.left) {
        traverse(node.left);
      }
      if(node.right) {
        traverse(node.right);
        finalData.push(node);
      }
    }
    traverse(this.root)
    return finalData;
  }
}

🔍 루트노드의 height는 0일까? 1일까?

  • height를 엣지의 개수로 본다면 0
  • height를 노드의 개수로 본다면 1

    위의 예시에서 트리는 height를 엣지의 개수로 본다면 3이고, 노드의 개수로 본다면 4이다.

reference

profile
Creating the dots
어제보다 나은 오늘을 만드는 중
이전 포스트

[자료구조] 해시 테이블

다음 포스트

[자료구조] 그래프

0개의 댓글