05 (월)

오늘 한줄 피드백

공부 하려고 학교에 갔지만 정작 공부를 별로 못한 오늘. 여자친구와 카공하며 빡공한다는 건 어불성설.

자료구조

주로 트리에 대해 공부했다.

---

기본개념

• degree : 자식의 갯수
• level : depth랑 비슷한 개념, root노드의 level은 1이고 maximum level==height
• complete binary tree : 마지막 level-1까지의 level은 전부 채워져 있고, 마지막 level은 왼쪽부터 채워져나가는 binary tree

Traversal

typedef struct _node{
  int data;
  struct _node* left;//struct 빼먹지 않기
  struct _node* right;
}node;

void inorder(node* root){
  if(root){//null이라면 접근 못하도록 조건문
    inorder(root->left);
    printf("%d\n",root->data);
    inorder(root->right);
  }
}

node* makenode(node* root,int num){
  int n=7;//n is f 2^k-1 for k is positive integer
  if(num<=n){
    node *ptr1=(node*)malloc(sizeof(node));
    ptr1->left=NULL;
    ptr1->right=NULL;
    node *ptr2=(node*)malloc(sizeof(node));
    ptr2->left=NULL;
    ptr2->right=NULL;
    root->data=num;
    root->left=makenode(ptr1,2*num);
    root->right=makenode(ptr2,2*num+1);
    return root;
  }
  else {//이상의 값이면 더미 root를 반환하는게 아니라 NULL을 반환
    return NULL;
  }
}

int main(void){
  node *ptr=(node*)malloc(sizeof(node));
  ptr->data=1;
  ptr->left=NULL;
  ptr->right=NULL;
  makenode(ptr,1);
  inorder(ptr);
  return 0;
}

재귀가 아닌 반복문을 사용한다면?

void iter_inorder(tree_pointer ptr) { 
  int top = -1;
  tree_pointer stack[MAX_STACK_SIZE];
  for( ; ; ) {
    for( ; ptr; ptr = ptr->left_child)
      stack[++top] = ptr;
    if(top < 0) break;
    ptr = stack[top--];
    printf("%c ", ptr->data);
    ptr = ptr->right_child;
  }
}

두 노드가 같은 지, 다른 지 비교할 땐 NULL일 때도 비교해야 한다.

