Ledger Nano X - The secure hardware wallet
SHARE
TWEET

algorytmika 2

a guest Apr 6th, 2020 125 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3. #include <array>
  4.  
  5. using namespace std;
  6.  
  7. struct Node {
  8.     Node* parent;
  9.     Node* left_child;
  10.     Node* right_child;
  11.     int v;
  12.     int bf;
  13.     int h;
  14. };
  15.  
  16. void nodeHeight(Node*&node) {
  17.     if (node) {
  18.         int l_c = 0;
  19.         int r_c = 0;
  20.         if(node->left_child) {
  21.             l_c = node->left_child->h;
  22.         }
  23.         if (node->right_child) {
  24.             r_c = node->right_child->h;
  25.         }
  26.         node->bf = abs(l_c - r_c);
  27.         nodeHeight(node->left_child);
  28.         nodeHeight(node->right_child);
  29.     }
  30. }
  31.  
  32. int getHeight(Node* &node) {
  33.     if (!node) {
  34.         return 0;
  35.     }
  36.     else {
  37.         int left_h = getHeight(node->left_child);
  38.         int right_h = getHeight(node->right_child);
  39.         if (right_h > left_h) {
  40.             node->h = right_h + 1;
  41.         }
  42.         else {
  43.             node->h = left_h + 1;
  44.         }
  45.     }
  46. }
  47.  
  48. void printPRE_ORDER(Node* node) {
  49.     if (node) {
  50.         cout << node->v << ":" <<"Bf: "<< node->bf << " " << "My height: " << node->h << endl;
  51.         printPRE_ORDER(node->left_child);
  52.         printPRE_ORDER(node->right_child);
  53.     }
  54. }
  55.  
  56. void printIN_ORDER(Node* node) {
  57.     if (node) {
  58.         printIN_ORDER(node->left_child);
  59.         cout << node->v << ":" << node->bf << " ";
  60.         printIN_ORDER(node->right_child);
  61.     }
  62. }
  63.  
  64. void del_node_postorder(Node*&node) {
  65.     if (node->left_child) {
  66.         del_node_postorder(node->left_child);
  67.     }
  68.     if (node->right_child) {
  69.         del_node_postorder(node->right_child);
  70.     }
  71.     delete node;
  72. }
  73.  
  74. Node* deleteNode(Node*&node, int value) {
  75.     Node* root = node;
  76.     while (node) {
  77.         if (value > node->v) {
  78.             node = node->right_child;
  79.         }
  80.         else if (value < node->v) {
  81.             node = node->left_child;
  82.         }
  83.         else {
  84.             break;
  85.         }
  86.     }
  87.     // sam liść
  88.     if (node->left_child == NULL && node->right_child == NULL) {
  89.         if (node->parent->left_child !=NULL && node->parent->left_child->v == node->v) {
  90.             node->parent->left_child = NULL;
  91.         }
  92.         else {
  93.             node->parent->right_child = NULL;
  94.         }
  95.         delete node;
  96.     }
  97.     // istnieje lewe dziecko
  98.     else if (node->left_child != NULL && node->right_child == NULL) {
  99.         //którym dzieckiem jest node względem swojego rodzica
  100.         if (node->parent->left_child != NULL && node->parent->left_child->v == node->v) {
  101.             node->parent->left_child = node->left_child;
  102.             node->left_child->parent = node->parent;
  103.         }
  104.         else {
  105.             node->parent->right_child = node->left_child;
  106.             node->left_child->parent = node->parent;
  107.         }
  108.         delete node;
  109.     }
  110.     //istnieje prawe dziecko
  111.     else if (node->left_child == NULL && node->right_child != NULL) {
  112.         //którym dzieckiem jest node względem swojego rodzica
  113.         if (node->parent->left_child != NULL && node->parent->left_child->v == node->v) {
  114.             node->parent->left_child = node->right_child;
  115.             node->right_child->parent = node->parent;
  116.         }
  117.         else {
  118.             node->parent->right_child = node->right_child;
  119.             node->right_child->parent = node->parent;
  120.         }
  121.         delete node;
  122.     }
  123.     //posiada dwoje dziecki
  124.    
  125.     else {
  126.         Node* tmp = node;
  127.         node = node->right_child;
  128.         while (node->left_child) {
  129.             node = node->left_child;
  130.         }
  131.         tmp->v = node->v;
  132.         //TU Kopiuje
  133.         // sam liść
  134.         if (node->left_child == NULL && node->right_child == NULL) {
  135.             if (node->parent->left_child != NULL && node->parent->left_child->v == node->v) {
  136.                 node->parent->left_child = NULL;
  137.             }
  138.             else {
  139.                 node->parent->right_child = NULL;
  140.             }
  141.             delete node;
  142.         }
  143.         // istnieje lewe dziecko
  144.         else if (node->left_child != NULL && node->right_child == NULL) {
  145.             //którym dzieckiem jest node względem swojego rodzica
  146.             if (node->parent->left_child != NULL && node->parent->left_child->v == node->v) {
  147.                 node->parent->left_child = node->left_child;
  148.                 node->left_child->parent = node->parent;
  149.             }
  150.             else {
  151.                 node->parent->right_child = node->left_child;
  152.                 node->left_child->parent = node->parent;
  153.             }
  154.             delete node;
  155.         }
  156.         //istnieje prawe dziecko
  157.         else if (node->left_child == NULL && node->right_child != NULL) {
  158.             //którym dzieckiem jest node względem swojego rodzica
  159.             if (node->parent->left_child != NULL && node->parent->left_child->v == node->v) {
  160.                 node->parent->left_child = node->right_child;
  161.                 node->right_child->parent = node->parent;
  162.             }
  163.             else {
  164.                 node->parent->right_child = node->right_child;
  165.                 node->right_child->parent = node->parent;
  166.             }
  167.             delete node;
  168.         }
  169.     }
  170.  
  171.     return root;
  172. }
  173.  
  174. Node* bts_search(Node* root) {
  175.     if (root && root->bf <= 1) {
  176.         bts_search(root->left_child);
  177.         bts_search(root->right_child);
  178.     }
  179.     else {
  180.         return root;
  181.     }
  182. }
  183. bool isBalanced(Node* root) {
  184.     if (root && root->bf <= 1) {
  185.         bts_search(root->left_child);
  186.         bts_search(root->right_child);
  187.     }
  188.     else if(root && root->bf > 1){
  189.         return false;
  190.     }
  191. }
  192.  
  193. void findMax(Node* node, int &max) {
  194.     if (node) {
  195.         max = node->v;
  196.         cout << "Element sciezki: " << max << endl;
  197.         findMax(node->right_child, max);    
  198.     }
  199. }
  200. void findMin(Node* node, int& min) {
  201.     if (node) {
  202.         min = node->v;
  203.         cout << "Element sciezki: " << min << endl;
  204.         findMin(node->left_child, min);
  205.     }
  206. }
  207.  
  208. void insert(Node* &root, int value) {
  209.     Node *node, *parent;
  210.     node = new Node;
  211.     //setting everything to the default settings.
  212.     node->left_child = NULL;
  213.     node->right_child = NULL;
  214.     node->parent = NULL;
  215.     node->v = value;
  216.     node->bf = 0;
  217.  
  218.     parent = root;
  219.     if(!parent){
  220.         root = node;
  221.     }
  222.     else {
  223.         while (true) {
  224.             //reaching the proper destination of the new node
  225.             if (value <= parent->v) {
  226.                 if (!parent->left_child) {
  227.                     parent->left_child = node;
  228.                     break;
  229.                 }
  230.                 parent = parent->left_child;
  231.             }
  232.             else {
  233.                 if (!parent->right_child) {
  234.                     parent->right_child = node;
  235.                     break;
  236.                 }
  237.                 parent = parent->right_child;
  238.             }
  239.         }
  240.        
  241.     }
  242.     //after reaching the destination setting the parent for a node
  243.     node->parent = parent;
  244. }
  245.  
  246. Node* balanceTree(Node*& node) {
  247.     Node* root = node;
  248.     Node* tmp = NULL;
  249.     do {
  250.         tmp = bts_search(node);
  251.         if (tmp) {
  252.             int value, value_child;
  253.             value = tmp->v;
  254.             Node* tmp_1;
  255.             if (tmp->left_child && tmp->right_child) {
  256.                 cout << "Mam oba dzieci" << endl;
  257.                 if (tmp->left_child->h > tmp->right_child->h) {
  258.                     tmp_1 = tmp->left_child;
  259.                     while (tmp_1->right_child) {
  260.                         tmp_1 = tmp_1->right_child;
  261.                     }
  262.                     value_child = tmp_1->v;
  263.                     root = deleteNode(root, value_child);
  264.                     tmp->v = value_child;
  265.                     insert(root, value);
  266.                 }
  267.                 else {
  268.                     tmp_1 = tmp->right_child;
  269.                     while (tmp_1->left_child) {
  270.                         tmp_1 = tmp_1->left_child;
  271.                     }
  272.                     value_child = tmp_1->v;
  273.                     root = deleteNode(root, value_child);
  274.                     tmp->v = value_child;
  275.                     insert(root, value);
  276.                 }
  277.             }
  278.             else if (tmp->left_child && !tmp->right_child) {
  279.                 cout << "Mam lewe dziecko" << endl;
  280.                 tmp_1 = tmp->left_child;
  281.                 while (tmp_1->right_child) {
  282.                     tmp_1 = tmp_1->right_child;
  283.                 }
  284.                 value_child = tmp_1->v;
  285.                 root = deleteNode(root, value_child);
  286.                 tmp->v = value_child;
  287.                 insert(root, value);
  288.             }
  289.             else if (!tmp->left_child && tmp->right_child) {
  290.                 cout << "Mam prawe dziecko" << endl;
  291.                 tmp_1 = tmp->right_child;
  292.                 while (tmp_1->left_child) {
  293.                     tmp_1 = tmp_1->left_child;
  294.                 }
  295.                 value_child = tmp_1->v;
  296.                 root = deleteNode(root, value_child);
  297.                 tmp->v = value_child;
  298.                 insert(root, value);
  299.             }
  300.             else {
  301.                 cout << "Bez dzieci" << endl;
  302.             }
  303.             getHeight(root);
  304.             nodeHeight(root);
  305.         }
  306.     } while (tmp != NULL);
  307.  
  308.  
  309.     return root;
  310. }
  311.  
  312. void findElement(int* tab, int first, int last, Node*& root) {
  313.     int index = (last + first) / 2;
  314.     if (last >= first) {
  315.         insert(root, tab[index]);
  316.         findElement(tab, first, index - 1, root);
  317.         findElement(tab, index + 1, last, root);
  318.     }
  319. }
  320. void insert_sort(int* arr, int len) {
  321.     int tmp;
  322.     int j;
  323.     for (int i = 0; i < len - 1; i++) {
  324.         if (arr[i] > arr[i + 1]) {
  325.             tmp = arr[i + 1];
  326.             int j = i;
  327.             while (j >= 0 && arr[j] > tmp) {
  328.                 arr[j + 1] = arr[j];
  329.                 j--;
  330.             }
  331.             arr[j + 1] = tmp;
  332.         }
  333.     }
  334. }
  335.  
  336. int main()
  337. {
  338.     int max_value, min_value;
  339.     int tab[] = {10,3,2,1,6,4,7,20,30,23};
  340.     int n = sizeof(tab) / sizeof(int);
  341.     Node* root = NULL;
  342.     for (int i = 0; i < n; i++) {
  343.         insert(root, tab[i]);
  344.     }
  345.     /*
  346.     //insert_sort(tab, n);
  347.     cout << endl;
  348.     //findElement(tab, 0, n-1, root);
  349.     findMax(root, max_value);
  350.     findMin(root, min_value);
  351.     cout << max_value << " <-MAX\n";
  352.     cout << min_value << " <-MIN\n";
  353.     //findElement1(tab, 0, 8, root);
  354.  
  355.     //printIN_ORDER(root);
  356.     //del_node_postorder(root);
  357.     //nodeHeight(root);
  358.     getHeight(root);
  359.     nodeHeight(root);
  360.     //cout << endl;
  361.  
  362.     Node* tmp = bts_search(root);
  363.     cout << tmp->v << endl;
  364.    
  365.     root = balanceTree(root);
  366.     cout << endl;
  367.     printPRE_ORDER(root);
  368.     */
  369.    
  370. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top