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

트리의 특징

트리구조는 데이터를 선형이 아닌 계층으로 정렬한다.
- 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

Tree Data Structure in Javascript for Beginners

Binary Tree | Set 3 (Types of Binary Tree)

Height of a tree with only one node

Calculating the Height of a Binary Tree

이진트리와 전위순회, 중위순회, 후위순회

Understand everything about Binary Search Tree

Author And Source

이 문제에 관하여([자료구조] 트리, 이진탐색트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kaitlin_k/자료구조-트리-이진탐색트리

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)