[자료구조] 트리(Tree) 총 정리

Dragony·2019년 12월 17일
1

자료구조

목록 보기
2/10
post-custom-banner

1. 트리란?

트리는 노드로 이루어진 자료구조.
1. 트리는 하나의 루트 노드를 갖는다
2. 루트 노드는 0개 이상의 자식 노드를 갖고있다.
3. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

노드(node)들과 노드들을 연결하는 간선(edgd)들로 구성되어있다.

  • 트리에는 싸이클(cycle)이 존재할 수 없다.
  • 노드들은 특정 순서로 나열 될 수도 있고 그럴 수 없을 수도 있다
  • 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다.
  • 각 노드는 어떤 자료형으로도 표현 가능하다.
struct Node{
	char name[];
    struct Node* children;
}

트리는 그래프의 한 종류이다.

  • 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)
  • 또는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류 이다.
    * loop나 circuit이 없다. 당연히 self-loop도 없다
    • 즉, 사이클이 없다.
  • 노드가 N인 트리는 항상 N-1개의 간선을 가진다.
    * 즉, 간선은 항상 (Vertex의 개수 -1) 만큼을 가진다.
  • 루트에서 어떤 노드로 가는 경로는 유일하다.
    * 임의의 두 노드간의 경로도 유일하다. 즉, 두개의 정점 사이에는 반드시 1개의 경로만을 가진다.
  • 한개의 루트 노드만이 존재하며, 모든 자식 노드는 한개의 부모 노드만을 가진다.
    * 부모- 자식 관계이므로 흐름은 top-bottom 아니면 bottom-top 으로 이루어진다.
  • 순회는 전위, 후위, 중위로 이루어지고 이 3가지 모드 DFS/BFS 안에 있다.
  • 트리는 이진트리, 이진 탐색트리, 균형트리(AVL트리, red-black 트리), 이진 힙(최대 힙, 최소 힙)등이 있다.

비선형 구조 이다. 비선형 구조는 선형구조와는 다르게 데이터가 계층적(혹은 망)으로 구성되어 있다. 즉 트리는 계층 모델이다. ex) 디렉터리 구조, 조직도

2.트리(Tree)와 관련된 용어

