[JS] 트리(Tree), 이진 트리, 이진 탐색 트리

Wol-dan·2021년 9월 11일
자료구조
1

알고리즘&자료구조

목록 보기
1/7

트리(Tree)

다음과 같은 특징을 갖는 자료구조를 트리라고 한다.

  • 루트 노드(가장 상위 노드)가 있다.
  • 노드간 부모와 자식 관계가 성립한다.
  • 트리엔 '레벨'('깊이')이 있다.

이진 트리(Binary Tree)

모든 노드의 차수(해당 노드가 가진 자식 수/서브 트리 수)가 2 이하인 트리

  • 이진 트리의 레벨이 i라고 할 때, 해당 레벨 i에서 가질 수 있는 최대 노드 수는 2^(i-1) (i >= 1)이다.
  • 깊이가 k인 이진 트리가 가질 수 있는 최대 노드 수는 2^(k) - 1 (k >= 1)이다.
  • 이진 트리의 노드는 데이터, 왼쪽 자식으로의 포인터, 오른쪽 자식으로의 포인터를 갖는다.

이진 트리의 종류

  • 완전 이진 트리(Complete Binary Tree): 다음과 같은 성질을 갖는 이진 트리이다.

    • 트리의 마지막 레벨을 제외하고는 노드가 꽉 차있어야 한다.
    • 트리의 마지막 레벨에는 노드가 왼쪽부터 순서대로 차 있어야 한다.

  • Full Binary Tree: 자식 노드를 한 개만 갖는 노드가 하나도 없는 트리. 자식을 가지려면 하나도 갖지 말거나 2개를 가져야한다는 것.

  • Perfect Binary Tree: 최대로 가질 수 있는 노드로 꽉꽉 차있는 이진 트리. 트리의 레벨을 n이라 가정했을 때, 2^n - 1개의 노드를 갖는 트리를 의미한다.

이진 트리의 순회

이진 트리 순회 알고리즘은 트리에 저장된 모든 노드를 빠짐없이 살펴보고 싶을 때 사용한다. 깊이 우선 순회 방법으로는 전위 순회, 중위 순회, 후위 순회 가 있고, 너비 우선 순회 방법으로는 레벨 순회 가 있다.

image

  • 전위 순회(pre-order): NLR
  • 중위 순회(in-order): LNR
  • 후위 순회(post-order): LRN
  • 레벨 순회(level-order): NLR

image

  • 전위 순회(pre-order): 1 2 4 5 3 6 7
  • 중위 순회(in-order): 4 2 5 1 6 3 7
  • 후위 순회(post-order): 4 5 2 6 7 3 1
  • 레벨 순회(level-order): 1 2 3 4 5 6 7

이진 트리 순회 구현하기

재귀적(Recursive) 방법

  • 트리 정의
class Tree {
  constructor(val) {
    this.val = val;
    this.leftNode = null;
    this.rightNode = null;
  }

  setVal(val) {
    this.val = val;
  }

  setLeft(node) {
    this.leftNode = node;
  }

  setRight(node) {
    this.rightNode = node;
  }
}
  • 전위 순회(pre-order)
// 초기 인자로는 root 노드가 들어올 것이다.
var recursivePreOrder = function (node) {
  if (!node) {
    return;
  }
  console.log(node.val);
  this.recursivePreOrder(node.leftNode);
  this.recursivePreOrder(node.rightNode);
};
  • 중위 순회(in-order)
var recursivePreOrder = function (node) {
  if (!node) {
    return;
  }
  this.recursivePreOrder(node.leftNode);
  console.log(node.val);
  this.recursivePreOrder(node.rightNode);
};
  • 후위 순회(post-order)
var recursivePreOrder = function (node) {
  if (!node) {
    return;
  }
  this.recursivePreOrder(node.leftNode);
  this.recursivePreOrder(node.rightNode);
  console.log(node.val);
};

반복적 방법

재귀적인 방법 말고 반복과 스택을 이용하여 트리를 순회할 수도 있다.

  • 전위 순회(pre-order)
var iterativePreOrder = function (node) {
  if (node == null) {
    return;
  }
  let stack = [];
  stack.push(node);
  while (stack.length > 0) {
    let pop_node = stack.pop();
    console.log(pop_node.val);
    if (pop_node.right) stack.push(pop_node.right);
    if (pop_node.left) stack.push(pop_node.left);
  }
};
  • 중위 순회(in-order)
