[자료구조][C언어] selection tree- winner tree, loser tree의 구현

중앙대학교 소프트웨어대학 강현철교수님의 "자료구조" 과목을 듣는 과정에서 학습 목적으로 작성한 포스트입니다. 

 

Selection Tree(선택 트리)는 merge sort에 사용하는 특수한 구조를 가지는 트리 자료구조다.

selection tree에는 크게 winner tree와 loser tree가 있다. 

다른 말로는 tournament tree라고도 불린다.

 

(merge sort가 뭔지 모른다면 merge sort를 공부하고 와야 이 포스팅을 이해할 수 있다..!)

 

merge sort 출처: 위키

쪼갠 리스트들을 합치는 과정에서 각 리스트의 최솟값(최댓값)들을 비교해야 하기 때문에 n/2 , n/2개를 합칠때마다 (n-1)번의 비교횟수가 필요하다. 이걸 줄이기 위해서 선택트리를 이용한다. 

 

 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define numRow 5 /* power of 2 (2, 4, 8, 16, ...) */
#define numCol 10


int matrix[numRow][numCol] = {
  { 5,90,5,9,80,80,7,90,7,90 },
  { 100,30,30,51,160,160,160,51,160,59 },
  { 500,100,7000,100,900,600,100,100,650,100 },
  { 1000,300,41,300,41,41,41,900,900,950 },
  { 90,81,81,95,81,83,81,90,81,90 }
};


typedef struct NodeStruct {
  int value;
  int count;
  struct NodeStruct* leftChild;
  struct NodeStruct* rightChild;
  struct NodeStruct* loserNode;
  int run;
  
}Node;

Node* BST_insert(Node*, int);
Node* BST_delete(Node*, int);
Node* BST_search(Node*, int);
Node* findMinNode(Node*);
void winnerTreeMake(int);
Node* searchBSTree(Node*);
Node* InorderSearch(Node*);
void BST_print(Node*);
Node* CompareAndReturnLoser(Node*, Node*);
Node* CompareAndReturnWinner(Node*, Node*);
Node* compareAndSwap(Node**, int, Node*);
void Node_print(Node*);


Node* root[numRow] = { 0, };




Node* rootA = NULL;

Node* BST_insert(Node* root, int value) {
  if (root == NULL) {
    root = (Node*)malloc(sizeof(Node));
    root->leftChild = NULL;
    root->rightChild = NULL;
    root->value = value;
    root->count = 1;
    return root;
  }
  else {
    if (root->value > value)
      root->leftChild = BST_insert(root->leftChild, value);
    else if (root->value < value)
      root->rightChild = BST_insert(root->rightChild, value);
    else
      
      root->count++;
  }
  return root;
}
Node* findMinNode(Node* root) {
  Node* tmp = root;
  while (tmp->leftChild != NULL)
    tmp = tmp->leftChild;
  return tmp;
}
Node* BST_delete(Node * root, int value) {
  Node* tNode = NULL;
  if (root == NULL)
    return NULL;
  
  if (root->value > value)
    root->leftChild = BST_delete(root->leftChild, value);
  else if (root->value < value)
    root->rightChild = BST_delete(root->rightChild, value);
  else {
    if (root->rightChild != NULL && root->leftChild != NULL) {
      tNode = findMinNode(root->rightChild);
      root->value = tNode->value;
      root->rightChild = BST_delete(root->rightChild, tNode->value);
    }
    else {
      tNode = (root->leftChild == NULL) ? root->rightChild : root->leftChild;
      free(root);
      return tNode;
    }
  }
  
  return root;
}
Node* BST_search(Node * root, int value) {
  if (root == NULL)
    return NULL;
  
  if (root->value == value)
    return root;
  else if (root->value > value)
    return BST_search(root->leftChild, value);
  else
    return BST_search(root->rightChild, value);
}
void BST_print(Node * root) {
  if (root == NULL)
    return;
  
  BST_print(root->leftChild);
  printf("%d %d\n", root->value, root->count);
  BST_print(root->rightChild);
}


Node* biggestNode = NULL;

Node* searchBSTree(Node* rootNode) {
  
  
  if (rootNode == NULL) {
    Node* minusNode = (Node*)malloc(sizeof(Node));
    minusNode->count = 0;
    minusNode->value = -1;
    minusNode->run = -1;
    return minusNode;
  }
  
  biggestNode = rootNode;
  InorderSearch(rootNode);
  return biggestNode;
}

Node* InorderSearch(Node* currentNode) {
  if (currentNode == NULL) {
    return NULL;
  }
  InorderSearch(currentNode->leftChild);
  if ((currentNode->count) > (biggestNode->count)) {
    biggestNode = currentNode;
  }
  else if ((currentNode->count) == (biggestNode->count)) {
    if ((currentNode->value) > (biggestNode->value)) {
      biggestNode = currentNode;
    }
  }
  InorderSearch(currentNode->rightChild);
  return biggestNode;
}

Node* CompareAndReturnWinner(Node* A, Node* B) {
  if (A->count == B->count) {
    if (A->value == B->value) {
      return A->run > B->run ? A : B;
    }
    else {
      return A->value > B->value ? A : B;
    }
  }
  else {
    return A->count > B->count ? A : B;
  }
}
Node* CompareAndReturnLoser(Node* A, Node* B) {
  if (A->count == B->count) {
    if (A->value == B->value) {
      return A->run > B->run ? B : A;
    }
    else {
      return A->value > B->value ? B : A;
    }
  }
  else {
    return A->count > B->count ? B : A;
  }
}


Node* compareAndSwap(Node** loserArray, int championIndex, Node* challenger) {
  Node* champion = loserArray[championIndex];
  
  if (CompareAndReturnWinner(champion, challenger) == champion) {
    loserArray[championIndex] = challenger;
    return champion;
  }
  else {
    return challenger;
  }
}

Node** winnerArray;
Node** loserArray;
void winnerTreeMake(int numOfLeaf) {
  
  int height = 1;
  numOfLeaf--;
  while (numOfLeaf > 0) {
    numOfLeaf = numOfLeaf / 2;
    height = height + 1;
  }
  
  int sizeOfArray = (int)pow(2, height);
  
  
  loserArray = (Node**)malloc(sizeof(Node*) * (sizeOfArray));
  for (int i = 0; i < sizeOfArray; i++) {
    loserArray[i] = (Node*)malloc(sizeof(Node));
    loserArray[i]->count = 0;
    loserArray[i]->value = -1;
    loserArray[i]->run = -1;
  }
  
  winnerArray = (Node**)malloc(sizeof(Node*) * (sizeOfArray));
  for (int i = 0; i < sizeOfArray; i++) {
    winnerArray[i] = (Node*)malloc(sizeof(Node));
    winnerArray[i]->count = 0;
    winnerArray[i]->value = -1;
    winnerArray[i]->run = -1;
  }
  
  
  int indexOffset = (int)pow(2, height - 1);
  for (int i = 0; i < numRow; i++) {
    Node* firstValue = searchBSTree(root[i]);
    
    winnerArray[i + indexOffset]->value = firstValue->value;
    winnerArray[i + indexOffset]->count = firstValue->count;
    winnerArray[i + indexOffset]->run = i;
    
    loserArray[i + indexOffset]->value = firstValue->value;
    loserArray[i + indexOffset]->count = firstValue->count;
    loserArray[i + indexOffset]->run = i;
    
    root[i] = BST_delete(root[i], firstValue->value);
  }
  
  
  for (int i = pow(2, height) - 1; i > 1; i -= 2) {
    winnerArray[i / 2] = CompareAndReturnWinner(winnerArray[i], winnerArray[i - 1]);
    loserArray[i / 2] = CompareAndReturnLoser(winnerArray[i], winnerArray[i - 1]);
  }
  
  
  Node** winnernode = (Node**)malloc(sizeof(Node*) * (numRow*numCol));
  for (int i = 0; i < numRow*numCol; i++) {
    winnernode[i] = (Node*)malloc(sizeof(Node));
  }
  
  winnernode[0]->value = winnerArray[1]->value;
  winnernode[0]->count = winnerArray[1]->count;
  winnernode[0]->run = winnerArray[1]->run;
  int resultLength = 0;
  for (int i = 0; i < numRow*numCol; i++) {
    
    int winnersRun = winnernode[i]->run;
    Node* nextNode = searchBSTree(root[winnersRun]);
    
    loserArray[winnersRun + indexOffset] = (Node*)malloc(sizeof(Node));
    loserArray[winnersRun + indexOffset]->value = nextNode->value;
    loserArray[winnersRun + indexOffset]->count = nextNode->count;
    loserArray[winnersRun + indexOffset]->run = winnersRun;
    
    root[winnersRun] = BST_delete(root[winnersRun], nextNode->value);
    
    nextNode = loserArray[winnersRun + indexOffset];
    
    int nextParentIndex = (winnersRun + indexOffset) / 2;
    for (int i = 0; i < height - 1; i++) {
      nextNode = compareAndSwap(loserArray, nextParentIndex, nextNode);
      nextParentIndex /= 2;
    }
    
    if (nextNode->count == 0) {
      resultLength = i + 1;
      break;
    }
    winnernode[i + 1]->value = nextNode->value;
    winnernode[i + 1]->count = nextNode->count;
    winnernode[i + 1]->run = nextNode->run;
  }
  for (int i = 0; i < resultLength; i++) {
    Node_print(winnernode[i]);
  }
}

void Node_print(Node* target) {
  printf("(%d, %d, %d)\n", target->run, target->value, target->count);
}


int main() {
  
  for (int i = 0; i < numRow; i++) {
    for (int j = 0; j < numCol; j++) {
      root[i] = BST_insert(root[i], matrix[i][j]);
      //printf("%d insert done, value: %d\n", i, matrix[i][j]);
    }
  }
  
  for (int k = 0; k < numRow; k++) {
    BST_print(root[k]);
    printf("\n");
  }
  winnerTreeMake(numRow);
  return 0;
}