fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Node
  5. {
  6.     public:
  7.  
  8.     int value;
  9.     Node* left;
  10.     Node* right;
  11.     Node* parent;
  12.  
  13.     Node(int value)
  14.     {
  15.         this->value = value;
  16.         this->left = NULL;
  17.         this->right = NULL;
  18.         this->parent = NULL;
  19.     }
  20. };
  21.  
  22. class Binary_Search_Tree
  23. {
  24.     public:
  25.     Node* root = NULL;
  26.  
  27.     void insert_data(int value)
  28.     {
  29.         Node* newnode = new Node(value);
  30.  
  31.         if(!root)
  32.         {
  33.             root = newnode;
  34.             return;
  35.         }
  36.  
  37.         Node* temp = root;
  38.         Node* prev = NULL;
  39.  
  40.         while(temp)
  41.         {
  42.             prev = temp;
  43.  
  44.             if(value < temp->value)
  45.                 temp = temp->left;
  46.             else
  47.                 temp = temp->right;
  48.         }
  49.  
  50.         temp = newnode;
  51.  
  52.         newnode->parent = prev;
  53.  
  54.         if(value > prev->value)
  55.             prev->right = newnode;
  56.         else
  57.             prev->left = newnode;
  58.     }
  59.  
  60.     void inorder(Node* temp)
  61.     {
  62.         if(!temp)
  63.             return;
  64.         inorder(temp->left);
  65.         cout << temp->value << " ";
  66.         inorder(temp->right);
  67.     }
  68.  
  69.     void preorder(Node* temp)
  70.     {
  71.         if(!temp)
  72.             return;
  73.         cout << temp->value << " ";
  74.         preorder(temp->left);
  75.         preorder(temp->right);
  76.     }
  77.  
  78.     void posteorder(Node* temp)
  79.     {
  80.         if(!temp)
  81.             return;
  82.         posteorder(temp->left);
  83.         posteorder(temp->right);
  84.         cout << temp->value << " ";
  85.     }
  86.  
  87.     Node* search_data(int value)
  88.     {
  89.         Node* temp = root;
  90.  
  91.         while(temp)
  92.         {
  93.             if(temp->value == value)
  94.                 return temp;
  95.             else if(temp->value > value)
  96.                 temp = temp->left;
  97.             else
  98.                 temp = temp->right;
  99.         }
  100.  
  101.         return NULL;
  102.     }
  103.  
  104.     Node* max_value(Node* temp)
  105.     {
  106.         if(!temp)
  107.             return NULL;
  108.  
  109.         while(temp->right)
  110.         {
  111.             temp = temp->right;
  112.         }
  113.  
  114.         return temp;
  115.     }
  116.  
  117.     Node* min_value(Node* temp)
  118.     {
  119.         if(!temp)
  120.             return NULL;
  121.  
  122.         while(temp->left)
  123.         {
  124.             temp = temp->left;
  125.         }
  126.  
  127.         return temp;
  128.     }
  129.  
  130.     void delete_node(int value)
  131.     {
  132.         Node* found = search_data(value);
  133.  
  134.         if(!found)
  135.             cout << "Not in the  bst\n";
  136.         else if(!found->left and !found->right)
  137.             delete_case1(found);
  138.         else if(!found->left or !found->right)
  139.             delete_case2(found);
  140.         else
  141.             delete_case3(found);
  142.     }
  143.  
  144.     void delete_case1(Node* temp)
  145.     {
  146.         Node* parent = temp->parent;
  147.  
  148.         if(temp->value > parent->value)
  149.             parent->right = NULL;
  150.         else
  151.             parent->left = NULL;
  152.         delete temp;
  153.     }
  154.  
  155.     void delete_case2(Node* temp)
  156.     {
  157.         Node* parent = temp->parent;
  158.         Node* child = temp->left;
  159.  
  160.         if(!child)
  161.             child = temp->right;
  162.  
  163.         if(temp->value < parent->value)
  164.             parent->left = child;
  165.         else
  166.             parent->right = child;
  167.  
  168.         child->parent = parent;
  169.  
  170.         delete temp;
  171.     }
  172.  
  173.     void delete_case3(Node* temp)
  174.     {
  175.         Node* suc = find_succesor(temp);
  176.         int value = suc->value;
  177.  
  178.         delete_node(suc->value);
  179.         temp->value = value;
  180.     }
  181.  
  182.     Node* find_succesor(Node* temp)
  183.     {
  184.         if(!temp)
  185.             return NULL;
  186.         else if(!temp->right)
  187.             return min_value(temp->right);
  188.         else if(temp->parent)
  189.         {
  190.             Node* cur = temp->parent;
  191.  
  192.             while(cur->value < temp->value)
  193.             {
  194.                 temp = cur;
  195.                 cur = cur->parent;
  196.  
  197.                 if(!cur)
  198.                     return NULL;
  199.             }
  200.  
  201.             return cur;
  202.         }
  203.         else
  204.             return NULL;  
  205.     }
  206.  
  207.     Node* find_predeccessor(Node* temp)
  208.     {
  209.         if(!temp)
  210.             return NULL;
  211.         else if(!temp->left)
  212.             return max_value(temp->left);
  213.         else if(temp->parent)
  214.         {
  215.             Node* cur = temp->parent;
  216.  
  217.             while(cur->value > temp->value)
  218.             {
  219.                 temp = cur;
  220.                 cur = cur->parent;
  221.  
  222.                 if(!cur)
  223.                     return NULL;
  224.             }
  225.  
  226.             return cur;
  227.         }
  228.         else
  229.             return NULL;  
  230.     }
  231. };
  232.  
  233. int main()
  234. {
  235.     ios::sync_with_stdio(false);
  236.     cin.tie(nullptr);
  237.  
  238.     Binary_Search_Tree B;
  239.  
  240.     int n;
  241.     cin >> n;
  242.  
  243.     for(int i = 0; i < n; i++)
  244.     {
  245.         int x;
  246.         cin >> x;
  247.  
  248.         B.insert_data(x);
  249.     }
  250.  
  251.     B.inorder(B.root);
  252.     // cout << endl;
  253.     // B.preorder(B.root);
  254.  
  255.     //Node* a = B.search_data(44);
  256.     //Node* a = B.max_value(B.root);
  257.     // Node* a = B.min_value(B.root);
  258.  
  259.     // if(a)   
  260.     //     cout << a->value << endl;
  261.     // else
  262.     //     cout << "Not Found\n";
  263.  
  264.     cout << endl;
  265.     B.delete_node(17);
  266.     B.delete_node(97);
  267.     B.inorder(B.root);
  268.  
  269.     return 0;
  270. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin 
12
44 17 88 32 65 97 28 54 82 29 76 80
stdout 
17 28 29 32 44 54 65 76 80 82 88 97 
28 29 32 44 54 65 76 80 82 88
https://ideone.com/oJo5vi
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!