[자료구조] Tree

윤석진·2022년 1월 2일
0
post-thumbnail

🌲 Tree

계층적인 구조를 나타내는 자료구조

Tree의 구성

  • 노드(node)
    트리를 구성하고 있는 각각의 요소
  • 루트(root)
    트리에서 최상위에 있는 노드
  • 서브트리(subtree)
    하나의 노드와 그 노드들의 자손들로 이루어진 트리
  • 단말 노드(terminal node)
    하위 노드가 없는 노드
  • 비단말 노드(internal node)
    적어도 하나의 하위 노드를 가지는 노드

Tree의 용어

  • 레벨(level)
    트리의 각 층의 번호
  • 높이(height)
    트리의 최대 레벨
  • 차수(degree)
    노드가 가지고 있는 하위 노드의 개수

Tree의 응용 분야

  • 계층적인 조직 표현
  • 파일 시스템
  • 인공지능에서의 결정 트리

Binary Tree

모든 노드가 2개의 서브 트리를 가지고 있는 트리

  • 서브 트리는 공집합일 수 있다.
  • 이진 트리의 노드에는 최대 2개까지의 하위 노드가 존재한다.
  • 모든 노드의 차수가 2 이하가 된다.
    = 구현하기가 편리하다.
  • 이진 트리에는 서브 트리 간의 순서가 존재한다.

Binary Tree의 성질

  • 노드의 개수가 n개이면 간선의 개수는 n-1
  • 높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며 최대 2h-1개의 노드를 가진다.
  • n개의 노드를 가지는 이진 트리의 높이는 최대 n이거나 최소 log2(n+1)

Binary Tree의 분류

  • Full Binary Tree(포화 이진 트리)
    트리의 각 레벨에 노드가 꽉 차있는 이진 트리
  • Complete Binary Tree(완전 이진 트리)
    높이가 h일 때 레벨 1부터 h까지는 노드가 모두 채워져 있고 마지막 레벨 h에서는 왼쪽부터 오른쪽으로 순서대로 채워져 있는 이진 트리

Binary Tree의 표현

  • 배열표현법
0123456789
ABCDEF

모든 이진 트리를 포화 이진 트리라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법

  • 링크표현법
          ↙ A ↘
    ↙ B ↘        ↙ C ↘
↙ D ↘ ↙ E ↘ ↙ F ↘

포인터를 이용하여 상위 노드가 하위 노드를 가리키게 하는 방법

Binary Tree의 순회

  • preorder traversal(전위 순회)
    루트 → 왼쪽 하위 → 오른쪽 하위
  • inorder traversal(중위 순회)
    왼쪽 하위 → 루트 → 오른쪽 하위
  • postorder traversal(후위 순회)
    왼쪽 하위 → 오른쪽 하위 → 루트
  • level-order traversal(레벨 순회)
    루트부터 계층 별로 방문

수식 트리

산술식을 트리 형태로 표현한 것

  • 비단말 노드(internal node) = 연산자(operator)
  • 단말 노드(terminal node) = 피연산자(operand)

수식 트리 계산

후위 순회를 사용한다.

  • 서브 트리의 값을 재귀 호출로 계산한다.
  • 비단말노드를 방문할 때 양쪽 서브 트리의 값을 저장된 연산자를 이용하여 계산한다.

Thread Binary Tree

NULL 링크에 중위 순회 시에 후속 노드인 중위 후속자(inorder successor)를 저장시켜 놓은 트리

  • 이진 트리의 NULL 링크를 이용하여 순환 호출 없이도 트리의 노드들을 순회한다.
  • 단말 노드와 비단말노드의 구분을 위해 isThread 필드가 필요하다.

Binary Search Tree

탐색 작업을 효율적으로 하기 위한 자료 구조

  • 이진 탐색 트리에 저장된 키는 유일하다.
  • 왼쪽 서브 트리의 키 <= 루트 노드의 키 <= 오른쪽 서브 트리의 키
  • 왼쪽/오른쪽 서브 트리도 이진 탐색 트리이다.
  • 이진 탐색 트리를 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

Binary Search Tree의 연산

탐색

  • 비교한 결과가 같으면 탐색이 성공적으로 끝난다.
  • 비교한 결과가 주어진 키 값이 루트 노드의 키 값보다 작으면 탐색은 이 루트 노드의 왼쪽 하위를 기준으로 다시 시작한다.
  • 비교한 결과가 주어진 키 값이 루트 노드의 키 값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다.

삽입

  • 이진 탐색 트리에 원소를 삽입하기 위해서는 먼저 탐색을 수행하는 것이 필요하다.
  • 탐색에 실패한 위치가 새로운 노드를 삽입하는 위치가 된다.

삭제

  1. 삭제하려는 노드가 단말 노드일 경우
    해당 노드만 삭제하면 된다.
  2. 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우
    해당 노드를 삭제하고 서브 트리는 상위 노드에 붙여준다.
  3. 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우
    해당 노드와 가장 비슷한 값을 가진 노드를 해당 노드 위치로 가져온다.

    왼쪽 서브 트리에서 가장 큰 값과 오른쪽 서브 트리에서 가장 작은 값에서 가장 비슷한 값을 찾을 수 있다.

Binary Search Tree의 성능

이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이 h에 비례한다.

최선

  • 이진 트리가 균형적으로 생성되어 있는 경우
  • O(log2 n)

최악

  • 한쪽으로 치우친 경사 이진 트리의 경우
  • O(n)
profile
공부하며 쓰는 블로그

0개의 댓글