Advertisement
Guest User

Untitled

a guest
Feb 26th, 2017
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.05 KB | None | 0 0
  1. #include <list>
  2. #include <functional>
  3.  
  4. using namespace std;
  5.  
  6. #ifdef ONLINE_JUDGE
  7.  
  8. #include <fstream>
  9.  
  10. ifstream cin("input.txt");
  11. ofstream cout("output.txt");
  12. #else
  13. #include <iostream>
  14. #endif
  15.  
  16. class Node {
  17. private:
  18.     void remove_LeftSon(Node* node) {
  19.         node->left->parent = node->parent;
  20.         if (node->parent != nullptr) {
  21.             if (node->parent->right == node)
  22.                 node->parent->right = node->left;
  23.             else
  24.                 node->parent->left = node->left;
  25.         }
  26.         delete node;
  27.     }
  28.  
  29.     void remove_Leaf(Node* node) {
  30.         if (node->parent != nullptr) {
  31.             if (node->parent->right == node)
  32.                 node->parent->right = nullptr;
  33.             else
  34.                 node->parent->left = nullptr;
  35.         }
  36.         delete node;
  37.     }
  38.  
  39.     void remove_RightSon(Node* node) {
  40.         node->right->parent = node->parent;
  41.         if (node->parent != nullptr) {
  42.             if (node->parent->right == node)
  43.                 node->parent->right = node->right;
  44.             else
  45.                 node->parent->left = node->right;
  46.         }
  47.         delete node;
  48.     }
  49.  
  50.     void remove_BothSons(Node* node) {
  51.         Node* nextNode = node->right;
  52.         while (nextNode->left != nullptr)
  53.             nextNode = nextNode->left;
  54.         swap(node->key, nextNode->key);
  55.         nextNode->removeRightWay();
  56.     }
  57.  
  58. public:
  59.     long long key, treeSize;
  60.     bool flag;
  61.     Node* left, *right, *parent;
  62.  
  63.     Node(long long value = 0) {
  64.         key = value;
  65.         left = right = parent = nullptr;
  66.         flag = false;
  67.         treeSize = 0;
  68.     }
  69.  
  70.     void removeRightWay() {
  71.         if (this->left != nullptr && this->right != nullptr) {
  72.             remove_BothSons(this);
  73.         }
  74.         else if (this->left != nullptr) {
  75.             remove_LeftSon(this);
  76.         }
  77.         else if (this->right != nullptr) {
  78.             remove_RightSon(this);
  79.         }
  80.         else {
  81.             remove_Leaf(this);
  82.         }
  83.     }
  84. };
  85.  
  86. class BinarySearchTree {
  87. private:
  88.     Node* root;
  89.     function<void(Node*)> strategy;
  90.  
  91.     Node* find(long long value) const {
  92.         Node* ans = root;
  93.         while (ans != nullptr) {
  94.             if (ans->key == value)
  95.                 return ans;
  96.             else if (value < ans->key)
  97.                 ans = ans->left;
  98.             else
  99.                 ans = ans->right;
  100.         }
  101.         return ans;
  102.     }
  103.  
  104.     void rootLeftRightTraversalNodes(Node* node) {
  105.         if (node == nullptr)
  106.             return;
  107.         if (strategy)
  108.             strategy(node);
  109.         rootLeftRightTraversalNodes(node->left);
  110.         rootLeftRightTraversalNodes(node->right);
  111.     }
  112.  
  113.     void leftRightRootTraversalNodes(Node* node) {
  114.         if (node == nullptr)
  115.             return;
  116.         leftRightRootTraversalNodes(node->left);
  117.         leftRightRootTraversalNodes(node->right);
  118.         if (strategy)
  119.             strategy(node);
  120.     }
  121.  
  122. public:
  123.  
  124.     Node* getRoot() const {
  125.         return root;
  126.     }
  127.  
  128.     BinarySearchTree() {
  129.         root = nullptr;
  130.     }
  131.  
  132.     void add(long long value) {
  133.         Node** curr = &root, ** prev = nullptr;
  134.         while (*curr) {
  135.             prev = curr;
  136.             if (value < (*curr)->key)
  137.                 curr = &(*curr)->left;
  138.             else if (value >(*curr)->key)
  139.                 curr = &(*curr)->right;
  140.             else
  141.                 return;
  142.         }
  143.         *curr = new Node(value);
  144.         if (prev != nullptr)
  145.             (*curr)->parent = *prev;
  146.     }
  147.  
  148.     void removeRightWay(long long value) {
  149.         Node* node = find(value);
  150.         if (node == nullptr)
  151.             return;
  152.  
  153.         if (node == root) {
  154.             Node* temp = new Node();
  155.             temp->left = root;
  156.             root->parent = temp;
  157.             node->removeRightWay();
  158.             root = temp->left;
  159.             if (root != nullptr)
  160.                 root->parent = nullptr;
  161.             delete temp;
  162.         }
  163.         else
  164.             node->removeRightWay();
  165.     }
  166.  
  167.     void rootLeftRightTraversal() {
  168.         rootLeftRightTraversalNodes(root);
  169.     }
  170.  
  171.     void leftRightRootTraversal() {
  172.         leftRightRootTraversalNodes(root);
  173.     }
  174.  
  175.     bool hasKey(long long value) const {
  176.         return find(value) != nullptr;
  177.     }
  178.  
  179.     void setStrategy(function<void(Node*)> func) {
  180.         strategy = func;
  181.     }
  182. };
  183.  
  184. int main() {
  185.     ios_base::sync_with_stdio(false);
  186.     cin.tie(0);
  187.  
  188.     long long key;
  189.     BinarySearchTree bst;
  190.     while (cin >> key) {
  191.         bst.add(key);
  192.     }
  193.  
  194.     auto calcSubtreeSize = [](Node* node) {
  195.         node->treeSize = 1;
  196.         if (node->left != nullptr && node->right != nullptr)
  197.             node->treeSize += node->left->treeSize + node->right->treeSize;
  198.         else if (node->left != nullptr)
  199.             node->treeSize += node->left->treeSize;
  200.         else if (node->right != nullptr)
  201.             node->treeSize += node->right->treeSize;
  202.     };
  203.     bst.setStrategy(calcSubtreeSize);
  204.     bst.leftRightRootTraversal();
  205.  
  206.     pair <long long, long long> targetNode = make_pair(0,LLONG_MIN);
  207.     auto findTargetNode = [&targetNode](Node* node) {
  208.         long long diff;
  209.         if (node->left != nullptr && node->right != nullptr)
  210.             diff = abs(node->left->treeSize - node->right->treeSize);
  211.         else if (node->left != nullptr)
  212.             diff = node->left->treeSize;
  213.         else if (node->right != nullptr)
  214.             diff = node->right->treeSize;
  215.         else
  216.             diff = 0;
  217.  
  218.         if (diff > targetNode.first)
  219.             targetNode = make_pair(diff, node->key);
  220.         else if (diff = targetNode.first && node->key > targetNode.second)
  221.             targetNode = make_pair(diff, node->key);
  222.     };
  223.     bst.setStrategy(findTargetNode);
  224.     bst.leftRightRootTraversal();
  225.     bst.removeRightWay(targetNode.second);
  226.  
  227.     list<Node> traverseNodes;
  228.     auto pushNodesToList = [&traverseNodes](Node* node) { traverseNodes.push_back(*node); };
  229.     bst.setStrategy(pushNodesToList);
  230.     bst.rootLeftRightTraversal();
  231.     for (auto node : traverseNodes)
  232.         cout << node.key << " " << node.treeSize << "\n";
  233.  
  234.     return 0;
  235. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement