Advertisement
Guest User

Untitled

a guest
Dec 17th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.66 KB | None | 0 0
  1. //
  2. // Created by skala_000 on 17/12/2017.
  3. //
  4. // Hw06.cpp : Defines the entry point for the console application.
  5. //
  6. #include <stdlib.h>
  7. #include <vector>
  8. #include <queue>
  9. #include <iostream>
  10. #include <stdio.h>
  11. #include <tchar.h>
  12. #include <SDKDDKVer.h>
  13.  
  14. //#include "stdafx.h"
  15. #ifdef _WIN32
  16. #define WINPAUSE system("pause")
  17. #endif
  18.  
  19. #define START_WEIGHT 0
  20. #define INS_PROB 2
  21.  
  22. using namespace std;
  23.  
  24.  
  25. //Global var
  26. int rCur = 0, RCT = 0, NN = 0, R_this = 0, maxDepth = 0, canAddTwo =0;
  27. queue<int> survivors;
  28.  
  29. struct node_t {
  30.  
  31.     int min = START_WEIGHT;
  32.     int max = START_WEIGHT;
  33.     int height = START_WEIGHT;
  34.     int deep = 0;
  35.  
  36.     /*node_t *rch = */ node_t *lch = NULL;
  37.     node_t *rch = NULL;
  38.  
  39.  
  40.     node_t(int min, int height, int deep) : min(min), height(height), deep(deep) {}
  41. };
  42.  
  43. int getMin(node_t* x) {
  44.     int min = 0;
  45.     min = (x->min);
  46.     return (min);
  47. }
  48.  
  49. int getMiddle(int x){
  50.     int tmp = 0;
  51.     tmp = x/2;
  52.     x++;
  53.     return x;
  54. }
  55.  
  56. int getHeight(node_t *x, bool left){
  57.     if(left){
  58.         if(x->lch == NULL){
  59.             return 0;
  60.         }
  61.         return (x->lch->height);
  62.     }else{
  63.         if(x->rch == NULL){
  64.             return 0;
  65.         }
  66.         return (x->rch->height);
  67.     }
  68. }
  69.  
  70. int moveNodes(int howDeepIsTree){
  71.     return (1 << (howDeepIsTree)) -1;
  72. }
  73.  
  74. int getMax(node_t* x) {
  75.     int max = 0;
  76.     if((x->max) == 0){
  77.         max = x->min;
  78.     }else{
  79.         max = x->max;
  80.     }
  81.     return (max);
  82. }
  83.  
  84. bool isInternal(node_t* x) {
  85.     bool innerNodes = ( (!((x->lch) == NULL)) && (!((x->rch) == NULL)) );
  86.     return innerNodes;
  87. }
  88.  
  89.  
  90.  
  91. node_t* rightRotation(node_t *&x) {
  92.     node_t* newParent;
  93.     newParent = x->lch;
  94.     x->lch = newParent->rch;
  95.     newParent->rch = x;
  96.     if(getHeight(x,1) <= getHeight(x,0)){
  97.         x->height = x->rch->height;
  98.     }else{
  99.         x->height = x->lch->height;
  100.     }
  101.     (x->height)++;
  102.     //setHeight(newParent);
  103.     if(getHeight(newParent,1) <= getHeight(newParent,0)){
  104.         newParent->height = newParent->rch->height;
  105.     }else{
  106.         newParent->height = newParent->lch->height;
  107.     }
  108.     (newParent->height)++;
  109.     return newParent;
  110. }
  111.  
  112. node_t* leftRotation(node_t *&x) {
  113.     node_t* newParent;
  114.     newParent = x->rch;
  115.     x->rch = newParent->lch;
  116.     newParent->lch = x;
  117.  
  118.     if(getHeight(x,1) <= getHeight(x,0)){
  119.         x->height = x->rch->height;
  120.     }else{
  121.         x->height = x->lch->height;
  122.     }
  123.     (x->height)++;
  124.  
  125.     if(getHeight(newParent,1) <= getHeight(newParent,0)){
  126.         newParent->height = newParent->rch->height;
  127.     }else{
  128.         newParent->height = newParent->lch->height;
  129.     }
  130.     (newParent->height)++;
  131.     return newParent;
  132. }
  133.  
  134. int geChildrenDiference(node_t* x) {
  135.     int result = (getHeight(x,1) - getHeight(x,0));
  136.     return result;
  137. }
  138.  
  139.  
  140.  
  141. void leafIsFull(int IK, node_t* x) {
  142.     if ((IK < (x->min))) {
  143.         node_t* XR = new node_t((x->max),   START_WEIGHT,0);
  144.         node_t* XL = new node_t(IK,         START_WEIGHT,0);
  145.  
  146.         x->max = START_WEIGHT;
  147.  
  148.         x->rch = XR;
  149.         x->lch = XL;
  150.     }else if (IK < (x->max)) {
  151.         node_t* XR = new node_t(x->max,     START_WEIGHT,0);
  152.         node_t* XL = new node_t(x->min,     START_WEIGHT,0);
  153.  
  154.         x->min = IK;
  155.         x->max = START_WEIGHT;
  156.  
  157.         x->rch = XR;
  158.         x->lch = XL;
  159.     }else{
  160.         node_t* XL = new node_t((x->min),   START_WEIGHT,0);
  161.         node_t* XR = new node_t(IK,         START_WEIGHT,0);
  162.  
  163.         (x->min) = (x->max);
  164.         (x->max) = START_WEIGHT;
  165.  
  166.         (x->rch) = XR;
  167.         (x->lch) = XL;
  168.     }
  169.  
  170. }
  171.  
  172.  
  173. node_t* rightLeftRotation(node_t *&n) {
  174.     n->rch = rightRotation(n->rch);
  175.     return leftRotation(n);
  176. }
  177.  
  178. node_t* leftRightRotation(node_t *&n) {
  179.     n->lch = leftRotation(n->lch);
  180.     return rightRotation(n);
  181. }
  182.  
  183. node_t* createNewTree(int depth) {
  184.     int temp_depth = depth;
  185.     if (!(temp_depth != maxDepth)) {
  186.         node_t* z = new node_t(survivors.front(), START_WEIGHT,0);
  187.         survivors.pop();
  188.         if (canAddTwo) {
  189.             temp_depth = survivors.front();
  190.             z->max = temp_depth;
  191.             survivors.pop();
  192.             canAddTwo--;
  193.         }
  194.         return z;
  195.     }
  196.     else {
  197.         node_t* z = new node_t(0, START_WEIGHT,0);
  198.         temp_depth = maxDepth + (depth*(-1));
  199.         z->height = temp_depth;
  200.         z->lch = createNewTree(depth + 1 + START_WEIGHT);
  201.         z->min = survivors.front();
  202.         survivors.pop();
  203.         if (canAddTwo) {
  204.             z->max = survivors.front();
  205.             survivors.pop();
  206.             canAddTwo--;
  207.         }
  208.         z->rch = createNewTree(depth + 1 + START_WEIGHT);
  209.         return z;
  210.     }
  211. }
  212.  
  213. node_t* insert(int IK, node_t* X, bool doAble) {
  214.     int res;
  215.  
  216.     if(X==NULL){
  217.         res = 0;
  218.     }else if(!(IK != X->min)){
  219.         res = 1;
  220.     }else if((IK == X->max)){
  221.         res = 2;
  222.     }
  223.  
  224.     switch(res){
  225.         //possible end of rec
  226.         case 0: X = new node_t(IK, START_WEIGHT,0);
  227.  
  228.         case 1: return X;
  229.  
  230.         case 2: return X;
  231.     }
  232.     node_t* tmp;
  233.     int tmp_int = 0;
  234.     if (isInternal(X) && (doAble)) {
  235.         int tmp_int_1 = 0;
  236.         if((!(IK >= (X->min)))&&(doAble)){
  237.             tmp = insert(IK, X->lch, 1);
  238.             X->lch = tmp;
  239.             tmp_int = geChildrenDiference(X);
  240.             if(tmp_int == INS_PROB) {
  241.                 rCur++;
  242.                 if (IK <= X->lch->min){
  243.                     X = rightRotation(X);
  244.  
  245.                 }else{
  246.                     X = leftRightRotation(X);
  247.                 }
  248.             }
  249.         }
  250.         else if ((IK > X->max)&&(doAble)) {
  251.             tmp = insert(IK, X->rch, 1);
  252.             X->rch = tmp;
  253.             tmp_int = geChildrenDiference(X);
  254.             if (tmp_int == -INS_PROB) {
  255.                 rCur++;
  256.                 if (IK > getMax(X->rch)){
  257.                     X = leftRotation(X);
  258.                 }else{
  259.                     X = rightLeftRotation(X);
  260.                 }
  261.             }
  262.         }else{
  263.             tmp_int_1 = X->min;
  264.             X->min = IK;
  265.             tmp = insert(tmp_int_1, X->lch, 1);
  266.             X->lch = tmp;
  267.             tmp_int = geChildrenDiference(X);
  268.             if (tmp_int == INS_PROB) {
  269.                 rCur++;
  270.                 if (IK <= getMin(X->lch)){
  271.                     X = rightRotation(X);
  272.                 }
  273.                 else if (IK > getMin(X->lch)){
  274.                     X = leftRightRotation(X);
  275.                 }else{
  276.                     printf("Error else\n");
  277.                 }
  278.             }
  279.         }
  280.         if(getHeight(X,1) <= getHeight(X,0)){
  281.             X->height = X->rch->height;
  282.         }else{
  283.             X->height = X->lch->height;
  284.         }
  285.         (X->height)++;
  286.     }else{
  287.         if (X->max == 0) {
  288.             if (IK < X->min) {
  289.                 X->max = X->min;
  290.                 X->min = IK;
  291.             }
  292.             else if(X->min <= IK) {
  293.                 X->max = IK;
  294.             }else{
  295.                 printf("Error else\n");
  296.             }
  297.         }
  298.         else if ((X->max != 0)&&(doAble)){
  299.             leafIsFull(IK, X);
  300.             NN += INS_PROB;
  301.             (X->height)++;
  302.         }
  303.     }
  304.     return X;
  305. }
  306. void carveThrough(node_t* n) {
  307.     if (isInternal(n)) {
  308.         carveThrough(n->lch);
  309.         survivors.push(n->min);
  310.         if (!(n->max == START_WEIGHT)){ survivors.push(n->max);}
  311.         carveThrough(n->rch);
  312.     }
  313. }
  314.  
  315. node_t* reduce(node_t* n) {
  316.     int depthOfTree = 0, cntrOfNodes = 0;
  317.     carveThrough(n);
  318.  
  319.     int size = survivors.size();
  320.  
  321.     if (!(size != 1)) {
  322.         n = new node_t(survivors.front(), START_WEIGHT,0);
  323.         survivors.pop();
  324.         return n;
  325.     }
  326.     while (cntrOfNodes * INS_PROB < survivors.size()) {
  327.         cntrOfNodes = moveNodes(depthOfTree);
  328.         depthOfTree++;
  329.     }
  330.  
  331.     --depthOfTree;
  332.  
  333.     maxDepth = depthOfTree;
  334.     NN = cntrOfNodes;
  335.     size = survivors.size();
  336.     int tmp_z = size - cntrOfNodes;
  337.     canAddTwo = tmp_z;
  338.  
  339.     n = createNewTree(1);
  340.     R_this++;
  341.  
  342.     return n;
  343. }
  344.  
  345.  
  346. int main(int argc, char *argv[]) {
  347.     if(argc > 2){
  348.         printf("Error arguments");
  349.         return -1;
  350.     }
  351.     //var
  352.     int N = 0, IK = 0, i = 0, result1 = 0, result2 = 0, result3 = 0;
  353.     //WINPAUSE;
  354.     node_t* root = NULL;
  355.     scanf("%d %d", &N, &RCT);
  356.  
  357.     if (N>0) {
  358.         NN = 1;
  359.     }
  360.  
  361.     while(i < N){
  362.  
  363.         cin >> IK;
  364.  
  365.         root = insert(IK, root, 1);
  366.         if (rCur == RCT) {
  367.             rCur = 0;
  368.             root = reduce(root);
  369.         }
  370.         i++;
  371.     }
  372.  
  373.     result1 = NN;
  374.     result2 = root->height;
  375.     result3 = R_this;
  376.     printf("%d %d %d\n", result1, result2, result3);
  377.  
  378.     return 0;
  379. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement