Algorithm

Tree / Binary Tree / Heap (트리, 이진 트리, 힙)

5_ssssseung 2021. 4. 7. 13:23

트리

개념

  • 비선형 구조
  • 원소들 간에 1:n 관계를 가지는 자료구조
  • 원소들 간에 계층관계를 가지는 계층형 자료구조
  • 상위 원소에서 하위 원소로 내려가며 확장되는 트리(나무)모양의 구조

 

정의

  • 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족
    1. 노드 중 최상의 노드는 루트(root)
    2. 나머지 노드들은 n(>=0)개의 분리 집합 T1, ... , TN으로 분리 가능
  • 이들 T1, ... , TN은 각각 하나의 트리로 간주 가능하며(재귀적 정의) 루트의 부 트리(subtree)라고 함

 

용어 설명

  • 노드(node) - 트리의 원소
    • 트리 T의 노드 - A, B, C, D, E, F, G, H, I, J, K

 

  • 간선(edge) - 노드를 연결하는 선, 부모 노드와 자식 노드를 연결

 

  • 루트 노드(root node) - 트리의 시작 노드
    • 트리 T의 루트 노드 - A

 

  • 형제 노드(sibling node) - 같은 부모 노드의 자식 노드들
    • B, C, D는 형제 노드

 

  • 조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
    • K의 조상 노드 : F, B, A

 

  • 서브 트리(subtree) - 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

 

  • 자손 노드 - 서브 트리에 있는 하위 레벨의 노드들
    • B의 자손 노드 - E, F, K

 

  • 차수(degree)
    • 노드의 차수 : 노드에 연결된 자식 노드의 수
      • B의 차수 = 2, C의 차수 = 1
    • 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
      • 트리 T의 차수 = 3
    • 단말 노드(leaf node) : 차수가 0인 노드, 자식 노드가 없는 노드

 

  • 높이
    • 노드의 높이 : 루트에서 노드에 이르는 간선의 수, 노드의 레벨
      • B의 높이 = 1, F의 높이 = 2
    • 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨
      • 트리 T의 높이 = 3

 

이진 트리

개념

  • 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리
  • 각 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리
    • 왼쪽 자식 노드 (left child node)
    • 오른쪽 자식 노드 (right child node)
  • 이진 트리의 예

 

특성

  • 레벨 i에서의 노드의 최대 개수는 2^i 개
  • 높이가 h인 이진 트리가 가질 수 잇는 노드의 최소 개수는 h+1 개
  • 최대 개수는 2^(h+1) - 1 개

 

종류

  • 포화 이진 트리(Full Binary Tree)
    • 모든 레벨에 노드가 포화상태로 차 있는 이진 트
    • 높이가 h일 때, 최대의 노드 개수인 2^(h+1) - 1 의 노드를 가진 이진 트리
      • 높이 3일 때 2^4 -1 = 15개의 노드
    • 루트를 1번으로 하여 2^(h+1) - 1까지 정해진 위치에 대한 노드 번호를 가짐

 

 

  • 완전 이진 트리(Complete Binary Tree)
    • 높이가 h이고 노드 수가 n개일 때 (단, h+1 <= n < 2^(h+1) - 1 ), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리
    • 노드가 10개인 완전 이진 트리

 

  • 편향 이진 트리(Skewed Binary Tree)
    • 높이 h에 대해 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리
      • 왼쪽 편향 이진 트리
      • 오른쪽 편향 이진 트리

 

순회(traversal)

  • 트리의 각 노드를 중복되지 않게 전부 방문하는 것을 의미
  • 트리는 비 선형 구조이기 때문에 선형구조에서와 같이 선후 연결관계를 알 수 없음
  • 따라서 특별한 접근 방법이 필요

 

  • 순회 : 트리의 노드들을 체계적으로 방문하는 것
  • 3가지 기본적인 순회방법
    • 전위순회(preorder traversal) : VLR
    • 중위순회(inorder traversal) : LVR
    • 후위순회(postorder traversal) : LRV
     
  • V - 부모 노드, L - 왼쪽 자식 노드, R - 오른쪽 자식 노드

전위 순회

  • 수행 방법
    1. 현재 노드 n을 방문하여 처리 -> V
    2. 현재 노드 n의 왼쪽 서브트리로 이동 -> L
    3. 현재 노드 n의 오른쪽 서브트리로 이동 -> R
  • 전위순회 예

 

중위 순회

  • 수행 방법
    1. 현재 노드 n의 왼쪽 서브트리로 이동 -> L
    2. 현재 노드 n을 방문하여 처리 -> V
    3. 현재 노드 n의 오른쪽 서브트리로 이동 -> R
  • 중위순회 예

 

후위 순회

  • 수행 방법
    1. 현재 노드 n의 왼쪽 서브트리로 이동 -> L
    2. 현재 노드 n의 오른쪽 서브트리로 이동 -> R
    3. 현재 노드 n을 방문하여 처리 -> V
  • 후위순회 예

 

이진트리의 표현

배열

  • 배열을 이용하여 이진 트리 표현
    • 이진 트리에 각 노드 번호를 부여
    • 루트의 번호르 1로 지정
    • 레벨 n에 있는 노드에 대하여 왼쪽부터 오른쪽으로 2^n 부터 2^(n+1) - 1 까지 번호르 차례로 부여

 

    • 노드 번호를 배열의 인덱스로 사용
    • 노드 번호가 i 인 노드의 부모 노드 번호 : floor(i / 2) (i/2와 같거나 그보다 작은 정수 중 가장 큰 값)
    • 노드 번호가 i 인 노드의 왼쪽 자식 노드 번호 : 2*i
    • 노드 번호가 i 인 노드의 오른쪽 자식 노드 번호 : 2*i+1
    • 레벨 n의 노드 번호 시작 번호 : 2^n노드 번호의 성질
  •  
    • 높이가 h인 이진 트리를 위한 배열 크기
      • 레벨 i의 최대 노드 수 : 2^i
      • 따라서 1 + 2 + 4 + 8 + ... + 2^i = Σ2^i = 2^(h+1) - 1

 

 

 

  • 배열을 이용한 이진 트리 표현의 단점
    • 편향 이진 트리의 경우 메모리 공간 낭비 발생
    • 트리의 중간에 새로운 노드를 삽입, 기존 노드의 삭제할 경우 배열 크기 변경이 어려워 비효율적

 

