[자료구조] 6주차 - 트리 (Tree)

Tree

선형 자료구조의 한계

• 2개 이상의 관계를 표현할 수 없음

계층적 구조

1. 하나의 근원(root)으로부터 파생됨
2. 한 노드가 여러 개의 노드로 전파됨
3. 순환하는 경로(cycle path)가 없음

트리

1. 루트(root)라고 불리는 특별한 노드가 있음
2. 연결된 모든 노드의 쌍은 재귀적으로 부모자식관계(parent-child relation)을 맺음
3. 순환하는 경로(cycle path)가 없음

용어

• node (vertex)
  • Root node, Leaf node, Internal node
  • 부모 노드(Parent node), 자식 노드(Child node), 형제 노드(Sibling node)
  • 조상 노드(Ancesor node), 후손 노드(Descendent node)
• 부분 트리 (subtree)
• Degree of a node : 한 노드가 갖는 자식노드의 개수
• Degree of a tree : 한 트리에 속한 노드들의 최대 degree
• 노드의 깊이(Depth of a node)
• 트리의 깊이(높이) (Depth of a tree)
  • Depth of a root = 1

트리의 자료구조

typedef class node *nptr;
class node {
    data_type data;    //1. 저장할 데이터
    int n_childs;    //2. 자식 노드의 수
    nptr *childs;    //3. 자식 노드에 대한 포인터
};

이진 트리

정의 : Degree가 2인 트리 (최대 노드의 수는 2개)

이진트리의 성질

1. i번째 레벨의 최대 노드의 수는 2^(i-1)개
   • 수학적 귀납법을 이용해 증명
2. depth가 k인 이진 트리의 최대 노드의 수는 2^k-1개
   • 수학적 귀납법을 이용해 증명
3. 원소가 있는 이진 트리에 대해서 (leaf node의 수) = (degree가 2인 노드의 수) + 1
   • 직접 증명법을 이용해 증명

특별한 이진트리

• 포화 이진 트리
  • depth가 k일 때 2^k - 1개의 노드를 갖는 이진 트리
• 완전 이진 트리
  • 같은 depth를 갖는 포화 이진 트리와 노드들 사이에 1:1 대응이 성립하는 이진 트리

트리 탐색

탐색

• root node로부터 시작해서 트리의 모든 노드를 방문하는 연산
• 모든 트리에서 적용되는 일반적인 탐색
  • 깊이 우선 탐색 DFS
  • 넓이 우선 탐색 BFS
• 이진 트리에만 적용되는 특별한 검색

노드와 그 자식 노드를 방문하는 순서에 따라 3가지 탐색이 가능

• 중위 우선 탐색 : 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드
• 전위 우선 탐색 : 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드
• 후위 우선 탐색 : 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드

탐색 시간 복잡도 : O(n)

이진 탐색 트리(Binary Search Tree)

이진 탐색 과정에서 분할되느 배열을 이진 트리에 대응시킨 구조

이진 탐색 트리의 조건

1. 모든 노드느 서로 다른 하나의 값(key)을 저장함
2. 왼쪽 subtree의 값들은 루트 노드의 값보다 더 작음
3. 오른쪽 subtree의 값들은 루트 노드의 값보다 더 큼
4. 왼쪽 subtree와 오른쪽 subtree는 이진 탐색 트리임

좋은 이진 탐색 트리와 나쁜 이진 탐색 트리

• 최선의 경우 : depth = O(log n)
• 최악의 경우 : depth = O(n)

이진 탐색 트리의 연산

생성(초기화)

• 이진 탐색 트리의 자료 구조

  typedef class node *nptr;
  class node{
      data_type key;
      nptr lchild, rchid;
  }

• root node를 선언

검색

• void node::search(int x){
      if(x == this->key){
          printf("Bingo! \n");
      }
      else if(x < this->key){
          if(this->key != NULL)
              this->lchild->search(x);
          else
              printf("Not found\n");
      }
      else{
          if(this->rchild != NULL)
              this->rchild->search(x);
          else
              printf("Not found\n");
      }
  }

