fork download
copy 
  1. #include <iostream>
  2. #include <stack>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. class Node {
  7. public:
  8.     int key;
  9.     Node* left;
  10.     Node* right;
  11.     int height;
  12.     int bf; // Balance Factor
  13.  
  14.     Node(int key) {
  15.         this->key = key;
  16.         this->left = nullptr;
  17.         this->right = nullptr;
  18.         this->height = 1;
  19.         this->bf = 0;
  20.     }
  21. };
  22.  
  23. Node* getAVLNode(int key) {
  24.     return new Node(key);
  25. }
  26.  
  27. int height(Node* T) {
  28.     return T ? T->height : 0;
  29. }
  30.  
  31. Node* rotateLL(Node* x) {
  32.     Node* y = x->left;
  33.     x->left = y->right;
  34.     y->right = x;
  35.  
  36.     x->height = 1 + max(height(x->left), height(x->right));
  37.     y->height = 1 + max(height(y->left), height(y->right));
  38.  
  39.     x->bf = height(x->left) - height(x->right);
  40.     y->bf = height(y->left) - height(y->right);
  41.  
  42.     return y;
  43. }
  44.  
  45. Node* rotateRR(Node* x) {
  46.     Node* y = x->right;
  47.     x->right = y->left;
  48.     y->left = x;
  49.  
  50.     x->height = 1 + max(height(x->left), height(x->right));
  51.     y->height = 1 + max(height(y->left), height(y->right));
  52.  
  53.     x->bf = height(x->left) - height(x->right);
  54.     y->bf = height(y->left) - height(y->right);
  55.  
  56.     return y;
  57. }
  58.  
  59. Node* rotateLR(Node* x) {
  60.     x->left = rotateRR(x->left);
  61.     return rotateLL(x);
  62. }
  63.  
  64. Node* rotateRL(Node* x) {
  65.     x->right = rotateLL(x->right);
  66.     return rotateRR(x);
  67. }
  68.  
  69. bool insertAVL(Node*& T, int newKey) {
  70.     Node* p = T;
  71.     Node* q = nullptr;
  72.     stack<Node*> nodeStack;
  73.  
  74.     // Find position to insert newKey while storing parent nodes on stack
  75.     while (p != nullptr) {
  76.         if (newKey == p->key) {
  77.             return false; // Avoid inserting duplicates
  78.         }
  79.  
  80.         q = p;
  81.         nodeStack.push(q);
  82.  
  83.         if (newKey < p->key) {
  84.             p = p->left;
  85.         } else {
  86.             p = p->right;
  87.         }
  88.     }
  89.  
  90.     // Create new node
  91.     Node* y = getAVLNode(newKey);
  92.  
  93.     // Insert y as a child of q
  94.     if (T == nullptr) {
  95.         T = y;
  96.     } else if (newKey < q->key) {
  97.         q->left = y;
  98.     } else {
  99.         q->right = y;
  100.     }
  101.  
  102.     // Update height and balancing factor while popping parent nodes from stack
  103.     Node* x = nullptr;
  104.     Node* f = nullptr;
  105.     while (!nodeStack.empty()) {
  106.         q = nodeStack.top();
  107.         nodeStack.pop();
  108.         q->height = 1 + max(height(q->left), height(q->right));
  109.         q->bf = height(q->left) - height(q->right);
  110.  
  111.         if (q->bf > 1 || q->bf < -1) {
  112.             if (x == nullptr) {
  113.                 x = q;
  114.                 f = nodeStack.empty() ? nullptr : nodeStack.top();
  115.             }
  116.         }
  117.     }
  118.  
  119.     // Rebalance the tree
  120.     if (x != nullptr) {
  121.         if (x->bf > 1) {
  122.             if (x->left->bf >= 0) {
  123.                 x = rotateLL(x);
  124.             } else {
  125.                 x = rotateLR(x);
  126.             }
  127.         } else if (x->bf < -1) {
  128.             if (x->right->bf <= 0) {
  129.                 x = rotateRR(x);
  130.             } else {
  131.                 x = rotateRL(x);
  132.             }
  133.         }
  134.         if (f == nullptr) {
  135.             T = x;
  136.         } else if (f->left == x) {
  137.             f->left = x;
  138.         } else {
  139.             f->right = x;
  140.         }
  141.     }
  142.  
  143.     return true;
  144. }
  145.  
  146. bool deleteAVL(Node*& T, int deleteKey) {
  147.     Node* p = T;
  148.     Node* q = nullptr;
  149.     stack<Node*> nodeStack;
  150.  
  151.     // Perform standard BST deletion
  152.     while (p != nullptr && deleteKey != p->key) {
  153.         q = p;
  154.         nodeStack.push(q);
  155.         if (deleteKey < p->key) {
  156.             p = p->left;
  157.         } else {
  158.             p = p->right;
  159.         }
  160.     }
  161.  
  162.     if (p == nullptr) {
  163.         return false; // deleteKey was not found
  164.     }
  165.  
  166.     // Case 1: Node has two children
  167.     if (p->left != nullptr && p->right != nullptr) {
  168.         nodeStack.push(p);
  169.         Node* tempNode = p;
  170.         if (height(p->left) < height(p->right)) {
  171.             p = p->right;
  172.             while (p->left != nullptr) {
  173.                 nodeStack.push(p);
  174.                 p = p->left;
  175.             }
  176.         } else {
  177.             p = p->left;
  178.             while (p->right != nullptr) {
  179.                 nodeStack.push(p);
  180.                 p = p->right;
  181.             }
  182.         }
  183.         tempNode->key = p->key;
  184.         q = nodeStack.top();
  185.         nodeStack.pop();
  186.     }
  187.  
  188.     // Case 2: Node has 0 or 1 child
  189.     if (p->left == nullptr && p->right == nullptr) {
  190.         if (q == nullptr) {
  191.             T = nullptr;
  192.         } else if (q->left == p) {
  193.             q->left = nullptr;
  194.         } else {
  195.             q->right = nullptr;
  196.         }
  197.     } else {
  198.         Node* child = (p->left != nullptr) ? p->left : p->right;
  199.         if (q == nullptr) {
  200.             T = child;
  201.         } else if (q->left == p) {
  202.             q->left = child;
  203.         } else {
  204.             q->right = child;
  205.         }
  206.     }
  207.  
  208.     delete p;
  209.  
  210.     // Update height and balancing factor while popping parent nodes from stack
  211.     Node* x = nullptr;
  212.     Node* f = nullptr;
  213.     while (!nodeStack.empty()) {
  214.         q = nodeStack.top();
  215.         nodeStack.pop();
  216.         q->height = 1 + max(height(q->left), height(q->right));
  217.         q->bf = height(q->left) - height(q->right);
  218.  
  219.         if (q->bf > 1 || q->bf < -1) {
  220.             x = q;
  221.             f = nodeStack.empty() ? nullptr : nodeStack.top();
  222.  
  223.             // Rebalance the tree
  224.             if (x->bf > 1) {
  225.                 if (x->left->bf >= 0) {
  226.                     x = rotateLL(x);
  227.                 } else {
  228.                     x = rotateLR(x);
  229.                 }
  230.             } else if (x->bf < -1) {
  231.                 if (x->right->bf <= 0) {
  232.                     x = rotateRR(x);
  233.                 } else {
  234.                     x = rotateRL(x);
  235.                 }
  236.             }
  237.             if (f == nullptr) {
  238.                 T = x;
  239.             } else if (f->left == x) {
  240.                 f->left = x;
  241.             } else {
  242.                 f->right = x;
  243.             }
  244.         }
  245.     }
  246.  
  247.     return true;
  248. }
  249.  
  250. void inorder(Node* T) {
  251.     if (T == nullptr) {
  252.         return;
  253.     }
  254.  
  255.     cout << "<";
  256.     inorder(T->left);
  257.     cout << " " << T->key << " ";
  258.     inorder(T->right);
  259.     cout << ">";
  260. }
  261.  
  262. void clear(Node* T) {
  263.     if (T == nullptr) {
  264.         return;
  265.     }
  266.     clear(T->left);
  267.     clear(T->right);
  268.     delete T;
  269. }
  270.  
  271. int main() {
  272.     Node* root = nullptr;
  273.     char operation;
  274.     int key;
  275.  
  276.     while (cin >> operation >> key) {
  277.         bool success = false;
  278.         if (operation == 'i') {
  279.             success = insertAVL(root, key);
  280.         } else if (operation == 'd') {
  281.             success = deleteAVL(root, key);
  282.         }
  283.  
  284.         if (success) {
  285.             inorder(root);
  286.             cout << endl;
  287.         }
  288.     }
  289.  
  290.     clear(root);
  291.     return 0;
  292. }
  293.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
