1. 트리

주요용어

• 트리 : 트리는 논리적 계층이 있는 구조이며, 트리를 구성하는 항목을 노드(node) 혹은 점(vertex)이라고 함
• 루트 : 트리에서 부모를 갖지 않은 노드
• 진입 차수 : 트리에 있는 어떤 노드에 대해 그 노드로 들어오는 선의 개수
• 진출 차수 : 트리에 있는 어떤 노드에 대해 그 노드에서 나가는 선의 개수
• 내부 노드 : 루트도 잎도 아닌 노드
• 형제(sibling) : 같은 부모를 갖는 노드들
• 포화 이진 트리 : 이진 트리에서 각 레벨이 허용되는 최대 개수 노드를 가지는 트리
• 완전 이진 트리 : 높이가 k인 이진 트리가 레벨 0부터 k-2까지 다 채우고 마지막 k-1 레벨에서 왼쪽부터 오른쪽으로 노들들이 차례로 채워진 트리
• 순회(traverse) : 트리의 각 노드를 빠짐없이 한 번씩만 방문하는 것

내용

• 트리의 정의
  • 트리
    • 검색의 편리함
    • 논리적 계층
    • 계급적 특성
• 트리의 구성
  • 노드: 트리의 항목/트리에 저장되는 데이터의 묶음
  • 부모노드-자식노드: 상하 계층구조가 있고 직접적으로 연결된 노드로서 상위계층의 부모노드와 하위계층의 자식 노드
• 트리의 레벨
  • 노드의 레벨: 루트로부터 그 노드까지 이어진 선(경로)의 길이
  • 트리의 높이: 루트로부터 가장 멀리 있는 노드까지 이어진 선(경로)의 길이에 1을 더한 값
• 이진 트리
  • 이진 트리의 정의
    • 모든 노드의 차수가 2 이하인 트리
    • 수학적으로 이진트리의 구성에 관한 이론을 정리하기 쉽고, 컴퓨터 내부에서 구현하기도 효율적임
    • 모든 노드가 2개 이하의 자식노드를 가지므로 일반성을 잃지 않고 ‘오른쪽’, ‘왼쪽’이라는 방향개념을 부여할 수도 있음
      • 오른쪽 노드, 왼쪽 노드의 개념적 접근도 있음
• 포화 이진 트리
  • 이진 트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리
• 완전 이진 트리
  • 높이가 k인 이진 트리가 ‘0레벨’부터 ‘k-2레벨’까지 다 채우고, 마지막 ‘k-1 레벨’에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워진 이진트리
• 이진 트리의 구현
  • 배열을 이용한 이진 트리의 구현
    • 트리가 완전 이진 트리 또는 포화 이진 트리인 경우 낭비되는 공간이 없어 효율적임
    • 트리가 깊어질수록 기억장소 낭비가 2의 거듭제곱에 비례하며 낭비가 심해짐
  • 포인터를 이용한 이진 트리의 구현

    • 포인터를 이용한 이진 트리의 노드 생성

      struct node {
      	struct node *left;
      	struct node *right;
      	int info;
      }

이진 트리 연산

• 이진 트리 순회

  • 이진 트리의 전위 순회
    • 루트노드-왼쪽 자식노드-오른쪽 자식노드
  • 이진 트리의 후위 순회
  • 이진 트리의 순회 알고리즘
    • 전위 순회(PLR)

      struct node *nodeptr;
      void preorder(struct node *tree_ptr) {
      	if (tree_ptr) {
      		printf("%d", tree_ptr -> info);
      		preorder(tree_ptr->left);
      		preorder(tree_ptr->right);
      	}
      }

    • 중위 순회(LPR)

      struct node *nodeptr;
      void preorder(struct node *tree_ptr) {
      	if (tree_ptr) {
      		preorder(tree_ptr->left);
      		printf("%d", tree_ptr -> info);
      		preorder(tree_ptr->right);
      	}
      }

• 이진 트리 생성/삽입/삭제

  • 일반적인 이진 트리를 생성하는 것은 연결 리스트 연산을 사용함
  • 첫 노드를 생성하면 루트 노드가 되고, 새로운 노드를 추가하려면 연결 리스트의 삽입 연산을 사용함
  • 노드를 삭제할 떄, 삭제하려는 노드가 리프노드인 경우는 해당 노드를 가리키는 포인터를 null로 지정하면 됨
  • 리프노드가 아닌 경우에는 삭제하려는 노드의 자식노드에 대한 처리를 추가로 해주어야 함

• 이진 트리 노드 개수 세기

  int get_node_count(nodeptr *root) {
      if (root == null) return 0;
      int result = 1;
      result = get_node_count((nodeptr*) root -> left)
                  +
                  get_node_count((nodeptr*) root -> right);
      reurn result;
  }

  int get_leaf_count(nodeptr *root) {
      int root = 0;
      if (root == null) {
          return 0;
      } elst if (root->left == null && root->right == null) {
          return 1;
      }
  
      result = get_leaf_count((nodeptr*) root -> left)
                  +
                  get_leaf_count((nodeptr*) root -> right);
      reurn result;
  }

요약

• 트리는 논리적 계층이 있는 구조입니다.
• 트리를 구성하는 항목을 노드 혹은 정점(vertex)이라고 합니다.
• 트리에서 루트는 부모를 갖지 않은 노드입니다.
• 트리에 있는 어떤 노드에 대해 그 노드로 들어오는 선의 개수를 진입 하수, 나가는 선의 개수를 진출 차수라고 합니다.
• 트리에서 각 노드의 차수는 진출 차수로 정의합니다.
• 트리이 차수는 트리 내의 각 노드의 차수 가운데 최대 차수로 정의합니다.
• 루트도 잎도 아닌 노드를 내부 노드라 하고 같은 부모를 갖는 노드를 형제라고 합니다.
• 트리에서 각 노드의 레벨은 루트로부터 그 노드까지 이어진 경로의 길이로 정합니다.
• 트리는 데이터의 계층 관계, 포함 관계 등을 나타내는 자료구조입니다.
• 트리에 속한 모든 노드의 차수가 2 이하인 트리를 이진 트리라고 합니다.
• 이진 트리에서 각 레벨이, 허용되는 최대 개수 노드를 가질 때 그 트리를 포화 이진 트리라고 합니다.
• 높이가 k인 이진 트리가 레벨 0부터 레벨 k-2까지 다 채우고 마지막 k-1레벨에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워졌을 떄 완전 이진 트리라고 합니다.
• 트리의 각 노드를 빠짐없이 한 번씩만 방문하는 것을 순회라고 합니다.
• 루트를 방문하는 순서에 따라 각각 전위 순회, 중위 순회, 후위 순회라고 구분하여 부릅니다.

2. 스레드 트리

주요용어

• 스레드(thread) : 정해진 순회 방법에 따른 방문순서를 유지하는 포인터
• 스레드 트리 : 스레드라는 포인터를 갖는 이진 트리
• 오른쪽 스레드 : 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킴
• 왼쪽 스레드 : 정해진 순회 순서에 따른 그 노드의 선행 노드를 가리킴
• 이진 트리의 null 포인터 개수 : 2n-(n-1) = n+1개

내용

• 스레드 트리의 정의
  • 스레드 트리
    • 이진 트리의 노드 순회: 전위 순회, 중위 순회, 후위 순회
    • 이진 트리의 노드를 순회할 때, 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리해야하는 번거로움이 발생함
    • 스레드 트리: ‘스레드;라는 포인터를 추가하여 트리 순회를 편리하게한 것
• 스레드 트리의 구현

  • 포인터 필드의 추가: 스레드를 저장하는 포인터를 추가하는 것

    • 왼쪽 스레드 포인터, 왼쪽 자식 포인터 데이터, 오른쪽 자신 포인터 오른쪽 스레드 포인터 필드로 노드 구조를 정의함

  • 오른쪽 스레드: 정해진 순회 순서에 따른 그 노드의 추속 노드를 가리키고

  • 왼쪽 스레드: 그 노드의 선행 노드를 가리킴

  • 포인터 필드의 추가

    struct TNode {
    	int info;
    	TNode left;
    	TNode right;
      TNode right_thread;
    	TNode left_thread;
    }

  • 추가된 포인터 필드를 이용한 중위 순회 연산

    void inorder(struct TNode *firstin) {
    	struct TNode *p;
    	p = firstin;
    	while(p != NULL) {
    		printf("%d", p->info);
    		p = p->right_thread;
    	}
    }

  • 추가된 포인터 필드를 이용한 중위 순회 연산과정

    • 순회할 트리의 노드를 가리키는 포인터 firstin을 매개변수로 하는 함수의 이름을 inorder()로 합니다.
    • 노드를 가리킬 수 있는 (TNode) 타입의 포인터 p를 생성하고 루트 노드를 가리키도록 합니다.
    • 포인터 p가 가리키는 데이터(info)를 출력하고 p를 p의 오른쪽 스레드 값으로 바꾸어 (p → right_thread) 중위 순회에 따른 다음 노드를 가리키도록 수정 합니다.
    • 이 과정을 p가 null이 될 때까지 반복합니다.
    • 스택을 운영하지 않고도 쉽게 트리에 속한 모든 노드를 순회 할 수 있음
    • 하지만 스레드를 위해 추가 기억장소를 사용한다는 부담이 생김
• 스레드의 구현 방법(2)
  • 잎 노드의 빈 포인터 필드의 활용
    • 이진 트리의 포인터 갯수 (노드이 개수를 n개라 가정함): 왼쪽 서브트리를 가리키는 포인터 n개 + 오른쪽 서브트리를 가리키는 n개 = 2n개의 포인터
  • 노드의 빈 포인터 필드의 활용
    • 루트 노드를 제외한 각 노드 개수는 모두 진입 차수는 1이 되므로,
    • 루트 노드를 제외한 전체 노드 죽, 누군가로부터 가리켜져 야 할 노드의 개수: n-1
    • null이 아닌 포인터 개수 : n-1
    • 2n - (n-1) = n+1개의 null 포인터가 노드에 존재함
    • 2n - (n-1) = n+1개의 null 포인터를 스레드로 활요함
    • 이진 트리의 중위 순회: 어떤 노드 x에 대해 오른쪽 포인터가 null이면 이 포인터를 x 노드의 다음으로 순회되는 노드를 가리키도록 하고, 왼쪽 포인터가 null이면 x 노드의 바로 직전에 순회된 노드를 가리키게 함
    • 각 노드에 대해 포인터가 스레드로 사용 중인지 아니면 서브트리에 대한 포인터인지 구분하기 위해 태그 필드가 필요함 (삽입/삭제 연산에서 반드시 필요함)
    • 전위 순회 : 각 노드의 왼쪽 포인터 필드를 스레드로 사용하는 제한을 가정함
      • 어떤 노드의 왼쪽 포인터가 실제 왼쪽 자식을 가리키면 그대로 두고,
      • null이면 전위 순회로 순회할 때 다음으로 순회되는 노드를 가리키도록 지정함
• 스레드 트리 삽입 연산
  • 전위 순회 스레드 트리의 전위 순회 연산

    void Preordthr(struct TFNode *root) {
    	struct TFNode *p;
    	p = root;
    	while(p != null) {
    		printf("%d", p->info);
    		p = p->left;
    	}
    }

  • 중위 순회 스레드 트리의 노드 삽입 연산
    • 스레드 트리의 노드 삽입 연산(1)

      void insert(struct Tnode *x, struct Tnode **ttree) {
      	ttree -> left = NULL;
      	ttree -> right = x -> right;
      	ttree -> right_thread = x->right_thread;
      	x->right = ttree;
      	x->right_thread = ttree;
      }

• 스레드 트리 삭제 연산
  • 스레드 트리의 내부 노드 삭제: 삭제된 노드의 자식 노드를 처리 방법이 필요함
    • 노드의 자식 노드를 모두 삭제하는 방법
    • 삭제하려는 노드 x의 왼쪽 서브 트리나 오른쪽 서브 트리의 루트를 x가 있던 우치로 옮기는 방법
    • 잎 노드가 아닌 노드를 삭제하지 못하게 하는 것

3. 힢

주요용어

• 힢: 부모노드와 자식노드 사이의 대소관계가 정의되어 구성되는 완전 이진트리로 우선순위 큐와 같은 결과를 제공함
• 최대힢: 루트가 가장 큰 값을 갖고 부모는 자식보다 큰 값을 가지면 됨
• 최소힢: 루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가지면 됨

내용

• 우선순위 큐
  • 우선순위 큐의 작동 방식:
    • 첫째, 삭제 명령이 실행되면 저장된 데이터 중에서 가장 작은 값(가장 큰 값)이 삭제된다.
    • 둘때, 나머지 데이터들은 어떤 순서로 저장되든 문제가 되지 않는다.
• 힢(Heap)
  • 힢의 정의
    • 피라미드 모양으로 쌓아 올린 더미
    • 무엇인가 쌓아놓은 더미이고 항상 가장 위에 있는 것을 우선 꺼내는 구조
    • 부모-자식 노드사이에서(부분적으로) 정렬된 완전 이진 트리로 부모노드는 자식노드보다 우선순위가 높음
  • 힢의 종류
    • 최소 힢: 루트가 전체 노드중에서 최소값인 힙
      • 트리의 모든 노드가 자식 노드보다 작은 값을 가짐
      • 트리의 레벨에 따라 데이터가 순서를 갖지는 않음
      • 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음
      • 루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가짐
    • 최대 힢: 루트가 전체 노드중에서 최소값인
      • 트리의 모든 노드가 자식 노드보다 큰 값을 가짐
      • 트리의 레벨에 따라 데이터가 순서를 갖지는 않음
      • 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음
      • 루트가 가장 큰 값을 갖고 부모는 자신보다 큰 값을 가지면 됨
• 힢의 구현
  • 힢 구현을 위한 자료구조
    • 배열을 이용한 힙의 구현: 완전 이진트리이기 때문에 배열로 구현해도 기억장소 낭비가 없음
      • 연결 리스트보다 실행 속도 면에서 효율적임
      • 기억장소 측면에서도 장점을 가짐

힢의 노드 삽입

• 시간 복잡성 = O(log2n)
  

        void insert_max_heap(int item, int *n) {
        	// 노드 수가 *n인 최대 히프에 item 값을 추가
            int i;
            if (HEAP_FULL(*n)) {
            	fprintf(stderr, "The heap is full. \n");
                exit(1);
            }
        	i = ++(*n);
        	while((i != 1 && (item > heap[i/2])) {
        		heap[i] = heap[i/2];	// 부모 노드의 값을 아래로 이동
        		i /= 2;	// 한 레벨 위로 이동
        	}
        	heap[i] = item;
        }

힢의 노드 삭제

        int delete_max_heap (int *n) {
          int parent, child;
          int item, temp;

          if (HEAP_EMPTY (*n)) {
            fprintf(stderr, "The heap is empty\n"); exite(1);
          }

          item = heap[1];
          temp = heap[(*n)--];	// 제일 마지막 원소를 비교 대상으로
          parent = 1; child = 2;	// 루트 노드부터 시작
          while (child <= *n) {
            // 두 개의 자식 노드 중에 큰 쪽과 비교
            if ((child < *n) && (heap[child] < heap[child+1])) 
            	child++;	
            if (temp >= heap[child]) brak;	// 더 이상 내려갈 필요 없음
            heap[parent] = heap[child];	// child의 데이터를 위로 이동
            parent = child;	// 아래로 내려가자
            child *= 2;
          }
          heap[parent] = temp;
          return item;
        }