• 시간 복잡도 : 트리의 깊이

  • 최선의 경우 O(log n)
  • 최악의 경우 O(n)

추가

• 새로운 원소를 저장하는 노드를 생성하여 추가

• 새로 추가되는 노드는 반드시 leaf node임

• void node::insert(int ) { 
      //  degenerate case: root node에 삽입
      if (this->key == -1) { 
          this->key = x; 
          return; 
      } 
      //  x와 key와 같으면 
      if ( this->key == x) {
          printf(“No duplicate data\n”); 
      } 
      //  x가 key보다 작으면 
      else if (x < this->key) { 
          // lchild에 추가 
          if(this->child != NULL){
              this->lchild->insert(x);
          }else{
              this->lchild = (nptr)malloc(sizeof(nod));
                 this->lchild->key = x;
              this->lchild->lchild = this->lchild->rchild = NULL;
          }
      } 
      //  x가 key보다 크면 
      else {
      // rchild에 추가 
      }
  }
  

• 시간 복잡도 : 트리의 깊이

  • 최선의 경우 O(log n)
  • 최악의 경우 O(n)

제거

• 제거할 노드를 찾아가는 과정은 검색/추가와 비슷한 재귀적 구조로 구현

• 어떤 노드를 제거하느냐에 따라 다른 연산 방법이 필요

  • Leaf node : 그냥 제거
  • 한 개의 child를 갖는 노드 : 제거 후 child node로 대체
  • 두 개의 child를 갖는 노드
    • 제거할 노드의 key를 left_max(right_min)으로 대체하고 left_max(right_min) 노드를 제거
    • left_max : 왼쪽 부분 트리의 원소 중 최대값
    • right_min : 오른쪽 부분 트리의 원소 중 최소값

• int node::remove(intx) { 
      //  x와 key가 같으면
      if (x == this->key) {
          printf("Removing %d\n", x); 
          // (1) 두 child가 다 NULL 
          // (2-1) lchild만 NULL
          // (2-2) rchild만 NULL
          // (3) 둘 다 NULL이 아닌 경우
      } 
      //  x가key보다작으면 
      else if (x < this->key) {
          if (this->lchild!= NULL) {
              if (this->lchild->remove(x) == 1)
                  this->lchild= NULL; 
          } else {
              printf("Not found %d in removing\n", x); 
          } return 0;
      }
      //  x가key보다크면
      else { 
          //
      }
  }

• // (1) 두 child가 다 NULL 
  if(this->lchild == NULL && this->rchild == NULL)
      return 1;
  // (2-1) lchild만 NULL
  if(this->lchild == NULL && this->rchild != NULL){
      this->key = this->rchild->key;
      this->lchild = this->rchild->lchild;
      this->rchild = this->rchild->rchild;
      return 0;
  }
  // (3) 둘 다 NULL이 아닌 경우 (left_max로 대체)
  if(this->lchild != NULL && this->rchild != NULL){
      this->key = this->lchild->get_max();
      //대체한 노드 제거(left subtree 중에서 key와 일치하는 노드를 제거)
      if(this->lchild->remove(this->key)==1) 
          this->lchild = NULL;
      return 0;
  }

• 시간 복잡도 : 트리의 깊이

  • 최선의 경우 O(log n)
  • 최악의 경우 O(n)

균형 이진 탐색 트리(Balanced Binary Search Tree)

height를 최소로 유지하도록 설계된 이진 탐색 트리

• AVL tree
  • 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 height의 차를 1이하로 유지
  • 추가/제거 연산을 해도 balance가 유지되도록 balancing 연산을 수행
    • Single left/right rotate
    • Double left/right rotate
• Red-black tree
  • 모든 노드는 red 또는 black
  • root node는 black
  • 모든 leaf node (NIL node)는 black
  • 한 노드가 red라면, 자식 노드는 모두 black
  • 한 노드에서 모든 자식 노드까지의 경로에는 동일한 수의 black 노드가 존잰
• 2-3 tree
  • 2개 또는 3개의 자식 노드를 갖는 탐색 트리
