자료구조 TIL - 4. Tree

 Tree의 개념

• 선형적인 관계의 데이터가 아닌 계층적인 관계를 가진 데이터를 저장하고 다루기 위한 자료구조의 하나
  • ex) 회사의 인사조직 데이터, OS의 파일 시스템 구조 등등
• 데이터가 부모 - 자식 관계의 계층적 구조로 표현이 된다.
• 대표적인 형태
  • 이진 트리  -  부모 노드가 가진 자식 노드가 2개를 넘지 않는 형태의 트리
  • 일반 트리  -  이진 트리와 다르게 자식 노드의 갯수에 제한이 없는 형태의 트리

 

Tree에서 사용하는 용어

Tree의 개념도

• 노드(Node)  -  트리 구조를 이루는 기본적인 요소
  • 루트 노드(Root Node)  -  트리의 시작점이 되는 노드
  • 부모 노드(Parent Node)  -  자식 노드들과 연결되고, Level이 1 작은 노드를 해당 자식 노드의 부모 노드라고 말함.
  • 자식 노드(Children Node)  -  부모 노드와 연결되고, Level이 1 큰 노드를 해당 부모 노드의 자식 노드라고 말함.
  • 단말 노드(Leaf Node)  -  자식 노드가 없는 노드를 말함, 반대의 경우는 비단말 노드(Nonterminal Node)라고 함
  • 부모 관계  -  부모 -- 자식 노드로 이루어진 관계를 말한다.
  • 형제 관계  -  같은 부모 노드를 가진 자식 노드들 간의 관계를 말한다.
• 간선(Edge)  -  트리 구성을 위해서 노드와 노드를 연결하는 요소
• 레벨(Level)  -  루트 노드를 기준으로 한 깊이 값
  • 루트 노드의 레벨을 1로 잡는 경우도 있고, 0으로 잡는 경우가 있는 것 같다.
  • 트리의 높이란 트리가 가지고 있는 가장 큰 레벨을 뜻한다.
• 차수(Degree)  -  노드가 가진 자식 노드의 수

 

Tree의 탐색

Tree의 세가지 순회 방법

• 순회란 트리의 각 노드를 방문하는 방법을 말한다.
• 노드를 방문하는 순서에 따라서 중위, 후위, 전위 순회로 나뉜다.
  • 중위 순회의 경우 깊이 우선 순회라고도 한다.
  • 중위 순회의 경우 대칭 순회라고도 한다.

 

Binary Tree

• Binary Tree(이진 트리)는 최대 차수가 2인 트리를 말한다.
• 이진 트리의 하나의 노드에 Right 또는 Left가 존재한다고 표현.
• 이진 트리의 종류
  • 완전 이진 트리(Complete Binary Tree)
    • 왼쪽부터 채워지며 마지막 레벨을 제외하면 모든 자식노드가 채워진 트리를 말한다.
  • 포화 이진 트리(Perfect Binary Tree)
    • 모든 노드가 0 또는 2개의 자식 노드를 가지고 모든 단말 노드가 같은 레벨에 있는 트리를 말한다
  • 편향 이진 트리
    • 모든 노드들이 한 쪽 방향으로 편중된 트리

 

Binary Search Tree

• 이진 트리의 한 종류

Binary Search Tree

• 하나의 규칙에 따라서 노드들의 값이 정렬된 트리이다.
  • 규칙은 "Left가 부모 노드보다 작고, Right가 부모 노드보다 크다."