연결 리스트

배열을 이용한 이진 트리 표현의 단점을 보완하기 위해 연결리스트를 이용해 트리 표현 가능

  • 연결 자료구조를 이용한 이진트리의 표현
    • 이진 트리의 모든 노드는 최대 2개의 자식 노드를 가지므로, 일정한 구조의 단순 연결 리스트 노드를 사용하여 구현

 

  • 완전 이진 트리의 연결 리스트 표현

 

수식트리

  • 수식을 표현하는 이진 트리
  • 수식 이진 트리(Expression Binary Tree)라고 부르기도 함
  • 연산자는 루트 노드이거나 가지 노드
  • 피연산자는 모두 잎 노드

 

수식트리의 순회

  • 중위 순회 : A / B * C * D + E (식의 중위 표기법)
  • 후위 순회 : A B / C * D * E + (식의 후위 표기법)
  • 전위 순회 : + * * / A B C D E (식의 전위 표기법)

 

이진탐색트리

  • 탐색작업을 효율적으로 하기 위한 자료 구조
  • 모든 원소는 서로 다른 유일한 키를 지님
  • key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)
  • 서브트리 또한 이진 탐색 트리로 구성
  • 중위 순회하면 오름차순으로 정렬가능

 

연산

탐색 연산

  • 루트에서 시작
  • 탐색할 키 값 x를 루트 노드의 키 값과 비교
    • x = 루트노드의 키 값인 경우 : 원하는 원소를 찾았으므로 탐색 연산 성공
    • x < 루트노드의 키 값인 경우 : 루트노드의 왼쪽 서브트리에 대해 탐색연산 수행
    • x > 루트노드의 키 값인 경우 : 루트노드의 오른쪽 서브트리에 대해 탐색연산 수행
  • 서브트리에 대해서 순환적으로 탐색 연산 반복

 

  • 예시) 13 탐색

 

삽입 연산

  • 탐색 연산을 수행
    • 삽입할 원소와 같은 원소가 있다면 삽입 불가능
    • 탐색에 실패할 경우 마지막까지 탐색한 위치가 삽입 위치
  • 탐색 실패한 위치에 원소를 삽입

 

  • 예시) 5 삽입

 

성능

  • 탐색, 삽입, 삭제 시간은 트리의 높이 만큼 시간 소요
    • O(h), h : BST의 깊이
  • 평균의 경우
    • 이진 트리가 균형적으로 생성되어 있는 경우
    • O(log n)
  • 최악의 경우
    • 한쪽으로 치우친 경사 이진트리 경우
    • O(n)
    • 순차탐색과 시간복잡도 동일

 

  • 검색 알고리즘 비교
    • 배열에서의 순차 검색 : O(N)
    • 정렬된 배열에서의 순차 검색 : O(N)
    • 정렬된 배열에서의 이진탐색 : O(logN)
      • 고정 배열 크기와 삽입, 삭제 시 추가 연산 필요
    • 이진 탐색트리에서의 평균 : O(logN)
      • 최악의 경우 : O(N)
      • 완전 이진 트리 또는 균형트리로 바꿀 수 있다면 최악의 경우 방지
        • 새로운 원소를 삽입할 때 소요 시간 단축
        • 평균과 최악의 시간이 동일 O(logN)

 

힙(heap)

  • 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 가장 작은 노드를 찾기 위해서 만든 자료구조

 

  • 최대 힙(max heap)
    • 키값이 가장 큰 노드를 찾기 위한 완전 이진 트리
    • 부모노드 키 값 > 자식노드 키 값
    • 루트 노드 : 키 값이 가장 큰 노드

 

  • 최소 힙(min heap)
    • 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
    • 부모노드 키 값 < 자식노드 키 값
    • 루트 노드 : 키 값이 가장 작은 노드

 

  • 힙의 예

 

힙의 연산

삽입

  1. 삽입할 자리 확장 (완전 이진 트리 규칙에 따라서 마지막 자리 확장)
  2. 확장한 자리에 삽입할 원소 저장
  3. 부모노드와 크기를 비교하여 자리바꾸기를 반복
  4. 바꿀 필요가 없다면 자리 확정

 

삭제

  1. 루트 원소 삭제
    • 힙에서는 루트 노드의 원소만 삭제 가능
  2. 마지막 노드를 루트 노드로 이동
  3. 자식 노드와 루트 노드의 크기 비교하여 자리바꾸기를 반복
  4. 바꿀 필요가 없다면 자리 확정

 

저작자표시

'Algorithm' 카테고리의 다른 글

비트 연산  (0) 2021.04.15
시간 복잡도 개념 및 설명  (0) 2021.04.13
BFS (Breadth First Search, 너비 우선 탐색)  (0) 2021.03.04
Circular Queue (원형 큐)  (0) 2021.03.03
Linear Queue (선형 큐)  (0) 2021.03.03

'Algorithm'의 다른글

  • 현재글Tree / Binary Tree / Heap (트리, 이진 트리, 힙)

관련글

댓글

티스토리툴바