DS_Homework_2_2

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

struct Node {
    int value[2] = { -1,-1 };
    Node* childNodes[3] = { nullptr,nullptr,nullptr };
    Node* parent = nullptr;
};

Node* tree;

Node* find(Node* node, const int& value);
void insert(Node* node, const int& value);

int main() {
    string inputLine;
    getline(cin, inputLine);
    stringstream inputStream = stringstream(inputLine);
    int input;
    tree = nullptr;
    while (inputStream >> input) {
        //cout << "###  " << input << "  ###\n";

        Node* location = find(tree, input);
        insert(location, input);

        //vector<Node*> levelNodes = vector<Node*>();
        //levelNodes.push_back(tree);
        //while (levelNodes.size() != 0)
        //{
        //  if (levelNodes.size() != 1) {
        //      cout << "\n";
        //  }
        //  vector<Node*> newLevelNodes = vector<Node*>();
        //  for (int i = 0; i < levelNodes.size(); i++) {
        //      if (levelNodes[i]->value[0] != -1)
        //          cout << levelNodes[i]->value[0];
        //      if (levelNodes[i]->value[1] != -1)
        //          cout << " " << levelNodes[i]->value[1];

        //      if (i != levelNodes.size() - 1)
        //          cout << " / ";
        //      for (int j = 0; j < 3; j++) {
        //          if (levelNodes[i]->childNodes[j] != nullptr) {
        //              newLevelNodes.push_back(levelNodes[i]->childNodes[j]);
        //          }
        //      }
        //  }
        //  levelNodes = newLevelNodes;
        //}
        //cout << "\n--------------------------------\n";

    }
    vector<Node*> levelNodes = vector<Node*>();
    levelNodes.push_back(tree);
    while (levelNodes.size() != 0)
    {
        if (levelNodes.size() != 1) {
            cout << "\n";
        }
        vector<Node*> newLevelNodes = vector<Node*>();
        for (int i = 0; i < levelNodes.size(); i++) {
            if (levelNodes[i]->value[0] != -1)
                cout << levelNodes[i]->value[0];
            if (levelNodes[i]->value[1] != -1)
                cout << " " << levelNodes[i]->value[1];

            if (i != levelNodes.size() - 1)
                cout << " / ";
            for (int j = 0; j < 3; j++) {
                if (levelNodes[i]->childNodes[j] != nullptr) {
                    newLevelNodes.push_back(levelNodes[i]->childNodes[j]);
                }
            }
        }
        levelNodes = newLevelNodes;
    }
}

void merge(Node* node, Node* left, Node* right, const int& value) {
    Node* parent = node->parent;
    //delete node;
    if (parent == nullptr) {
        // Top node, create new one
        tree = new Node();
        tree->value[0] = value;
        tree->childNodes[0] = left;
        tree->childNodes[1] = right;
        left->parent = tree;
        right->parent = tree;
        return;
    }

    if (parent->value[1] == -1) {
        // Parent not full
        left->parent = parent;
        right->parent = parent;
        if (parent->value[0] < value) {
            parent->value[1] = value;
            parent->childNodes[1] = left;
            parent->childNodes[2] = right;
        }
        else {
            parent->value[1] = parent->value[0];
            parent->value[0] = value;
            parent->childNodes[0] = left;
            parent->childNodes[2] = parent->childNodes[1];
            parent->childNodes[1] = right;
        }
    }
    else {
        // Parent full, choose which value to promote
        Node* parentLeft = new Node();
        Node* parentRight = new Node();
        parentLeft->parent = parent->parent;
        parentRight->parent = parent->parent;
        int promoting = -1;

        if (value < parent->value[0]) {
            parentLeft->value[0] = value;
            parentLeft->childNodes[0] = left;
            parentLeft->childNodes[1] = right;

            parentRight->value[0] = parent->value[1];
            parentRight->childNodes[0] = parent->childNodes[1];
            parentRight->childNodes[1] = parent->childNodes[2];

            left->parent = parentLeft;
            right->parent = parentLeft;
            parent->childNodes[1]->parent = parentRight;
            parent->childNodes[2]->parent = parentRight;

            promoting = parent->value[0];
        }
        else if (value > parent->value[1]) {
            parentLeft->value[0] = parent->value[0];
            parentLeft->childNodes[0] = parent->childNodes[0];
            parentLeft->childNodes[1] = parent->childNodes[1];

            parentRight->value[0] = value;
            parentRight->childNodes[0] = left;
            parentRight->childNodes[1] = right;

            left->parent = parentRight;
            right->parent = parentRight;
            parent->childNodes[0]->parent = parentLeft;
            parent->childNodes[1]->parent = parentLeft;

            promoting = parent->value[1];
        }
        else {
            parentLeft->value[0] = parent->value[0];
            parentLeft->childNodes[0] = parent->childNodes[0];
            parentLeft->childNodes[1] = left;

            parentRight->value[0] = parent->value[1];
            parentRight->childNodes[0] = right;
            parentRight->childNodes[1] = parent->childNodes[2];

            left->parent = parentLeft;
            right->parent = parentRight;
            parent->childNodes[0]->parent = parentLeft;
            parent->childNodes[2]->parent = parentRight;

            promoting = value;
        }


        merge(parent, parentLeft, parentRight, promoting);
    }

}

void split(Node* node, const int& value) {
    Node* left = new Node();
    Node* right = new Node();
    left->parent = node->parent;
    right->parent = node->parent;
    int promoting = -1;
    if (node->value[0] > value) {
        left->value[0] = value;
        right->value[0] = node->value[1];
        promoting = node->value[0];
    }
    else if (node->value[0]< value && node->value[1] > value) {
        left->value[0] = node->value[0];
        right->value[0] = node->value[1];
        promoting = value;
    }
    else if (node->value[1] < value) {
        left->value[0] = node->value[0];
        right->value[0] = value;
        promoting = node->value[1];
    }
    merge(node, left, right, promoting);
}

void addKey(Node* node, const int& value) {
    if (node->value[0] < value) {
        node->value[1] = value;
    }
    else {
        node->value[1] = node->value[0];
        node->value[0] = value;
    }
}

void insert(Node* node, const int& value) {
    if (node == nullptr) {
        tree = new Node();
        tree->value[0] = value;
    }
    else if (node->value[0] != -1 && node->value[1] != -1) {
        split(node, value);
    }
    else if (node->value[1] == -1) {
        addKey(node, value);
    }
}

Node* find(Node* node, const int& value) {
    if (node == nullptr) {
        return nullptr;
    }
    if (node->value[0] > value && node->childNodes[0] != nullptr) {
        return find(node->childNodes[0], value);
    }
    else if (node->value[0] < value && (node->value[1] > value || node->value[1] == -1) && node->childNodes[1] != nullptr) {
        return find(node->childNodes[1], value);
    }
    else if (node->value[1] < value && node->childNodes[2] != nullptr) {
        return find(node->childNodes[2], value);
    }
    return node;
}