[자료구조] Tree -1

트리의 응용

• 조직이나 기관의 계층 구조
  
• 컴퓨터 운영체제의 파일 시스템
  
• 자바 클래스 계층구조 등
  
• 트리는 일반적인 트리와 이진트리로 구분
  
• 다양한 탐색트리(Search Tree), 힙(Heap) 자료구조, 컴파일러의 수식을 위한 구문트리(Syntax Tree) 등의 기본이 되는 자료구조로서 광범위하게 응용
  
  

트리

• 일반적인 트리는 실제 트리를 거꾸로 세워 놓은 형태의 자료구조
  
• html와 xml의 문서트리, 자바 클래스 계층구조, 운영체제의 파일시스템, 탐색트리, 이항힙, 피보나치힙과 같은 우선순위 큐에서 사용
  
• 일반적인 트리 정의 : empty이거나, empry가 아니면 루트노드 R과 트리의 집합으로 구성.
  
• 단, 트리의 집합은 공집합일 수도 있다
  
  

1. 용어
   • 루트(Root) 노드 : 트리의 최상위에 있는 노드
     
   • 자식(Child) 노드 : 노드 하위에 연결된 노드
     
   • 차수(Degree) : 자식노드 수
     
   • 부모(Parent) 노드 : 노드의 상위에 연결된 노드
     
   • 이파리(Leaf) 노드 : 자식이 없는 노드,
     
   • 형제(Sibling) 노드 : 동일한 부모를 가지는 노드
     
   • 조상(Ancestor) 노드 : 루트노드까지의 경로상에 있는 모든 노드 집합
     
   • 후손(Descendant) 노드 : 노드 아래로 매달린 모든 노드들의 집합
     
   • 서브트리(Subtree) : 노드 자신과 후손 노드로 구성된 트리
     
   • 레벨(Level), 깊이(Depth) : 루트노드는 레벨1, 아래 층으로 내려가며 레벨이 1씩 증가
     
   • 높이(Height) : 트리의 최대 레벨
     
   • 키(Key) : 탐색에 사용되는 노드에 저장된 정보
     
   • 단말(Terminal)노드, 외부(External) 노드 : 이파리노드
     
   • 내부(Internal) 노드, 비단말(Non-Terminal) 노드 : 이파리가 아닌 노드
     
     

• 일반적인 트리를 메모리에 저장하려면 각 노드에 키와 자식 수만큼의 레퍼런스 저장 필요
  
  • ex) 노드의 최대 차수가 k개라면, k개의 레퍼런스 필드를 아래와 같이 선언
    
• N개의 노드가 있는 최대 차수가 k인 트리
  
  • null 레퍼런스 수 = Nk - (N-1) = N(k-1) +1
    
  • Nk = 총 레퍼런스의 수
    
  • (N-1) = 트리에서 부모-자식을 연결하는 레퍼런스 수
    
• k가 클수록 메모리의 낭비가 심해지는 것은 물론, 트리를 탐색하는 과정에서 null 레퍼런스를 확인해야 하므로 시간적으로 매우 비효율
  
  

1. 왼쪽자식-오른쪼형제 표현
   
   • 노드의 왼쪽 자식과 괸쪽 자식의 오른쪽 형제노드를 가리키는 2개의 레퍼런스만을 사용
   • 예제 (a)의 트리를 왼쪽자식-오른쪽형제 표현으로 변환하면, (b)의 트리를 얻으며, (c)는 (b)의 트리를 45도 회전시킨 것
     
     

이진트리

• 각 노드의 자식 수가 2 이하인 트리
  
• 컴퓨터 분야에서 널리 활용되는 기본적인 자료구조
  
• 이진트리가 데이터의 구조적인 관계를 잘 반영하고, 효율적인 삽입과 탐색을 가능하게 하며, 이진트리의 서브트리를 다른 이진트리의 서브트리와 교환하는 것이 쉽기 때문
  
• 이진트리에 대한 용어는 일반적인 트리에 대한 용어와 동일
  
• 이진트리는 empty이거나, 루트노드와 2개의 이진트리인 왼쪽 서브트리-오른쪽 서브트리로 구성된다
  
  

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/2zr_7DBjR5A