Complete Binary Tree(이진트리)

in csStudy

[2023.04.22 ~ 2023.04.27] 동안 공부한 DFS 내용이다.
해당 포스트는 누구나 자료구조와 알고리즘 개정 2판을 참고하여 작성되었다.

데이터를 특정 순서로 정렬할때, 정렬 알고리즘은 아무리 빨라도 O(NlogN) 의 시간이 걸린다. 데이터를 자주 정렬해야하면 데이터를 항상 정렬된 순서로 유지하는 편이 낫다. 하지만 정렬된 배열은 삽입과 삭제가 상대적으로 느리다. 값을 넣을 때는 빈 공간을 만들기 위해 셀을 시프트하고, 값을 삭제할 때는 빈 공간을 없애기 위해 셀을 시프트해야하기 때문이다. 평균적으로 삽입과 삭제에 O(N)이 걸린다. 해쉬테이블은 검색,삽입,삭제가 O(1) 이지만 순서를 유지하지 못하므로 적절하지 않다. 순서를 유지하면서 빠른 검색, 삽입, 삭제가 가능한 이진트리를 사용하자. ✍

트리

트리는 **노드 기반 자료구조**이지만, 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다.

[연결리스트] 는 각 노드마다 그 노드와 다른 한 노드를 연결하는 링크를 포함

  1. 루트 : 가장 최상위 노드
  2. 각 노드(부모)에 연결된 노드(자식) -> 크게 보면 조상과 자식관계
  3. 레벨 : 트리에서 같은 줄
  4. 프로퍼티 : 균형 잡힌 정도

200x200

이진 탐색 트리

이진(binary) + 탐색(search)

이진트리는 각 노드에 자식이 0개,1개,2개이다. 이진 탐색 트리

  1. 각 노드의 자식은 최대 왼쪽 하나, 최대 오른쪽 하나
  2. 한 노드의 왼쪽 자식은 그 노드보다 작은 값만, 한 노드의 오른쪽 자식은 그 노드보다 큰 값만 포함

이진 탐색 트리 검색

이진 탐색 트리를 검색하는 알고리즘이다.

  1. 노드를 “현재 노드”로 지정한다. (알고리즘을 시작할 때는 루트가 첫번째 노드)
  2. 현재 노드 값을 확인한다.
  3. 현재 노드 값 === 찾고 있는 값, return;
  4. 현재 노드 값 > 찾고 있는 값, 왼쪽 하위 트리 검색
  5. 현재 노드 값 < 찾고 있는 값, 오른쪽 하위 트리 검색
  6. 찾을 때까지, 트리 바닥에 닿을때까지 반복(1단계 ~ 5단계)

각 단계마다 검색할 대상을 반으로 줄여버리는 O(logN)이다. 단, 완전 균형적인 이진 탐색 트리에서만 그렇다…

이진 트리와 재귀와의 관계

검색할 대상을 찾는 로직은 **반복** 되며 임의의 깊이만 큼(하향식) 들어가야 하므로 재귀와 적합하다.

200x200

전위순회 (preorder traverse)

전위순회는 루트 노드를 탐색한다.

즉, 📌 부모 -> 왼쪽 -> 오른쪽 순으로 이동한다.

function solution(v) {
  let answer = [];
  function DFS(n) {
    if (n > 7) {
      return;
    } else {
      answer.push(n);
      DFS(2 * n);
      DFS(2 * n + 1);
    }
  }
  DFS(1);
  return answer;
}
solution(7);

중위순회 (inorder traverse)

왼쪽 하위 트리 탐색 후, 루트 노드, 오른쪽 하위트리로 이동한다.

즉, 📌 왼쪽 -> 부모 -> 오른쪽 순으로 이동한다.

function solution(v) {
  let answer = [];
  function DFS(n) {
    if (n > 7) {
      return;
    } else {
      DFS(2 * n);
      answer.push(n);
      DFS(2 * n + 1);
    }
  }
  DFS(1);
  return answer;
}
solution(7);

후위순회 (level order traverse)

왼쪽 하위 트리 탐색 후, 오른쪽 하위 트리 탐색 후 루트 노드로 이동한다. 즉, 📌 왼쪽 -> 오른쪽 -> 부모 순으로 이동한다.

function solution(v) {
  let answer = [];
  function DFS(n) {
    if (n > 7) {
      return;
    } else {
      DFS(2 * n);
      DFS(2 * n + 1);
      answer.push(n);
    }
  }
  DFS(1);
  return answer;
}
solution(7);