tree-terms.png

  • 루트 노트(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
  • 단말 노드(leaf node): 자식이 없는 노드(차수가 0인 노드), '말단 노드' 또는 '잎 노드'라고도 부른다.
  • 내부(internal) 노드 : 단말노드가 아닌 노드.
  • 간선(edge): 노드를 연결하는 선(link, branch 라고도 부름)
  • 형제(sibling): 같은 부모를 가지는 노드
  • 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
  • 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
  • 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
  • 노드의 차수(degree): 노드의 서브트리 수
  • 트리의 차수(degree of tree): 트리의 최대 차수
  • 트리의 높이(깊이)(height): 루트 노드에서 가장 깊숙이 있는 노드의 깊이, max{노드레벨}

3. 트리(Tree)의 종류

이진트리(binary tree)

이진트리란?
비어있거나, 루트와 왼쪽 서브트리, 오른쪽 서브트리라고 불리는 두개의 서로소의 이진트리로 구성되어 있는 노드들의 유한 집합.
각 노드가 최대 2개의 child를 갖는다. 모든 트리가 이진트리는 아니다.

  • 이진트리와 일반 트리의 차이점
    * 트리에서는 어느 노드의 child를 순서로 구분한다.
    • 이진트리에서는 child가 한개인 경우도 left child 인가 right child 인가에 따라 다른 이진트리로 간주된다.
레벨 i에서의 최대 노드 수 : 2^(i-1) (i>=1)
깊이가 k인 이진트리가 가질 수 있는 최대 노드 수 : 2^k-1 (k>=1)
리프노드수 = 차수가 2인 노드 수 + 1

포화 이진트리(full binary tree)

Perfect-Binary-Tree.png

  • 깊이가 k이고, 노드 수가 2^k-1(k>=0) 인 이진트리
  • 노드 번호 1,...,2^k-1까지 순차적인 부여 가능
  • 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드의 개수가 최대가 되어야 한다.
  • 모든 내부 노드가 두개의 자식 노드를 갖는다.
  • 모든 말단 노드가 동일한 깊이 또는 레벨을 갖는다.

완전 이진 트리(complete binary tree)

Complete-Binary-Tree.png

  • 깊이가 k이고 노드 수가 n인 이진 트리
  • 각 노드들이 깊이가 k인 포화이진 트리 에서 1부터 n까지 번호를 붙인 노드와 1대 1로 일치
  • 트리의 모든 높이에서 노드가 꽉 차 있는 이진트리. 즉, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있어야 한다.
  • 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽 으로 채워져야 한다.
  • 배열을 사용해 효율적으로 표현 가능

이진 탐색 트리(Binary Search Tree, BST)

  • 모든 노드가 아래와 같은 특정 순서를 따르는 속성이 있는 이진 트리
    * 모든 왼쪽 자식들 <= N < 모든 오른쪽 자식들 (모든 노드 N에 대해서 반드시 true)
  • 왼쪽, 오른쪽 서브트리도 BST
  • 사전(dictionary) : pair<키, 원소>의 집합
    * 모든 원소는 서로 상이한 키를 갖는다.

균형 트리, 비균형 트리

  • 균형 트리
    * O(log N) 시간에 insert와 find를 할 수 있을 정도로 균형이 잘 잡혀 있는 경우
    • 레드-블랙 트리, AVL 트리

이진 힙(최소힙과 최대힙)

  • 최소 힙 (Min Heap)
    트리의 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워져 있는 완전 이진트리 이며, 각 노드의 원소가 자식들의 원소보다 작다.
     즉, key(부모 노드) <= key(자식 노드)인 완전 이진 트리
    가장 큰 값은 루트 노드이다.
     N개가 힙에 들어가 있으면 높이는 log(N_ 이다.

  • 최대 힙(Max Heap)
    * 원소가 내림차순으로 정렬되어 있다는 점에서만 최소힙과 다르다.

    • 각 노드의 원소가 자식들의 원소보다 크다

  • 트라이(Trei) (접두사 트리(prefix tree) 라고도 부른다)
    * n-차 트리의 변종

    • 각 노드에 문자를 저장하는 자료구조
    • 따라서 트리를 아래쪽으로 순회하면 단어 하나가 나온다.
    • 접두사를 빠르게 찾아보기 위한 흔한 방식으로, 모든 언어를 트라이에 저장해 놓는 방식이 있다.
    • 유효한 단어 집합을 이용하는 많은 문제들은 트라이를 통해 최적화할 수 있다.

4.트리(tree)의 구현 방법

기본적으로 트리는 그래프의 한 종류이므로 그래프의 구현방법(인접 리스트 또는 인접 배열)로 구현할 수 있다.

인접 행렬 이용 (adjacency matrix)

다운로드.png

다운로드 (1).png

인접 배열 이용

  1. 1차원 배열에 자신의 부모 노드만 저장하는 방법
<보조정리>
-n개의 노드를 가진 완전 이진 트리
1. parent(i) : i/2 (if i!=1)
2. leftChild(i) : 2i (if 2i<=n)
				  왼쪽 자식 없음 (if 2i > n)
3. rightChild(i) : 2i+1 (if 2i+1<=n)
				   오른쪽 자식 없음 (if 2i+1 > n)
  • 트리는 부모 노드를 0개 또는 1개를 가지기 때문
  • 부모 노드를 0개 : 루트 노드
  1. 이진 트리의 경우, 2차원 배열에 자식 노드를 저장하는 방법.
  • 이진트리는 각 노드가 최대 2개의 자식을 갖는 트리이기 때문.
    * ex) A[i][0]:왼쪽 자식 노드, A[i][1]: 오른쪽 자식 노드

인접 리스트 이용

5. 트리(Tree) 의 순회

트리 순회(tree traversal)
-트리에 있는 모든 노드를 한 번씩만 방문
1. 중위 순회(Inorder Traversal)

  • 왼쪽 자식 방문->루트 방문->오른쪽 자식 방문 (LVR)
template <class T>
void Tree<T>::Inorder(TreeNode<T> *currentNode){
	if(currentNode){
    	Inorder(currentNode->leftChild);
        Visit(currentNode);
        Inorder(currentNode->rightChild);
       }
   }

(non-recursive version)

void Tree<T>::NonrecInorder(){
	Stack<TreeNode<T>*> s;
    TreeNode<T> * currentNode = root;
    while(1){
    	while(currentNode){ //Move down leftChild fields
        	s.Push(currentNode);
            currentNode = currentNode->leftChild;
           }
        if(s.IsEmpty()) return;
        currentNode = s.Top; s.Pop();
        Visit(currentNode);
        currentNode = currentNode->rightChild;
        }
    }
  1. 전위 순회(Preorder Traversal)
  • 루트 방문 -> 왼쪽 자식 방문 -> 오른쪽 자식 방문 (VLR)
template<class T>
void Tree<T>::Preorder(TreeNode<T> *currentNode){
	if(currentNode){
    	visit(currentNode);
        Preorder(currentNode->leftChild);
        Preoreder(currentNode->rightChild);
     }
 }
  1. 후위 순회(Postorder Traversal)
  • 왼쪽 자식 방문 -> 오른쪽 자식 방문 -> 루트 방문(LRV)
template<class T>
void Tree<T>::Postorder(TreeNode<T> *currentNode){
	if(currentNode){
   	    Postorder(currentNode->leftChild);
        Postoreder(currentNode->rightChild);
    	visit(currentNode);
     }
 }

그래프와 트리의 차이

다운로드 (1).png

profile
Dragony
안녕하세요 :) 제 개인 공부 정리 블로그입니다. 틀린 내용 수정, 피드백 환영합니다.
이전 포스트

우선순위 큐(Prioirity Queue) (1) - 최대 힙 이용

다음 포스트

[자료구조] 힙(heap) - 최대힙(max heap)의 삽입과 삭제

post-custom-banner

0개의 댓글