[AL] 2. 자료구조 (Tree)

2. 자료구조 (Tree)

1. 트리 (Tree)
2. 탐색 (Search)
3. 이진 탐색 트리 (BST)
4. 균형 트리 (AVL 트리, Red-black 트리)

 

1. 트리 (Tree)

1.1. 트리의 특징

노드로 이루어진 자료구조이다. OS File System, DOM(Document Object Model) 등이 트리 구조를 가지고 있다.

• DAG(Directed Acyclic Graphs, 방향이 있는 비순환 그래프) 의 한 종류이다
• N개의 노드를 가진 트리는 항상 N-1개의 간선을 가진다
• 루트에서 어떤 노드로 가는 경로는 유일하다

 

1.2. 트리 용어

• 루트 노드 (root node) : 부모가 없는 노드 (트리는 하나의 루트 노드만을 가짐)
• 단말 노드 (leaf node) : 자식이 없는 노드
• 내부 노드 (internal node) : 단말 노드가 아닌 노드
• 간선 (edge) : 노드를 연결하는 선 (link)
• 형제 (sibling) : 같은 부모를 가지는 노드
• 크기 (size) : 자신을 포함한 모든 자손 노드의 개수
• 깊이 (depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 레벨 (level) : 트리의 특정 깊이를 가지는 노드의 집합
• 차수 (degree) : 하위 간선의 수

 

1.3. 이진 트리

모든 노드가 최대 2개의 자식 노드를 가질 수 있는 트리를 말한다.

• 포화 이진 트리(Full Binary Tree) : leaf 노드를 제외한 모든 노드가 2개의 자식을 갖는 트리
• 완전 이진 트리(Complete Binary Tree) : leaf 노드가 왼쪽부터 차곡차곡 채워진 형태의 트리
• 높이 균형 트리(Height Balanced Tree) : 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1 이상 차이 나지 않는 트리
• 완전 높이 균형 트리(Completely Height Balanced Tree) : 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 트리

 

1.4. 순회 방법

• 전위 순회 (Preorder Traversal)

  root → left → right 순으로 순회를 하는 방법

• 중위 순회 (Inorder Traversal)

  left → root → right 순으로 순회를 하는 방법

• 후위 순회 (Postorder Traversal)

  left → right → root 순으로 순회를 하는 방법

• 소스코드 (C++)

  #include <iostream>
  #define SIZE 15
  using namespace std;
  
  typedef struct node *nodePointer;
  typedef struct node {
      int data;
      nodePointer left,right;
  } node;
  
  node nodes[SIZE+1];
  
  // 전위 순회
  void preorder(nodePointer pointer){
      if(pointer){
          cout << pointer->data << ' ';
          preorder(pointer->left);
          preorder(pointer->right);
      }
  }
  
  // 중위 순회
  void inorder(nodePointer pointer){
      if(pointer){
          inorder(pointer->left);
          cout << pointer->data << ' ';
          inorder(pointer->right);
      }
  }
  
  // 후위 순회
  void postorder(nodePointer pointer){
      if(pointer){
          postorder(pointer->left);
          postorder(pointer->right);
          cout << pointer->data << ' ';
      }
  }
  
  int main(int argc, const char * argv[]) {
      // cin,cout 속도향상
      ios_base::sync_with_stdio(false);
      cin.tie(NULL); cout.tie(NULL);
      
      // 초기화
      for(int i=1; i<=SIZE; i++){
          nodes[i].data = i;
          nodes[i].left = NULL;
          nodes[i].right = NULL;
      }
      
      // left right 설정
      for(int i=2; i<=SIZE; i++){
          if(i % 2 == 0){
              nodes[i/2].left = &nodes[i];
          }else{
              nodes[i/2].right = &nodes[i];
          }
      }
      
      preorder(&nodes[1]);
      cout << "\n";
      inorder(&nodes[1]);
      cout << "\n";
      postorder(&nodes[1]);
      cout << "\n";
      
      return 0;
  }
  

 

 

2. 탐색 (Search)

2.1. 순차 탐색 (Sequential Search)

배열에 순서 없이 저장되어 있는 리스트를 탐색하는 기법이다. 리스트에 있는 첫번째 원소부터 마지막 원소까지 차례로 탐색 값을 비교한다. 또한 새로운 레코드가 들어온다면 배열의 마지막에 삽입된다.

• 비교 횟수 : 성공적이지 않은 탐색 = N+1회 , 성공적인 탐색 = 평균 N/2회 (만약 정렬된 경우라면 성공적인 경우와 그렇지 않은 경우 모두 평균 N/2회 의 비교횟수를 가짐)

 

2.2. 이진 탐색 (Binary Search)

Divide-and-Conquer 방법을 적용한 탐색 방법이다. 이진 탐색을 위해서는 리스트가 항상 정렬되어 있어야 한다.

• 비교 횟수 : 성공적인 탐색 and 성공적이지 않은 탐색 = logN+1회

 

 

3. 이진 탐색 트리 (Binary Search Tree)

이진 탐색 을 위한 이진 트리이다. 이 트리는 왼쪽 자신 노드는 나보다 작고, 오른쪽 자식 노드는 나보다 크다 라는 조건을 가지고 있다. 또한 이진 탐색 트리를 중위 순회 하면 데이터가 정렬되는 효과가 있다

 

3.1. 탐색 과정

1. 루트와 주어진 키를 비교
2. 키가 루트보다 작다면, 왼쪽 부분트리로 이동
3. 키가 루트보다 크다면, 오른쪽 부분트리로 이동
4. 키가 루트와 같다면, 종료

 

3.2. 성능 특성

• 탐색-삽입의 평균적인 비교 횟수 : logN
• 탐색-삽입의 최악의 경우 비교 횟수 : N

최악의 경우 : 정렬 또는 역순정렬된 리스트 or 큰 키와 작은 키가 교대로 나오는 경우

=> 이진 트리 탐색의 경우에는 트리를 균형있게 유지하면 최악의 경우를 피할 수 있음!

 

3.3. 수도 코드

searchBST(B,search_key)
	p ← B;
	if(p = null) then return null;
	
	if(p.key = search_key) then return p;
	if(p.key < search_key) then return searchBST(p.right,search_key);
	if(p.key > search_key) then return searchBST(p.left,search_key);
end searchBST()

 

 

4. 균형 트리

순수 BST는 한쪽으로 치우친 트리의 모습에서는 최악의 비교 횟수를 가진다. 따라서, 트리가 균형잡힌 모습으로 자라도록 하는 알고리즘이 필요한데 이를 위해서 균형 트리 를 사용한다.

 

4.1. AVL 트리

왼쪽 부분트리와 오른쪽 부분트리의 높이 차이는 1보다 크지 않다는 성질을 가진 트리이다. 균형잡힌 AVL 트리 는 n개의 원소가 있을 때, O(log n) 의 시간복잡도로 검색, 삽입, 삭제를 할 수 있다. 하지만 삽입과 삭제를 할 때에는 원하는 노드를 찾기 위해 2개의 경로가 필요하기 때문에 Red-black 트리 만큼 효율이 좋지 않아 자주 쓰이지는 않는다.

 

4.2. Red-black 트리

자가 균형 이진 탐색 트리(Self-balancing Binary Search Tree) 로써, 대표적으로 연관 배열 등을 구현하는데 쓰이는 자료구조이다. 최악의 경우에도 상당히 우수한 실행시간을 보이며, n개의 원소가 있을 때, O(log n) 의 시간복잡도로 검색, 삽입, 삭제를 할 수 있다. Java의 Treemap , C++ STL의 map 이 Red-black Tree 로 만들어져 있다.

 

레드-블랙 트리는 아래와 같은 조건을 가진다.

1. Root Property : 루트노드는 블랙이다
2. External Property : 모든 외부노드는 블랙이다
3. Internal Property : 레드노드의 자식은 블랙이다 (= 레드 노드가 연속으로 나올 수 없다)
4. Depth Property : 모든 단말노드에서 Black Depth는 같다

 

4.2.1. 회전

 

4.2.2. 삽입

Case 1. 부모 노드가 레드인데, 부모의 형제가 없거나 블랙일 때 - 회전

Case 2. 부모 노드가 레드인데, 부모의 형제가 레드일 때 - 색상 변환

(색상 변환은 부모 노드를 블랙 으로, 조상 노드를 레드 로 변환)

 

Restructuring

1. 자신 - 부모 - 조상 노드를 오름차순 정렬
2. 중간값을 부모 노드로 만들고 나머지를 자식 노드로 만듬
3. 부모를 블랙 으로, 두 자식을 레드 로 만든다

Recoloring

1. 현재 삽입된 노드의 부모와 그 형제를 블랙 으로 만들고, 조상 노드를 레드 로 만든다
2. 조상 노드가 루트가 아니라면, 다시 Double Red 가 발생할 수 있다

 

참고 블로그 : https://zeddios.tistory.com/237