JellyKuo

DS_Homework_2_2

Nov 29th, 2020
376
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <sstream>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. struct Node {
  9.     int value[2] = { -1,-1 };
  10.     Node* childNodes[3] = { nullptr,nullptr,nullptr };
  11.     Node* parent = nullptr;
  12. };
  13.  
  14. Node* tree;
  15.  
  16. Node* find(Node* node, const int& value);
  17. void insert(Node* node, const int& value);
  18.  
  19. int main() {
  20.     string inputLine;
  21.     getline(cin, inputLine);
  22.     stringstream inputStream = stringstream(inputLine);
  23.     int input;
  24.     tree = nullptr;
  25.     while (inputStream >> input) {
  26.         //cout << "###  " << input << "  ###\n";
  27.  
  28.         Node* location = find(tree, input);
  29.         insert(location, input);
  30.  
  31.         //vector<Node*> levelNodes = vector<Node*>();
  32.         //levelNodes.push_back(tree);
  33.         //while (levelNodes.size() != 0)
  34.         //{
  35.         //  if (levelNodes.size() != 1) {
  36.         //      cout << "\n";
  37.         //  }
  38.         //  vector<Node*> newLevelNodes = vector<Node*>();
  39.         //  for (int i = 0; i < levelNodes.size(); i++) {
  40.         //      if (levelNodes[i]->value[0] != -1)
  41.         //          cout << levelNodes[i]->value[0];
  42.         //      if (levelNodes[i]->value[1] != -1)
  43.         //          cout << " " << levelNodes[i]->value[1];
  44.  
  45.         //      if (i != levelNodes.size() - 1)
  46.         //          cout << " / ";
  47.         //      for (int j = 0; j < 3; j++) {
  48.         //          if (levelNodes[i]->childNodes[j] != nullptr) {
  49.         //              newLevelNodes.push_back(levelNodes[i]->childNodes[j]);
  50.         //          }
  51.         //      }
  52.         //  }
  53.         //  levelNodes = newLevelNodes;
  54.         //}
  55.         //cout << "\n--------------------------------\n";
  56.  
  57.     }
  58.     vector<Node*> levelNodes = vector<Node*>();
  59.     levelNodes.push_back(tree);
  60.     while (levelNodes.size() != 0)
  61.     {
  62.         if (levelNodes.size() != 1) {
  63.             cout << "\n";
  64.         }
  65.         vector<Node*> newLevelNodes = vector<Node*>();
  66.         for (int i = 0; i < levelNodes.size(); i++) {
  67.             if (levelNodes[i]->value[0] != -1)
  68.                 cout << levelNodes[i]->value[0];
  69.             if (levelNodes[i]->value[1] != -1)
  70.                 cout << " " << levelNodes[i]->value[1];
  71.  
  72.             if (i != levelNodes.size() - 1)
  73.                 cout << " / ";
  74.             for (int j = 0; j < 3; j++) {
  75.                 if (levelNodes[i]->childNodes[j] != nullptr) {
  76.                     newLevelNodes.push_back(levelNodes[i]->childNodes[j]);
  77.                 }
  78.             }
  79.         }
  80.         levelNodes = newLevelNodes;
  81.     }
  82. }
  83.  
  84. void merge(Node* node, Node* left, Node* right, const int& value) {
  85.     Node* parent = node->parent;
  86.     //delete node;
  87.     if (parent == nullptr) {
  88.         // Top node, create new one
  89.         tree = new Node();
  90.         tree->value[0] = value;
  91.         tree->childNodes[0] = left;
  92.         tree->childNodes[1] = right;
  93.         left->parent = tree;
  94.         right->parent = tree;
  95.         return;
  96.     }
  97.  
  98.     if (parent->value[1] == -1) {
  99.         // Parent not full
  100.         left->parent = parent;
  101.         right->parent = parent;
  102.         if (parent->value[0] < value) {
  103.             parent->value[1] = value;
  104.             parent->childNodes[1] = left;
  105.             parent->childNodes[2] = right;
  106.         }
  107.         else {
  108.             parent->value[1] = parent->value[0];
  109.             parent->value[0] = value;
  110.             parent->childNodes[0] = left;
  111.             parent->childNodes[2] = parent->childNodes[1];
  112.             parent->childNodes[1] = right;
  113.         }
  114.     }
  115.     else {
  116.         // Parent full, choose which value to promote
  117.         Node* parentLeft = new Node();
  118.         Node* parentRight = new Node();
  119.         parentLeft->parent = parent->parent;
  120.         parentRight->parent = parent->parent;
  121.         int promoting = -1;
  122.  
  123.         if (value < parent->value[0]) {
  124.             parentLeft->value[0] = value;
  125.             parentLeft->childNodes[0] = left;
  126.             parentLeft->childNodes[1] = right;
  127.  
  128.             parentRight->value[0] = parent->value[1];
  129.             parentRight->childNodes[0] = parent->childNodes[1];
  130.             parentRight->childNodes[1] = parent->childNodes[2];
  131.  
  132.             left->parent = parentLeft;
  133.             right->parent = parentLeft;
  134.             parent->childNodes[1]->parent = parentRight;
  135.             parent->childNodes[2]->parent = parentRight;
  136.  
  137.             promoting = parent->value[0];
  138.         }
  139.         else if (value > parent->value[1]) {
  140.             parentLeft->value[0] = parent->value[0];
  141.             parentLeft->childNodes[0] = parent->childNodes[0];
  142.             parentLeft->childNodes[1] = parent->childNodes[1];
  143.  
  144.             parentRight->value[0] = value;
  145.             parentRight->childNodes[0] = left;
  146.             parentRight->childNodes[1] = right;
  147.  
  148.             left->parent = parentRight;
  149.             right->parent = parentRight;
  150.             parent->childNodes[0]->parent = parentLeft;
  151.             parent->childNodes[1]->parent = parentLeft;
  152.  
  153.             promoting = parent->value[1];
  154.         }
  155.         else {
  156.             parentLeft->value[0] = parent->value[0];
  157.             parentLeft->childNodes[0] = parent->childNodes[0];
  158.             parentLeft->childNodes[1] = left;
  159.  
  160.             parentRight->value[0] = parent->value[1];
  161.             parentRight->childNodes[0] = right;
  162.             parentRight->childNodes[1] = parent->childNodes[2];
  163.  
  164.             left->parent = parentLeft;
  165.             right->parent = parentRight;
  166.             parent->childNodes[0]->parent = parentLeft;
  167.             parent->childNodes[2]->parent = parentRight;
  168.  
  169.             promoting = value;
  170.         }
  171.  
  172.  
  173.         merge(parent, parentLeft, parentRight, promoting);
  174.     }
  175.  
  176. }
  177.  
  178. void split(Node* node, const int& value) {
  179.     Node* left = new Node();
  180.     Node* right = new Node();
  181.     left->parent = node->parent;
  182.     right->parent = node->parent;
  183.     int promoting = -1;
  184.     if (node->value[0] > value) {
  185.         left->value[0] = value;
  186.         right->value[0] = node->value[1];
  187.         promoting = node->value[0];
  188.     }
  189.     else if (node->value[0]< value && node->value[1] > value) {
  190.         left->value[0] = node->value[0];
  191.         right->value[0] = node->value[1];
  192.         promoting = value;
  193.     }
  194.     else if (node->value[1] < value) {
  195.         left->value[0] = node->value[0];
  196.         right->value[0] = value;
  197.         promoting = node->value[1];
  198.     }
  199.     merge(node, left, right, promoting);
  200. }
  201.  
  202. void addKey(Node* node, const int& value) {
  203.     if (node->value[0] < value) {
  204.         node->value[1] = value;
  205.     }
  206.     else {
  207.         node->value[1] = node->value[0];
  208.         node->value[0] = value;
  209.     }
  210. }
  211.  
  212. void insert(Node* node, const int& value) {
  213.     if (node == nullptr) {
  214.         tree = new Node();
  215.         tree->value[0] = value;
  216.     }
  217.     else if (node->value[0] != -1 && node->value[1] != -1) {
  218.         split(node, value);
  219.     }
  220.     else if (node->value[1] == -1) {
  221.         addKey(node, value);
  222.     }
  223. }
  224.  
  225. Node* find(Node* node, const int& value) {
  226.     if (node == nullptr) {
  227.         return nullptr;
  228.     }
  229.     if (node->value[0] > value && node->childNodes[0] != nullptr) {
  230.         return find(node->childNodes[0], value);
  231.     }
  232.     else if (node->value[0] < value && (node->value[1] > value || node->value[1] == -1) && node->childNodes[1] != nullptr) {
  233.         return find(node->childNodes[1], value);
  234.     }
  235.     else if (node->value[1] < value && node->childNodes[2] != nullptr) {
  236.         return find(node->childNodes[2], value);
  237.     }
  238.     return node;
  239. }
  240.  
RAW Paste Data