트리(Tree)

2019. 5. 9. 21:00·🧬 Data Structure

 

트리Tree는 자료들이 리스트, 스택, 큐와 같은 1:1 관계의 선형 구조가 아니라 1:n 관계의 비선형 자료구조이다. 또한 계층 관계로 만들어진 계층형 자료구조Hierarchical Data Structure이다.


노드node - 트리의 원소

루트 노드root node - 트리의 시작 노드(레벨 0)

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

형제 노드sibling node - 같은 부모의 자식 노드들

조상 노드Ancestor node - 간선을 따라 루트 노드까지 경로에 있는 모든 노드들

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

자손 노드child or descendant node - 서브 트리에 있는 하위 레벨의 노드들


노드의 차수node degree - 노드에 연결된 자식 노드의 수

트리의 차수tree degree - 트리에 있는 노드의 차수 중에서 가장 큰 값


노드의 높이node height or depth - 루트에서 노드에 이르는 간선의 수(노드의 레벨)

트리의 높이tree height or depth - 트리에 있는 노드의 높이 중에서 가장 큰 값(최대 레벨)


포리스트forest - 서브 트리의 집합


이진 트리Binary Tree - 트리의 모든 노드의 차수를 2 이하고 제한하여 전체 트리의 차수가 2 이하가 되도록 정의

이진 트리의 특성

  • 노드가 n개인 이진 트리는 항상 간선이 (n-1)개이다.
  • 높이가 h인 이진 트리가 가질 수 있는 노드 개수는 최소 (h+1)개이며, 최대 (2h+1-1)개이다.

 

 

이진 트리의 종류


1. 포화 이진 트리Full Binary Tree

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

2. 완전 이진 트리Complete Binary Tree

  • 높이가 h이고 노드 수가 n개일 때, 노드 위치가 포화 이진 트리에서의 노드 1번부터 n번까지의 위치와 완전히 일치하는 이진 트리
  • 완전 이진 트리에서는 (n+1)번부터 (2h+1-1)번까지 노드는 모두 공백 노드

3. 편향 이진 트리Skewed Binary Tree

  • 높이가 h일 때, (h+1)개의 노드를 가지면서, 모든 노드가 왼쪽이나 오른쪽 중 한 방향으로만 서브 트리를 가지고 있는 트리

 

 

이진 트리의 순회traversal

  • 전위 순회preorder traversal - D → L → R 순서로, 현재 노드를 방문하여 처리하는 작업 D를 가장 먼저 수행
  • 중위 순회inorder traversal - L → D → R 순서로, 현재 노드를 방문하여 처리하는 작업 D를 작업 L과 작업 R의 중간에 수행
  • 후위 순회postorder traversal - L → R → D 순서로, 현재 노드를 방문하여 처리하는 작업 D를 가장 나중에 수행

이진 탐색 트리Binary Search Tree - 이진 트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정의한 것


AVL 트리Adelson-Velskii, Landis Tree

  • 대표적인 균형 이진 탐색 트리
  • 각 노드에서 왼쪽 서브 트리의 높이 hLheight of Left subtree과 오른쪽 서브 트리의 높이 hRheight of Right subtree의 차이가 1 이하인 트리

AVL 트리의 특징

  • 왼쪽 서브 트리 < 부모 노드 < 오른쪽 서브 트리의 크기 관계를 갖는다.
  • 각 노드의 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이의 차이(hL-hR)를 노드의 균형 인수BF, Balance Factor라 한다.
  • 각 노드의 균형 인수로 {-1, 0, +1} 값만 가지게 함으로써 왼쪽 서브 트리와 오른쪽 서브 트리의 균형을 항상 유지함.

AVL 트리의 회전 연산

  • AVL 트리에서 수행하는 삽입, 삭제 작업은 이진 탐색 트리에서의 삽입, 삭제 작업과 같고, 이후에 균형을 맞추어주는 재구성 작업이 추가되는데 이 작업은 회전Rotation 연산을 통해 이루어진다.
  • LL 회전 연산 - 삽입, 삭제 연산 후에 AVL 트리에 LL 유형의 불균형이 발생했을 때 적용
  • RR 회전 연산 - 삽입, 삭제 연산 후에 AVL 트리에 LL 유형의 불균형이 발생했을 때 적용
  • LR 회전 연산 - 삽입, 삭제 연산 후에 AVL 트리에 LR 유형의 불균형이 발생했을 때 적용
  • RL 회전 연산 - 삽입, 삭제 연산 후에 AVL 트리에 RL 유형의 불균형이 발생했을 때 적용

 


 

'🧬 Data Structure' 카테고리의 다른 글

그래프(Graph)  (0) 2019.05.18
'🧬 Data Structure' 카테고리의 다른 글
  • 그래프(Graph)
Baeg-won
Baeg-won
  • Baeg-won
    좋았다면 추억이고 나빴다면 경험이다.
    Baeg-won
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 🍃 Spring, Spring Boot
        • 스프링 프레임워크 기초
        • 스프링 핵심 원리 - 기본편
        • 자바 ORM 표준 JPA 프로그래밍 - 기본편
        • 스프링 MVC
        • 실전! 스프링 부트와 JPA 활용1 - 웹 애플리..
      • 🥑 Web Technoloy
      • 🚗 Backend Toy Project
        • 스프링 부트 게시판
        • Photogram
        • Baeg-won Clothing Gallery
      • 🥇 Problem Solving
        • Breadth-First Search
        • Depth-First Search
        • Backtracking
        • Simulation
        • Two-pointer
        • Binary Search
        • Greedy
        • Dynamic Programming
        • Minimum Spanning Tree
        • Dijkstra
        • Floyd warshall
      • ☕ Java
        • 명품 자바 에센셜
        • Applications
      • 🍦 JavaScript
        • JavaScript 기초
      • 🐧 Linux
        • 이것이 리눅스다(CentOS 8)
      • 📟 Database
        • 혼자 공부하는 SQL
      • 🧬 Data Structure
      • 🎬 HTML
      • 🎤 Tech Interview
      • 📌 etc
        • Unity 2D Raising Jelly Game
        • C++
        • 영어 쉐도잉
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
Baeg-won
트리(Tree)
상단으로

티스토리툴바