var iterativeInOrder = function (node) {
  if (node == null) {
    return;
  }
  let crnt_node = node;
  let stack = [];
  while (true) {
    if (crnt_node != null) {
      stack.push(crnt_node);
      crnt_node = crnt_node.left;
    } else if (stack.length > 0) {
      crnt_node = stack.pop();
      console.log(crnt_node.val);
      crnt_node = crnt_node.right;
    } else {
      break;
    }
  }
};
  • 후위 순회(post-order)
var iterativePostOrder = function (node) {
  if (node == null) {
    return;
  }
  let crnt_node = node;
  let stack = [];
  let last_visit_node = null;
  while (true) {
    if (crnt_node != null) {
      stack.push(crnt_node);
      crnt_node = crnt_node.left;
    } else if (stack.length > 0) {
      peek_node = stack[stack.length - 1];
      if (peek_node.right != null && last_visit_node != peek_node.right) {
        crnt_node = peek_node.right;
      } else {
        console.log(peek_node.val);
        last_visit_node = stack.pop();
      }
    } else {
      break;
    }
  }
};
  • 레벨 순회

레벨 순회는 큐(Queue)를 사용하면 간단하게 구현할 수 있다.

var levelOrderTraversal = function (node) {
  if (node == null) {
    return;
  }
  let queue = [];
  queue.push(node);
  while (queue.length > 0) {
    let pop_node = queue.shift();
    console.log(pop_node.val);
    if (pop_node.left) queue.push(pop_node.left);
    if (pop_node.right) queue.push(pop_node.right);
  }
};

levelOrderTraversal(root);

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리는 다음과 같은 제약 조건이 추가된 이진 트리를 의미한다.

  • 왼쪽 자식 노드(왼쪽 서브트리)는 부모 노드보다 키값이 작고, 오른쪽 자식 노드(오른쪽 서브트리)는 부모 노드보다 키값이 큰 이진 트리

  • 왼쪽, 오른쪽 서브트리는 모두 이진 탐색 트리를 이루어야한다.(위 제약조건을 만족해야함)

  • 이진 탐색 트리 구현 방법

    • 배열
    • link로 잇는 연결리스트

  • 이진 탐색 트리의 장점

    • 정렬된 배열에서의 삽입, 삭제는 느리다.(O(n)이다. 예를 들어 배열안의 값을 삭제할 경우 그 값보다 큰 값들을 한 셀 왼쪽으로 시프트해야한다.)
    • 해시 테이블에서 검색, 삽입, 삭제는 O(1)로 빠르지만, 해시 테이블은 순서를 유지하지 못한다.
    • 이진 탐색 트리는 순서를 유지하면서도 빠른 검색, 삽입, 삭제가 가능하다.

  • 이진 탐색 트리의 단점

    • 트리의 깊이가 깊어지면 탐색이 오래 걸린다.

이진 탐색 트리 검색

  • 1️⃣ 루트 노드부터 시작해 노드의 값을 확인한다.

  • 2️⃣ 찾고 있는 값과 같다면 값을 찾았다!

  • 3️⃣ 찾고 있는 값이 현재 노드보다 작다면 왼쪽 하위 트리를 검색한다.

  • 4️⃣ 찾고 있는 값이 현재 노드보다 크다면 오른쪽 하위 트리를 검색한다.

  • 이진 탐색 트리 검색의 시간 복잡도: O(log N) (포화 이진 트리라고 가정했을 때)

    • 각 단계를 수행할 때마다 값이 들어있을 남은 공간 중 반씩 제거해나가기 때문이다. (왼쪽 or 오른쪽 서브트리로 후보가 반씩 좁혀짐)
    • 정렬된 배열을 이진 검색(이분 탐색)할 때와 같은 시간 복잡도를 가진다. 하지만 이진 트리는 삽입 연산에서 정렬된 배열보다 효율성이 높다.

이진 트리 검색은 재귀적으로 구현할 수 있는데 코드로 살펴보자.

const Node = function (data) {
  this.key = data ? data : null;
  this.left = null;
  this.right = null;
};

const BST = function () {
  this.root = null;
};

// 이진 탐색 트리: 검색(탐색)
BST.prototype.search = function (root, key) {
  // 루트가 비어있거나, 루트 노드와 찾으려던 키값이 같은 경우
  if (!root || root.key === key) return root;

  // 현재 루트 키값 < 찾으려는 키값 인 경우 -> 오른쪽 서브트리 탐색 (재귀호출)
  if (root.key < key) {
    return this.search(root.right, key);
  }

  // 현재 루트 키값 > 찾으려는 키값 인 경우 -> 왼쪽 서브트리 탐색 (재귀호출)
  return this.search(root.left, key);
};

이진 탐색 트리 삽입

