CS/자료구조

[CS | 자료구조 | 트리]

study_min 2024. 1. 5. 00:52
🌲

1. 트리의 정의

  • 1개 이상의 노드로 이루어진 유한 집합
  • 계층적 구조를 가짐(비선형 구조)
  • 순회(전위/중위/후위/레벨)
    • 전위순회 : 부모 - 왼쪽 자식 - 오른쪽 자식

      문제 풀 때 [전위순회-중위순회]조합이면 전위순회는 앞에서부터!

    • 중위순회 : 왼쪽 자식 - 부모 - 오른쪽 자식

      문제 풀 때 [전/후위순회-중위순회]조합이면 중위순회는 전/후위순회 순서대로 부모가 된다!

    • 후위순회 : 왼쪽 자식 - 오른쪽 자식 - 부모

      문제 풀 때 [후위순회-중위순회]조합이면 후위순회는 뒤에서부터!

    • 레벨순회 : 레벨 순으로 순회

      큐를 사용, 순차적으로 순회(위-아래, 왼-오 순)

  • 사이클(Cycle)이 존재하지 않는 연결그래프(cf) 그래프⊃트리)
  • 트리 관련 용어
    • 노드 : 단위 정보 항목(cf)1번 노드는 근(root)임)
      • 근=루트노드(root) : 1번 노드, 제일 상위 노드
      • 단말노드=리프노드(terminal) : 제일 마지막에 위치한(제일 하위 레벨) 노드
      • 제노드=형제노드(siblings) : 같은 부모노드를 갖는 노드들
    • 가지(branch) : 노드와 노드 관계
    • 레벨=깊이 : 근에서 가지로 연결될 때마다 1씩 증가하는 것
    • 높이 : 종단 노드부터 어떤 노드까지의 레벨 수(레벨이랑 반대로 올라가는 것)
    • 크기 : 자신을 포함한 모든 자손 노드의 개수
    • 차수 : 자노드(≒부트리=서브트리)의 수(cf) 트리의 차수 = 트리 내 모든 차수 중 최대값)
    • 숲 : 트리에서 근을 제거하는 것(트리의 수=근의 차수)

2. 트리의 유형

  • 이진트리(binary tree) : 차수가 2를 넘지 않는 트리(O(logN))
    • 포화이진트리 : 트리의 각 레벨에 노드가 꽉 차있는 이진트리
    • 완전이진트리 : 순차적으로 채워져있는 트리(완전⊃포화)
      • [우선순위큐 - 최소/최대힙] 으로 구현 : 데이터 중 큰/작은 값을 O(1)로 추출 가능
      • 순차적으로 채우기때문(왼쪽부터 찬다)에 빈 공간이 없어서 배열로 표현하기 좋음
      • 부모가 자식보다 크거나 같다
      • (root가 1일 때) 부모 : i//2, 형제 : i-1, i+1 (i=자식 번호)

      왼쪽자식 : 2i, 오른쪽 자식 : 2i+1 (i=부모 번호)

    • 이진탐색트리(탐색=크기 순) : 부모를 기준으로 왼쪽 노드가 부모보다 작고, 오른쪽 노드가 부모보다 크다!

      ⇒ 같은 값 여러개를 동시에 삽입할 수는 없다!!(부모와 자식의 크기가 달라야 함!)

      탐색을 하기 위해서는 같은 값을 넣으면 비교가 되지 않기에 다른 값으로 구성되어야 한다.

    • 편향 이진트리(사향 이진트리) : 한쪽 방향으로만 자노드가 있는 트리
    • 트리 VS 이진트리
      트리이진트리
      서브트리(부트리) - 공백공백 불가공백 가능
      서브트리(부트리) - 순서순서 구별 X순서 구별O(왼쪽, 오른쪽)
      트리의 차수1개 이상(차수 고정X)차수가 2를 넘지 않음
  • 순서 유무에 따라 나뉘는 트리
    • 순서트리 : 노드들의 위치에 의미를 갖는(순서대로) 트리

      cf) 이진트리는 순서트리이다.

    • 오리엔티드 트리 : 순서 상관X 트리(레벨은 의미O)

3. 필수 공식

💡
n : 전체 노드의 수 | e(=B) : 간선 | h : 트리 높이 | Nx : 차수가 x인 노드 N의 수 |
T : 카탈린 수(=만들어질 수 있는 트리의 수)
① e=n−1−(이진트리).② N0=N2+1−③ T= 1/(n+1)∗ 2nCn             = 2n!/((n+1) ∗ n!)−④ log(n+1)≤h≤n−(완전이진트리).④ 2h−1−1<n≤2h−1                (로그를 취하면)=>h−1<log(n+1)≤h         =>h=[log(n+1)]      =>O(log(n))−⑤ n=2h−1① \ e = n -1 \\ - \\ (이진트리)\\ . \\ ② \ N_0 = N_2 + 1\\ - \\ ③ \ T = \ 1/(n+1) * \ _{2n}C_n \\ \ \ \ \ \ \ \ \ \ \ \ \ \ = \ {2n}!/((n+1) \ * \ n!)\\ - \\ ④ \ log(n+1) ≤ h ≤ n \\ - \\ (완전이진트리)\\.\\④ \ 2^{h-1}-1 < n ≤ 2^h-1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ (로그를 \ 취하면) => h-1 < log(n+1) ≤ h \\ \ \ \ \ \ \ \ \ \ => h = [log(n+1)] \\ \ \ \ \ \ \ =>O(log(n)) \\ - \\ ⑤ \ n = 2^h-1

4. 관련 문제


Uploaded by N2T