코딩일기장

관련용어

• 루트 노드(Root Node) : 트리의 가장 위의 노드, 부모 노드가 없다. 
• 단말 노드(Leaf Node) : 자식이 없는 노드를 말한다.
  
• 간선(Edge) : 노드를 연결하는 선을 말한다.
  
• 부모 노드(Parent Node) : 임의의 노드 위에 연결된 하나의 노드를 말한다.
• 자식 노드(Child Node) : 임의의 노드의 하위에 연결된 모든 노드를 말한다.
• 형제(Sibling) : 같은 부모를 가지는 노드들을 말한다.
  
  
• 노드의 깊이(depth) : 루트 노드 부터 자기 자신 까지의 간선의 개수를 의미한다.
  
• 노드의 레벨(level) : 특정 깊이를 가지는 노드의 집합을 의미한다.
  
• 노드의 차수(degree) : 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수 또는 자식 노드의 수를 의미한다.
  
• 트리의 차수(degree of tree) : 가장 큰 노드의 차수를 의미한다.
  
• 트리의 높이(height) : 가장 밑에 있는 단말 노드의 깊이, 보통 가장 높은 레벨을 의미한다.
  

개념 및 특징

트리는 비선형 구조, 그 중에서도 계층적 구조의 대표적인 예인데요, 마치 나무가 가지를 뻗는 모양새라고 해서 트리라는 이름을 가졌습니다.

트리는 방향성이 있는 비순환 그래프의 한 종류인데 몇 가지 특징을 알아보겠습니다.

• 트리는 노드와 간선으로 구성 된 자료구조 입니다. 노드들 간에 간선으로 이어져 있습니다.
• 노드 간에 간선에는 방향이 자식 노드가 부모 노드를 가리킬 수 없기 때문에 사이클이 존재하지 않습니다.
  • self loop 또한 존재하지 않습니다.
  • 트리는 방향성이 있는 비순환 그래프입니다.
• 하나의 트리에는 오직 하나의 루트 노드만이 존재합니다.
• 노드마다 0개 이상의 자식 노드를 가집니다.
  • 0개면 단말 노드 입니다.
• 루트 노드를 제외하고 노드마다 부모 노드는 오직 하나입니다.
  • 어떤 노드에서 다른 모든 노드 까지의 경로는 오직 하나입니다.
• '간선의 개수' = '노드의 개수 - 1' 입니다.
• 트리의 종류에는 이진 트리, 이진 탐색 트리, AVL 트리, red - black 트리, 힙 등이 있습니다. 

이진트리

가장 기본적인 트리인 이진 트리에 대해서 알아보겠습니다.

이진트리는 자식 노드의 최대 개수가 2인 트리를 의미합니다. 따라서 노드 data와 두 개의 자식 노드에 대한 정보로 구성되어있습니다.

node{
	data elemnet;
   	node* child1;
   	node* child2;
}

※ 이진 트리의 분류

• 포화 이진트리
  • 트리의 각 레벨에 노드가 꽉 차있는 이진 트리를 의미합니다. => 트리의 높이가 N이면 노드의 개수는 2^N - 1
  • 말단 노드를 제외한 모든 노드는 2개의 자식 노드를 갖습니다.
  • 말단 노드들은 모두 형제(Sibling)입니다.

• 완전 이진트리
  • 마지막 레벨을 제외한 모든 레벨에서 노드가 꽉 차있는 이진 트리를 의미합니다.
  • 포화 이진트리와의 차이점은 마지막 레벨에서 노드가 꽉 차있지 않습니다. 
  • 왼쪽 부터 자식을 채워 나갑니다. 만약 왼쪽 자식은 없는 데 오른쪽이 있으면 완전 이진트리가 아닙니다.
  • 포화 이진트리는 완전 이진트리이지만 완전 이진트리는 포화 이진트리가 아닙니다.

※순회

• 전위순회(preorder) 
  1. 루트를 방문한다.
  2. 왼쪽 서브트리를 방문한다. 
  3. 오른쪽 서브트리를 방문한다.

preorder(node){
	if(node != NULL){
    	visit(node);
        preorder(node->left);
        preorder(node->right);
    }
}
	

• 중위순회(inorder)

  1. 왼쪽 서브트리를 방문한다.
  2. 루트를 방문한다.
  3. 오른쪽 서브트리를 방문한다.

inorder(node){
	if(node != NULL){
        inorder(node->left);
        visit(node);
        inorder(node->right);
    }
}
	

• 후위순회(postorder
  1. 왼쪽 서브트리를 방문한다.
  2. 오른쪽 서브트리를 방문한다.
  3. 루트를 방문한다.

postorder(node){
	if(node != NULL){
        postorder(node->left);
        postorder(node->right);
        visit(node);
    }
}
	

기타 트리(나중에 자세하게 다룰 예정)

• 이진 탐색트리
  • 모든 서브트리에서 '오른쪽 자식 노드 > 루트 > 왼쪽 자식 노드'의 속성을 가지는 트리를 의미합니다.
  • 한쪽으로 편중 될 수 있다는 단점을 가지고 있습니다. (불균형트리)
• AVL, red - black 트리
  • 균형트리, 이진 탐색트리의 단점을 보완할 수 있습니다.
• 힙
  • 최소 힙(Min heap), 최대 힙(Max heap)

트리 구현방법

• 배열
  1. 자식의 최대 개수를 알 때
     • 이차원 배열을 활용해 자식  노드의 index를 저장합니다. ex) 이진트리 array[n][0] => n 노드의 왼쪽 자식, array[n][1] => n 노드의 오른쪽 자식
  2. 자식의 최대 개수를 모를 때
     • 1차원 배열에 부모 노드의 index를 저장합니다.
• 인접 리스트
  • 각 정점마다 자식 노드를 연결하는 새로운 연결 리스트를 만들어 줍니다.

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!