• B+ tree
  • 여러 개의 자식 노드를 갖는 트리 (k-ary tree)
    • 각 노드는 (k-1)개의 key 값과 k개의 부분 트리를 갖음

우선 순위 큐 Heap

우선 순위 큐 : 가장 우선 순위가 높은 원소가 가장 먼저 제거되는 큐

Heap : 트리를 기반으로 구현된 우선 순위 큐

완전 이진 트리임

• 최대힙(Max heap) : 모든 노드의 값은 자식 노드의 값들보다 작지 않음

• 최소 힙(Min heap) : 모든 노드의 값은 자식 노드의 값들보다 크지 않음

힙의 연산

• 추가(Push)
  • 큐에 새로운 원소를 삽입함
  • 새로운 원소의 위치는 그 중요도(priority)에 따라 결정됨
  • O(n)
• 제거(Pop)
  • 큐에서 가장 우선 순위가 높은 원소를 삭제함
  • O(n)
• 탑(Top)
  • 큐에서 가장 우선 순위가 높은 원소를 찾음
  • O(1)

힙의 구현

첫 번째 노드(원소)가 1번

• k 번째 노드의 부모 노드 : k/2
• k 번째 노드의 왼쪽 child node : 2*k
• k 번째 노드의 오른쪽 child node : 2*k + 1

힙의 자료구조

int cnt = 0;
int n = 1000;
int *heap = (int *)calloc(n, sizeof(int));

Heapify(k) 함수

• k 번째 노드로 부터 힙을 재구성 할 것
• 하향식 재구성(Topdown heapify)
  • leaf node까지 힙을 재구성
• 상향식 재구성(Bottomup heapify)
  • Root node까지 힙을 재구성

void heapify_topdown(int idx){    //recursive

    //leaf 노드일 경우
    if(2*idx > cnt)    retrun;

    //자식 노드가 하나일 경우
    if(2*idx == cnt){
        if(heap[idx] < heap[2*idx]);
            swap(&heap[idx], &heap[2*idx])
        return;
    }

    //자식 노드가 두 개일 경우

    //lchild가  부모와 rchild보다 클 경우 부모와 바꾸고 다시 heapify 수행
    if(heap[2*idx] >heap[2*idx+1] && heap[2*idx] > heap[idx]){
        swap(&heap[idx], &heap[2*idx]);
        heapify_topdown(2*idx);
    } 
    else if(hep[2*idx+1] > heap[2*idx] && heap[2*idx+1] > heap[idx]){
        swap(&heap[idx], &heap[2*idx+1]);
        heapify_topdown(2*+1);
    }
}

void heapify_bottomup(int idx){    //recursive
    // root noded일 경우
    if(idx ==1)
        return;

    if(heap[idx/2] < heap[idx]){
        swap(&heap[idx/2], &heap[idx]);
        heapify_bootomup(idx/2);
    }      
}

힙의 연산

• 추가

  • 원소를 힙의 마지막 위치에 삽입

  • heapify()를 이용해서 새로운 원소가 삽입된 힙을 재구성

  • void push(int ndata){
        cnt++;
        heap[cnt] = ndata;
    
        heapify_bottomup(cnt);
    }

  • 시간 복잡도 : O(log n)

    • 원소 추가 : O(1), 힙의 재구성 O(log n)

• 제거

  • root node에 저장된 값을 제거

  • 힙의 마지막 노드에 저장된 값을 루트노드로 옮김

  • 루트 노드로부터 하향식 힙 재구성 수행

  • int pop(){
        int temp = heap[1];
        heap[1] = heap[cnt];
        cnt--;
    
        heapify_topdown(1);
        return temp;    //제거된 노드를 반환
    }

  • 시간 복잡도 : O(log n)

    • root node의 원소 제거 : O(1), 마지막 노드 제거 : O(1), 힙의 재구성O(log n)

Heap sort

O(n log n) 정렬 알고리즘

n번 push

n번 pop

void heap_sort(int*arr, intn) { 
    int i;

    for ( i= 0; i< n; i++ )
        push (arr[i]);

    for ( i= 0; i< n; i++ )
        printf(“%d,  “, pop ( ));
}