새로운 값을 삽입하려면 리프 노드(단말 노드)에 삽입해야한다. 즉 트리의 루트 노드부터 탐색해가며 노드를 삽입할 적절한 리프 노드를 찾고 노드를 삽입하는 과정이 이루어져야한다.

  • 1️⃣ 루트 노드부터 시작한다.

  • 2️⃣ 삽입할 노드의 키값과 루트 노드 값을 비교한 뒤 루트 노드보다 작다면 왼쪽 서브트리로, 크다면 오른쪽 서브트리로 탐색한다.(탐색에는 재귀 호출을 사용)

  • 3️⃣ 삽입할 적절한 말단에 다다르면 노드를 삽입한다.

  • 이진 탐색 트리 삽입의 시간 복잡도

    • 트리의 높이를 h라고 할 때, 최악의 경우 시간 복잡도는 O(h)라고 할 수 있다.
    • 최악의 경우, 한쪽으로 치우쳐진 트리라면 시간 복잡도는 O(n)으로 나타낼 수도 있다. (정렬된 데이터를 트리에 삽입할 때 한쪽으로 치우쳐진 트리가 보통 만들어진다. 따라서 정렬된 배열을 이진 탐색 트리로 변환하고 싶은 경우 데이터 순서를 무작위로 만든 후 트리를 생성하는 것이 좋다.)
    • 포화 이진 트리(균형 잡힌 트리)라고 가정했을 때는 이진 탐색 트리를 검색한 뒤 삽입 단계를 거치기 때문에 log N + 1, 즉 O(log n)의 시간 복잡도를 갖는다.
BST.prototype.insert = function (key) {
  // insertRec(재귀적으로 호출할 함수)의 결과를 BST의 루트에 저장
  this.root = this.insertRec(this.root, key);
};

// key값을 BST에 추가하기 위한 함수.
BST.prototype.insertRec = function (root, key) {
  // 트리가 비었거나 추가할 리프노드에 도착한 경우 key값으로 노드를 만들어 리턴
  if (root === null) {
    root = new Node(key);
    return root;
  }

  // 삽입하려는 key값이 현재 노드보다 작다면 왼쪽 서브트리로 재귀호출
  if (root.key > key) {
    root.left = this.insertRec(root.left, key);
  }

  // 삽입하려는 key값이 현재 노드보다 크다면 오른쪽 서브트리로 재귀호출
  else if (root.key < key) {
    root.right = this.insertRec(root.right, key);
  }

  // 최종적으로는 삽입하려는 key값이 추가된 트리를 리턴하게됨
  return root;
};

이진 탐색 트리 삭제

이진 탐색 트리에서 어떤 노드를 삭제할 때, 세 가지 경우가 있을 수 있다.

    1. 삭제할 노드가 리프 노드(단말 노드)에 있는 경우: 단순하게 그 노드를 그냥 트리에서 삭제하면 된다.
    1. 삭제할 노드가 한 개의 자식노드를 가진 경우: 삭제할 노드 자리에 한 개의 자식노드를 복사하고(이로써 삭제됨) 자식노드를 없애면 된다.
    1. 삭제할 노드가 두 개의 자식노드를 가진 경우: 다음 두 가지 중 선택하여 구현한다.
    • 3-1) 왼쪽 자식 중 가장 큰 값을 찾아 삭제할 노드 자리로 올린다.(값을 복사한다는 것이다.)
    • 3-2) 오른쪽 자식 중 가장 작은 값을 찾아 삭제할 노드 자리로 올린다.(값을 복사한다는 것이다.)
    • => 이렇게 삭제할 노드 자리에 값을 복사하고 나면 올린 노드는 삭제해준다.

  • 이진 탐색 트리 삭제의 시간 복잡도

    • 최악의 경우(한쪽으로 치우쳐진 트리) O(n)(리프 노드까지 가서 삭제하는 경우를 생각하면)
    • 균형 잡힌 트리의 경우 O(log n) (삭제할 노드를 검색 + 삭제된 노드 자리에 올라온 노드를 처리하는 단계)
BST.prototype.delete = function (key) {
  this.root = this.deleteRec(this.root, key);
};

