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.     Node* x = nullptr;
  74.     Node* f = nullptr;
  75.  
  76.     // find position to insert newKey while storing parent nodes on stack
  77.     while (p != nullptr) {
  78.         if (newKey == p->key) {
  79.             cout << "Key already exists!" << endl;
  80.             return false;  // Avoid inserting duplicates
  81.         }
  82.  
  83.         q = p;
  84.         nodeStack.push(q);
  85.  
  86.         if (newKey < p->key) {
  87.             p = p->left;
  88.         } else {
  89.             p = p->right;
  90.         }
  91.     }
  92.  
  93.     // create new node
  94.     Node* y = getAVLNode(newKey);
  95.  
  96.     // insert y as a child of q
  97.     if (T == nullptr) {
  98.         T = y;
  99.     } else if (newKey < q->key) {
  100.         q->left = y;
  101.     } else {
  102.         q->right = y;
  103.     }
  104.  
  105.     // update height and balancing factor while popping parent nodes from stack
  106.     while (!nodeStack.empty()) {
  107.         q = nodeStack.top();
  108.         nodeStack.pop();
  109.         q->height = 1 + max(height(q->left), height(q->right));
  110.         q->bf = height(q->left) - height(q->right);
  111.  
  112.         if (q->bf > 1 || q->bf < -1) {
  113.             if (x == nullptr) {
  114.                 x = q;
  115.                 f = nodeStack.empty() ? nullptr : nodeStack.top();
  116.             }
  117.         }
  118.     }
  119.  
  120.     // If no imbalance found, return
  121.     if (x == nullptr) return false;
  122.  
  123.     // Rebalance the tree
  124.     if (x->bf > 1) {
  125.         if (x->left->bf >= 0) {
  126.             return rotateLL(x);
  127.         } else {
  128.             return rotateLR(x);
  129.         }
  130.     } else if (x->bf < -1) {
  131.         if (x->right->bf <= 0) {
  132.             return rotateRR(x);
  133.         } else {
  134.             return rotateRL(x);
  135.         }
  136.     }
  137.  
  138.     return true;
  139. }
  140.  
  141. bool deleteAVL(Node* T, int deleteKey) {
  142.     Node* p = T;
  143.     Node* q = nullptr;
  144.     stack<Node*> nodeStack;
  145.     Node* x = nullptr;
  146.     Node* f = nullptr;
  147.  
  148.     // Perform standard BST deletion
  149.     while (p != nullptr && deleteKey != p->key) {
  150.         q = p;
  151.         nodeStack.push(q);
  152.         if (deleteKey < p->key) {
  153.             p = p->left;
  154.         } else {
  155.             p = p->right;
  156.         }
  157.     }
  158.  
  159.     if (p == nullptr) {
  160.         cout << "Key not found!" << endl;
  161.         return false; // deleteKey was not found
  162.     }
  163.  
  164.     // Case 1: Node has two children
  165.     if (p->left != nullptr && p->right != nullptr) {
  166.         nodeStack.push(p);
  167.         Node* tempNode = p;
  168.         if (height(p->left) < height(p->right)) {
  169.             p = p->right;
  170.             while (p->left != nullptr) {
  171.                 nodeStack.push(p);
  172.                 p = p->left;
  173.             }
  174.         } else {
  175.             p = p->left;
  176.             while (p->right != nullptr) {
  177.                 nodeStack.push(p);
  178.                 p = p->right;
  179.             }
  180.         }
  181.         tempNode->key = p->key;
  182.         q = nodeStack.top();
  183.         nodeStack.pop();
  184.     }
  185.  
  186.     // Case 2: Node has 0 or 1 child
  187.     if (p->left == nullptr && p->right == nullptr) {
  188.         if (q == nullptr) {
  189.             T = nullptr;
  190.         } else if (q->left == p) {
  191.             q->left = nullptr;
  192.         } else {
  193.             q->right = nullptr;
  194.         }
  195.     } else {
  196.         Node* child = (p->left != nullptr) ? p->left : p->right;
  197.         if (q == nullptr) {
  198.             T = child;
  199.         } else if (q->left == p) {
  200.             q->left = child;
  201.         } else {
  202.             q->right = child;
  203.         }
  204.     }
  205.  
  206.     delete p;
  207.  
  208.     // Update height and balancing factor while popping parent nodes from stack
  209.     while (!nodeStack.empty()) {
  210.         q = nodeStack.top();
  211.         nodeStack.pop();
  212.         q->height = 1 + max(height(q->left), height(q->right));
  213.         q->bf = height(q->left) - height(q->right);
  214.  
  215.         if (q->bf > 1 || q->bf < -1) {
  216.             x = q;
  217.             f = nodeStack.empty() ? nullptr : nodeStack.top();
  218.  
  219.             // Rebalance the tree
  220.             if (x->bf > 1) {
  221.                 if (x->left->bf >= 0) {
  222.                     T = rotateLL(x);
  223.                 } else {
  224.                     T = rotateLR(x);
  225.                 }
  226.             } else if (x->bf < -1) {
  227.                 if (x->right->bf <= 0) {
  228.                     T = rotateRR(x);
  229.                 } else {
  230.                     T = rotateRL(x);
  231.                 }
  232.             }
  233.         }
  234.     }
  235.  
  236.     return true;
  237. }
  238.  
  239. void inorder(Node* T) {
  240.     if (T == nullptr) {
  241.         return;
  242.     }
  243.  
  244.     cout << "<";
  245.  
  246.     if (T->left != nullptr) { // 왼쪽 자식이 있을 때만 출력
  247.         inorder(T->left);
  248.     }
  249.  
  250.     cout << " " << T->key << " "; // 현재 노드의 키를 출력
  251.  
  252.     if (T->right != nullptr) { // 오른쪽 자식이 있을 때만 출력
  253.         inorder(T->right);
  254.     }
  255.  
  256.     cout << ">";
  257. }
  258.  
  259. void clear(Node* T) {
  260.     if (T == nullptr) {
  261.         return;
  262.     }
  263.     clear(T->left);
  264.     clear(T->right);
  265.     delete T;
  266. }
  267.  
  268.  
  269. int main() {
  270.  
  271.     Node* root = nullptr;
  272.     char operation;
  273.     int key;
  274.  
  275.     while (cin >> operation >> key) {
  276.         bool sucess = false; // 삽입, 삭제가 에러 상황을 만나지 않고 잘 수행되었는지
  277.         if (operation == 'i') {
  278.             sucess = insertAVL(root, key);
  279.         }
  280.         else if (operation == 'd') {
  281.             sucess = deleteAVL(root, key);
  282.         }
  283.         if (sucess) {
  284.             inorder(root);
  285.             cout << endl;
  286.         }
  287.     }
  288.     clear(root);
  289.     return 0;
  290. }
  291.  
Success #stdin #stdout 0s 5284KB
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 
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
Key not found!
https://ideone.com/ZGyk1J
language:
C++ (gcc 8.3)
created:
2 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!