i 25
i 500
i 25
i 33
i 49
i 17
i 403
i 29
i 105
i 39
i 66
i 305
i 44
i 19
i 441
i 390
i 12
i 81
i 50
i 100
i 999
d 25
d 500
d 25
d 33
d 49
d 17
d 403
d 29
d 105
d 39
d 66
d 305
d 44
d 19
d 441
d 390
d 12
d 81
d 50
d 100
d 999
stdout
copy 
< 25 >
< 25 < 500 >>
<< 25 > 33 < 500 >>
<< 25 > 33 << 49 > 500 >>
<<< 17 > 25 > 33 << 49 > 500 >>
<<< 17 > 25 > 33 << 49 > 403 < 500 >>>
<<< 17 > 25 < 29 >> 33 << 49 > 403 < 500 >>>
<<< 17 > 25 < 29 >> 33 << 49 < 105 >> 403 < 500 >>>
<<< 17 > 25 < 29 >> 33 <<< 39 > 49 < 105 >> 403 < 500 >>>
<<< 17 > 25 < 29 >> 33 <<< 39 > 49 < 66 >> 105 < 403 < 500 >>>>
<<< 17 > 25 < 29 >> 33 <<< 39 > 49 < 66 >> 105 << 305 > 403 < 500 >>>>
<<<< 17 > 25 < 29 >> 33 < 39 < 44 >>> 49 << 66 > 105 << 305 > 403 < 500 >>>>
<<<< 17 < 19 >> 25 < 29 >> 33 < 39 < 44 >>> 49 << 66 > 105 << 305 > 403 < 500 >>>>
<<<< 17 < 19 >> 25 < 29 >> 33 < 39 < 44 >>> 49 <<< 66 > 105 < 305 >> 403 << 441 > 500 >>>
<<<< 17 < 19 >> 25 < 29 >> 33 < 39 < 44 >>> 49 <<< 66 > 105 < 305 < 390 >>> 403 << 441 > 500 >>>
<<<<< 12 > 17 < 19 >> 25 < 29 >> 33 < 39 < 44 >>> 49 <<< 66 > 105 < 305 < 390 >>> 403 << 441 > 500 >>>
<<<<< 12 > 17 < 19 >> 25 < 29 >> 33 < 39 < 44 >>> 49 <<< 66 < 81 >> 105 < 305 < 390 >>> 403 << 441 > 500 >>>
<<<<< 12 > 17 < 19 >> 25 < 29 >> 33 < 39 < 44 >>> 49 <<<< 50 > 66 < 81 >> 105 < 305 < 390 >>> 403 << 441 > 500 >>>
<<<<< 12 > 17 < 19 >> 25 < 29 >> 33 < 39 < 44 >>> 49 <<< 50 > 66 < 81 < 100 >>> 105 << 305 < 390 >> 403 << 441 > 500 >>>>
<<<<< 12 > 17 < 19 >> 25 < 29 >> 33 < 39 < 44 >>> 49 <<< 50 > 66 < 81 < 100 >>> 105 << 305 < 390 >> 403 << 441 > 500 < 999 >>>>>
<<<<< 12 > 17 > 19 < 29 >> 33 < 39 < 44 >>> 49 <<< 50 > 66 < 81 < 100 >>> 105 << 305 < 390 >> 403 << 441 > 500 < 999 >>>>>
<<<<< 12 > 17 > 19 < 29 >> 33 < 39 < 44 >>> 49 <<< 50 > 66 < 81 < 100 >>> 105 << 305 < 390 >> 403 < 441 < 999 >>>>>
<<<<< 12 > 17 > 19 > 29 < 39 < 44 >>> 49 <<< 50 > 66 < 81 < 100 >>> 105 << 305 < 390 >> 403 < 441 < 999 >>>>>
<<<<< 12 > 17 > 19 > 29 < 39 >> 44 <<< 50 > 66 < 81 < 100 >>> 105 << 305 < 390 >> 403 < 441 < 999 >>>>>
<<<< 12 > 19 > 29 < 39 >> 44 <<< 50 > 66 < 81 < 100 >>> 105 << 305 < 390 >> 403 < 441 < 999 >>>>>
<<<< 12 > 19 > 29 < 39 >> 44 <<< 50 > 66 < 81 < 100 >>> 105 << 305 > 390 < 441 < 999 >>>>>
<<< 12 > 19 < 39 >> 44 <<< 50 > 66 < 81 < 100 >>> 105 << 305 > 390 < 441 < 999 >>>>>
<<< 12 > 19 < 39 >> 44 <<< 50 > 66 < 81 >> 100 << 305 > 390 < 441 < 999 >>>>>
<<<< 12 > 19 > 44 << 50 > 66 < 81 >>> 100 << 305 > 390 < 441 < 999 >>>>
<<<< 12 > 19 > 44 << 50 > 81 >> 100 << 305 > 390 < 441 < 999 >>>>
<<<< 12 > 19 > 44 < 50 >> 81 < 100 << 390 > 441 < 999 >>>>
<<< 12 > 19 < 50 >> 81 < 100 << 390 > 441 < 999 >>>>
<< 12 < 50 >> 81 < 100 << 390 > 441 < 999 >>>>
<< 12 < 50 >> 81 << 100 > 390 < 999 >>>
<< 12 < 50 >> 81 < 100 < 999 >>>
<< 50 > 81 < 100 < 999 >>>
<< 50 > 100 < 999 >>
< 100 < 999 >>
< 999 >
https://ideone.com/MR7vkL
language:
C++ (gcc 8.3)
created:
5 hours 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!