BST.prototype.deleteRec = function (root, key) {
  // 만약 트리가 비었다면
  if (!root) return root;

  if (root.key > key) {
    root.left = this.deleteRec(root.left, key);
  } else if (root.key < key) {
    root.right = this.deleteRec(root.right, key);
  }

  // root.key와 key 값이 같다면, 삭제할 노드를 찾은 것이다.
  else {
    // 삭제할 노드의 자식이 한 개이거나 하나도 없는 경우(하나도 없는 경우는 left나 right 자식을 리턴해도 null이 리턴될 것이다.)
    if (root.left === null) return root.right;
    else if (root.right === null) return root.left;

    // 삭제할 노드의 자식이 두 개인 경우, 오른쪽 서브트리에서 가장 작은 값을 찾는다. 그리고 그 값을 root의 키값에 저장한다.(이러면 삭제할 노드의 키값은 지워지게 된다.)
    root.key = this.minValue(root.right);

    // 오른쪽 서브트리에서 가장 작은 값이 올라왔으니 해당 노드를 삭제해주어야한다. 오른쪽 서브트리와 위에서 구했던 가장 작은 값을 넘겨주면서 해당 노드를 삭제해준다.
    root.right = this.deleteRec(root.right, root.key);
  }

  // 삭제할 노드가 삭제된 트리를 최종적으로 리턴한다.
  return root;
};

BST.prototype.minValue = function (root) {
  // 계속 왼쪽 서브트리로 내려가며 가장 작은 값을 찾는다.
  let minv = root.key;
  while (root.left != null) {
    minv = root.left.key;
    root = root.left;
  }
  return minv;
};

이진 탐색 트리의 특징

이전에 배운 해시 테이블은 검색, 삽입, 삭제에 O(1)이 걸린다. 이진 탐색 트리(BST)는 균형 잡힌 트리일 경우 검색, 삽입, 삭제에 O(log n)이 걸린다. 그런데도 이진 탐색 트리가 해시 테이블보다 이점을 더 갖는 이유는 무엇일까?

  • 이진 탐색 트리(BST)를 중위 순회하기만 해도 항상 정렬된 키값들을 얻을 수 있다. 반면 해시 테이블에서 정렬된 결과를 얻으려면 추가적인 작업이 필요하다.
  • 일반적으로 해시를 구현하기 위해서는 프로그래밍 언어가 제공하는 라이브러리에 의존해야하는데 이진 탐색 트리는 이런 해시에 비해 구현하고 커스텀하기 쉽다.
  • 해시는 테이블을 resize 해야하는 경우 시간 복잡도에 추가적인 비용이 발생할 수 있다.

이진 탐색 트리 전체 코드

const Node = function (data) {
  this.key = data ? data : null;
  this.left = null;
  this.right = null;
};

const BST = function () {
  this.root = null;
};

BST.prototype.search = function (root, key) {
  if (!root || root.key === key) return root;

  if (root.key < key) {
    return this.search(root.right, key);
  }

  return this.search(root.left, key);
};

BST.prototype.insert = function (key) {
  this.root = this.insertRec(this.root, key);
};

BST.prototype.insertRec = function (root, key) {
  if (root === null) {
    root = new Node(key);
    return root;
  }

  if (root.key > key) {
    root.left = this.insertRec(root.left, key);
  } else if (root.key < key) {
    root.right = this.insertRec(root.right, key);
  }

  return root;
};

BST.prototype.delete = function (key) {
  this.root = this.deleteRec(this.root, key);
};

BST.prototype.deleteRec = function (root, key) {
  if (!root) return root;

  if (root.key > key) {
    root.left = this.deleteRec(root.left, key);
  } else if (root.key < key) {
    root.right = this.deleteRec(root.right, key);
  } else {
    if (root.left === null) return root.right;
    else if (root.right === null) return root.left;

    root.key = this.minValue(root.right);

    root.right = this.deleteRec(root.right, root.key);
  }

  return root;
};

BST.prototype.minValue = function (root) {
  let minv = root.key;
  while (root.left != null) {
    minv = root.left.key;
    root = root.left;
  }
  return minv;
};

BST.prototype.inorder = function () {
  this.inorderRec(this.root);
};

BST.prototype.inorderRec = function (root) {
  if (root != null) {
    this.inorderRec(root.left);
    console.log(root.key);
    this.inorderRec(root.right);
  }
};

const bst = new BST();
console.log(bst.insert(5)); // 5 삽입
console.log(bst.insert(1)); // 1 삽입
console.log(bst.insert(7)); // 7 삽입
console.log(bst.search(bst.root, 7)); // 7 탐색
console.log(bst.root);
console.log(bst.insert(2)); // 2 삽입
console.log(bst.insert(6)); // 6 삽입
console.log(bst.insert(8)); // 8 삽입
console.log(bst.root);
console.log(bst.delete(7)); // 7 삭제
console.log(bst.root);
bst.inorder(); // 1 2 5 6 8 출력

Ref

profile
Wol-dan
정리하고 모으고 커뮤니케이션하는 걸 좋아하는 새싹 웹 개발자🌱
다음 포스트

[JS] 히프(Heap), 최대 히프와 최소 히프, 우선순위 큐

0개의 댓글