//node가 같은지 비교
int equal(tree_pointer first, tree_pointer second) {
    //둘다 NULL이면 TRUE, 아니면 둘다 NULL이 아니면서 모든 값이 같아야 한다
  return((!first && !second) || (first && second &&
         (first->data == second->data) &&
         equal(first->left_child, second->left_child) &&
         equal(first->right_child, second->right_child))
}

Threaded Binary Tree

struct threaded_tree {
  short int left_thread;
    struct threaded_tree *left_child; 
    char data;
    struct threaded_tree *right_child; 
    short int right_thread;
};

tree구조의 leaf를 살펴보면 자식이 없기 때문에 해당 포인터가 NULL값을 같는데, perfect binary tree에서 leaf노드의 갯수가 leaf노드가 아닌 갯수보다 많기 때문에 이는 메모리 낭비가 심하다.
이를 해결하기 위해 노드의 구조체에서 thread를 추가한다.
thread를 실처럼 생각해 모든 노드를 하나로 이어준다.

threaded_pointer insucc(threaded_pointer tree) {
    /* find the inorder successor of a tree in a threaded binary tree */ 
    threaded_pointer temp;
    //right_thread가 true -> leaf -> right_child가 successor(후위)
    //right_thread가 false -> !leaf -> right_child에서 left_child가 leaf일때까지 내려가기
    temp = tree->right_child;
    if(!tree->right_thread)//null이라면
        while(!temp->left_thread)
          temp = temp->left_child;
    return temp;//참이라면 leaf임으로 그대로 반환
}

Heap

데이터를 저장하기 위한 방법. 찾거나 삽입하거나의 시간복잡도가 O(log n)이라 유용하게 사용한다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_ELEMENTS 200
#define HEAP_FULL(n) (n == MAX_ELEMENTS-1)
#define HEAP_EMPTY(n) (!n)

typedef struct {
  int key;
} element;
element heap[MAX_ELEMENTS];
int n = 0;

void insert_max_heap(element item, int *n);
element delete_max_heap(int *n);

int main() {

  int i, rn;
  element item;

  srand(time(NULL));
 
  printf("INSERTING: ");
  for(i=0; i<10; i++) {
    rn = rand() % 100 + 1;
    printf("%3d ", rn);
    item.key = rn;
    insert_max_heap(item, &n);
  }
  printf("\n\n");

  printf("DELETING:  ");
  for(i=0; i<10; i++) {
    item = delete_max_heap(&n);
    printf("%3d ", item.key);
  }
  printf("\n");
}

void insert_max_heap(element item, int *n) {
  /* insert item into a max heap of current size *n */
  int i;
  if(HEAP_FULL(*n)) {
    fprintf(stderr, "The heap is full.\n");
    exit(1);
  }
      i = ++(*n);
    /* 항상 마지막배열+1에서 시작, 부모노드와 비교하여 더 크면 교체 
        root노드에 도달하면 종료 */
  while((i != 1) && (item.key > heap[i/2].key)) {
    heap[i] = heap[i/2];
    i /= 2;
  }
  heap[i] = item;
}

element delete_max_heap(int *n) {
  /* delete element with the highest key from the heap */
  int parent, child;
  element item, temp;
  if(HEAP_EMPTY(*n)) {
    fprintf(stderr, "The heap is empty");
    exit(1);
  }
    //root노드의 값을 pop, 마지막노드를 root노드로 가져와 비교해보며 리빌딩
  /* save value of the element with the largest key */
  item = heap[1];
  /* use the last element in the heap to adjust heap */
  temp = heap[(*n)--];
  parent = 1;
  child = 2;
  while(child <= *n) {
    /* find the larger child of the current parent */
    if((child < *n) && (heap[child].key < heap[child+1].key)) child++;
    if(temp.key >= heap[child].key) break;
    /* move to the next lower level */
    heap[parent] = heap[child];
    parent = child;
    child *= 2;
  }
  heap[parent] = temp;
  return item;
}

Binary Search Tree

바이너리 트리에 갑이 들어가 있다 왼쪽자식은 부모노드보다 작은 값, 오른쪽자식은 부모노드보다 큰 값을 갖는다.

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_STACK_SIZE 100
#define LEFT 0
#define RIGHT 1

typedef struct {
    int key;
} element;

struct node {
    element data;
    struct node *leftChild;
    struct node *rightChild;
};
typedef struct node* treePointer;

void inorder(treePointer ptr) {
    if(ptr) {
        inorder(ptr->leftChild);
        printf("%d ", ptr->data.key);
        inorder(ptr->rightChild);
    }
}

treePointer modifiedSearch(treePointer node, int k) {
    treePointer parent = NULL;
    while(node) {
        if(k == node->data.key) return NULL;
        parent = node;
        if(k < node->data.key) node = node->leftChild;
        else node = node->rightChild;
    }
    return parent;
}

void insertNode(treePointer *node, int k) {
    // if the key is already in the tree, do nothing; otherwise add a new node with key k
    treePointer ptr, temp = modifiedSearch(*node, k);
    if(temp || !(*node)) {
        // k is not in the tree
        ptr = (treePointer)malloc(sizeof(*ptr));
        ptr->data.key = k;
        ptr->leftChild = ptr->rightChild = NULL;
        if(*node) {
            if(k < temp->data.key) temp->leftChild = ptr;
            else temp->rightChild = ptr;
        }
        else *node = ptr;
        printf("node with key %d inserted.\n", k);
    } else {
        printf("key %d is already in the tree.\n", k);
    }
}

void deleteNode(treePointer *root, int k) {
    treePointer node = *root;
    treePointer parent = NULL;
    int which_child;
    
    // search for the node
    while(node) {
        if(k == node->data.key) break;
        parent = node;
        if(k < node->data.key) {
            node = node->leftChild;
            which_child = LEFT;
        }
        else {
            node = node->rightChild;
            which_child = RIGHT;
        }
    }

    // case 1: if the node does not exist, we are done.
    if(node == NULL) return;

    // case 2: if the node is a leaf node, just set the corresponding child field of its parent to NULL and free the node.
    if(node->leftChild == NULL && node->rightChild == NULL) {
        if(parent == NULL) {
            // this is a root node
            *root = NULL;
        }
        else {
            if(which_child == LEFT) parent->leftChild = NULL;
            else parent->rightChild = NULL;
        }
        free(node);
    }
    // case 3: if the node is a non-leaf node with a single child
    else if(node->leftChild == NULL || node->rightChild == NULL) {
      if(which_child==LEFT){//어느 방향으로 왔는지 확인
                //어느 노드가 비어있는지 확인
        if(node->leftChild==NULL) parent->leftChild=node->rightChild;
        else parent->leftChild=node->leftChild;
      }
      else{
        if(node->leftChild==NULL) parent->rightChild=node->rightChild;
        else parent->rightChild=node->leftChild;
      }
    }

    // case 4: if the deleted node is a nonleaf node with two children
    // 큰쪽의 가장 작은 수 or 작은쪽의 가장 큰 수, 작은쪽의 가장 큰 수 채택
    else {
      treePointer temp = node;
      treePointer tempParent = node;
      temp=temp->leftChild;
      if(!temp->rightChild){
        tempParent=temp;
        temp=temp->rightChild;
      }
      node->data=temp->data;
      if(tempParent==node){//NULL로 초기화하는 것이 아니라 이어주기
        tempParent->leftChild=node->leftChild;
      }
      else{
        tempParent->rightChild=node->rightChild;
      }
    }
}

int main() {
   
    treePointer root = NULL;
    insertNode(&root, 8);
    insertNode(&root, 6);
    insertNode(&root, 9);
    insertNode(&root, 7);
    insertNode(&root, 10);
    insertNode(&root, 7);
    inorder(root); printf("\n");
    deleteNode(&root, 9);
    inorder(root); printf("\n");
}

중위순회방식으로 데이터가 저장된다. Insert과정에서는 case분류를 할 필요 없지만 Delete과정에서는 case를 분류한다.

Selection Trees

토너먼트 경기처럼 해석한다. n개의 팀이 있고, n-1번의 경기가 있다.
각 팀은 가중치 값을 가지고 있다.
승자트리(Winner Tree), 패자트리(Looser Tree) 두 종류가 있다.

• 승자트리 : 두 팀의 가중치를 비교해 더 작은 값을 진출시킨다. 계속 반복해 가장 작은 값이 우승을 한다. 시간복잡도는 n개의 팀이 log n만큼의시간이 걸리는 정렬방법을 사용하므로 O(n log n)이다
• 패자트리 : 승자트리와 똑같은 방식인데, 표기는 패자 팀을 기록한다. 이후 토너먼트에서도 패자 팀을 기록한다. 그리고 최종승자는 임의의 최상위 노드를 새로만들어 저장한다. 이렇게 하면 각 팀을 배열로 생각했을 때, 패자트리는 승자트리에서 하는 형제끼리의 계산을 하지 않아도 되므로 미세한 시간이득이 발생한다.