sfsfsdfsdadsvdfsdfsdfds
Sat Sep 17 2022 16:41:22 GMT+0000 (Coordinated Universal Time)
Saved by @Lokesh8126 #c++
#include<bits/stdc++.h> using namespace std; class BinaryTreeNode { public: int data; BinaryTreeNode * left; BinaryTreeNode *right; int height; // BinaryTreeNode() // { // data = 0; // left = NULL; // right = NULL; // } BinaryTreeNode(int data) { this->data = data; left = NULL; right = NULL; } ~BinaryTreeNode() { delete left; delete right; } }; class AVL { public: BinaryTreeNode *root; AVL() { this->root = NULL; } int getheight(BinaryTreeNode* root) { if (root == NULL) return 0; return 1 + max(getheight(root->left) , getheight(root->right)); } int getbalanceFactor(BinaryTreeNode* node) { if ( node == NULL) return 0; return getheight(node->left) - getheight(node->right); } BinaryTreeNode* rightRotate(BinaryTreeNode* y) { /* y x / \ / \ x T3 ---->T1 y / \ / \ T1 T2 T2 T3 */ BinaryTreeNode* x = y->left; BinaryTreeNode *T2 = x->right; // T1 & T3 not required because their ptr not changes x->right = y; y->left = T2; //updation to heights // y->height = 1 + max(getHeight(y->left) , getHeight(y->right)); // X->height = 1 + max(getHeight(x > left) , getHeight(x->right)); return x; //as now x is root node } BinaryTreeNode* leftRotate(BinaryTreeNode* x) { /* y x / \ / \ x T3 <--- T1 y / \ / \ T1 T2 T2 T3 */ //before rotation BinaryTreeNode* y = x->right; BinaryTreeNode *T2 = y->left; // T1 & T3 not required because their ptr not changes //changes to rotation y->left = x; x->right = T2; //updation to heights // y->height = 1 + max(getHeight(y->left) , getHeight(y->right)); // X->height = 1 + max(getHeight(x > left) , getHeight(x->right)); return y; //as now y is root node } // 1. insert private: BinaryTreeNode * insert(BinaryTreeNode* node, int data) { if ( node == NULL) { BinaryTreeNode* newnode = new BinaryTreeNode (data); return newnode; } if (data <= node->data) node->left = this->insert( node->left , data); else if (data > node->data) node->right = this->insert(node->right , data); else return node; // node->height = 1 + max(getHeight(node > left) , getHeight(node->right)); // //height update krni padegi as it is req in balfac int balfac = getbalanceFactor(node) ; // left left case ..bf= leftH -rightH >1 if (balfac > 1 && data < node->left->data) { //insertion takes place at LST return this->rightRotate(node); } //right right case , bf= leftH -rightH < -1 if (balfac < -1 && node->right->data < data) { return this->leftRotate(node); } //left rightcase,bf= leftH -rightH >1 if (balfac > 1 && node->left->data < data)//bf>1 tabhi root k left me imbal { /* r= 30 30 25 / / / \ 20 25 20 30 \ / data=25 20 */ node->left = leftRotate(node->left); // return this->rightRotate(node); } //right left case bf= leftH -rightH <-1 if (balfac > 1 && node->left->data < data)//bf>1 tabhi root k left me imbal { /* r= 20 20 25 \ \ / \ 30 25 20 30 / \ data=25 30 */ node->right = rightRotate(node->right); // //now RR imbalance return this->leftRotate(node); } return node; } public: BinaryTreeNode* insert ( int data) { // BinaryTreeNode *node = new BinaryTreeNode(data); this->root = insert(this->root , data); return root; } //2. delete : trick think node as leaf or any internal node private: BinaryTreeNode * deleteData(BinaryTreeNode* node , int data) { if (node == NULL) return NULL; if (data < node->data) { node ->left = deleteData(node->left , data); return node; } else if (node->data < data) { node->right = deleteData(node -> right , data); return node; } else // if value matche { if (node->left == NULL && node->right == NULL) //a leaf { delete node; return NULL; } else if (node->left == NULL) { BinaryTreeNode *rightsubtree = node->right; node ->right = NULL; delete node; return rightsubtree; } else if (node->right == NULL) { BinaryTreeNode *leftsubtree = node->left; node->left = NULL; delete node; return leftsubtree; } else // both rst and lst exists { BinaryTreeNode * minNode = node ->right; while (minNode->left != NULL) { minNode = minNode->left; } int minFromRST = minNode->data; node->data = minFromRST; node->right = deleteData(node->right, minFromRST); return node; } } int balfac = getbalanceFactor(node); if (balfac == 2 && getbalanceFactor(node->left ) >= 0) { /* r= 30 30 30 20 / \ / \ / / \ 20 40**del or 20 40 **del = 20 10 30 /\ / / 10 25 10 10 */ // 25 case will be taken care by rightrotate BinaryTreeNode*newnode = rightRotate(node); return newnode; } else if (balfac == 2 && getbalanceFactor(node->left) == -1) { /* r= 30 30 25 / \ / / \ (-1) 20 40**del or (-1) 20 lr imbalance = 20 30 \ \ 25 25 */ // 25 case will be taken care by rightrotate node->left = leftRotate(node->left); BinaryTreeNode*newnode = rightRotate(node); return newnode; } else if (balfac == -2 && getbalanceFactor(node->right) <= 0) { /* 20 20 30 / \ / \ / \ del 10 30 del(10) 30 20 40 /\ \ 25 40 40 // 25 case will be taken care by leftrotate */ BinaryTreeNode * newnode = leftRotate(node); return newnode; } else if (balfac == -2 && getbalanceFactor(node->right) == 1) { /* 20 20 25 / \ \ / \ del 10 30 (1) 30 rl imbal 20 30 / / 25 25 */ node->right = leftRotate(node->right); BinaryTreeNode * newnode = leftRotate(node); return newnode; } } public: BinaryTreeNode* deleteData( int data) { this->root = deleteData(this->root , data); return root; } //3.search private: bool search(BinaryTreeNode* node , int data) { if (node == NULL) return false; if (node->data == data) return true; else if (node->data < data) return search (node->right , data); else return search(node->left , data); } public: bool search(int data) { return search(root, data); } //4. occurences private : int count_occurence(BinaryTreeNode*node , int data) { if (node == NULL) return 0; if (node ->data == data) return 1 + count_occurence(node->left, data) + count_occurence(node->right, data); else if (node->data < data) return count_occurence(node->right, data); else if (data < node->data ) return count_occurence(node->left, data); return 0; } public: int count_occurence(int data) { return count_occurence(this->root , data); } private: int upper_bound(BinaryTreeNode*node, int data) { if (node == NULL) return 0; //leaf data=15 leaf=14(node->data)(rightmost) if (node->left == NULL && node->right == NULL && node->data <= data) { return 0; } //data=12 ex= null (12) 13(root) or 11 (12) 13(root) or 12 (12) 13(root) if ((data < node->data && node->left == NULL) || (node->left->data <= data && data < node->data)) { return node->data; } //data=12 11(root) (12) or 12(root) (12) if (node->data <= data) { //node->left->data se compare wali cond already checked above return upper_bound(node->right, data); } else if (data < node->data) { //data=12 14(root->left) 15(root) return upper_bound(node->left , data); } return 0; } public: int upper_bound(int data) { return upper_bound(this->root , data); } private: int lower_bound(BinaryTreeNode*node, int data) { if (node == NULL) return 0; //reachd to leaf data =14 leaf=15(node->data) leftmost node if (node->left == NULL && node->right == NULL && data < node->data ) { return 0; } //itsef a leaf if (node->left == NULL && node->right == NULL && data == node->data) return node->data; //data=12 11(root) null or 11(root) 13 or 12(root) 13 if ((node->data < data && node->right == NULL) || (node->data < data && data < node->right->data)) { return node->data; } //data=12 12 13(root) or (12) 12(root) if ( data <= node->data) { return lower_bound(node->left, data); } else if ( node->data < data) { //node->right->data se compare wali cond already checked above //data=12 10(root) 11(root->right) 12 return lower_bound(node->right, data); } return 0; } public: int lower_bound(int data) { return lower_bound(this->root , data); } public: int lesser_bound(BinaryTreeNode*node , int data) { if (node == NULL) return 0; //reachd to leaf data =14 leaf=15(node->data) leftmost node if (node->left == NULL && node->right == NULL && data < node->data ) { return 0; } //itsef a leaf if (node->left == NULL && node->right == NULL && data == node->data) return 0; //data=12 11(root) null or 11(root) 13 or 12(root) 13 if ((node->data < data && node->right == NULL) || (node->data < data && data < node->right->data)) { return node->data; } //data=12 12 13(root) or (12) 12(root) if ( data <= node->data) { return lesser_bound(node->left, data); } else if ( node->data < data) { //node->right->data se compare wali cond already checked above //data=12 10(root) 11(root->right) 12 return lesser_bound(node->right, data); } return 0; } private: int closest_element(BinaryTreeNode*node , int data) { if (node == NULL) return -1; if (node->data == data) return node->data; int x = upper_bound(node, data); int y = lesser_bound(node, data); //y----------data ---------x if (y != 0 && x != 0) return (data - y) > (x - data) ? x : y; else if (y == 0 && x != 0) return x; else return y; } public: int closest_element(int data) { return closest_element(this->root , data); } private: BinaryTreeNode* Element_Kth_largest(BinaryTreeNode*node , int &k) { // if (node == NULL || c > k ) // return -1; // //reverse inorder traversal // Element_Kth_largest(node->right, k, c ); // c++; // if (k == c) // return node->data; // Element_Kth_largest(node->left, k , c); // return -1; if (node == NULL) return NULL; BinaryTreeNode* newnode = Element_Kth_largest(node->right, k); if (newnode != NULL) return newnode; k--; if (k == 0) return node; return Element_Kth_largest(node->left, k); } public: int Element_Kth_largest(int k) { BinaryTreeNode*newnode = Element_Kth_largest(this->root, k ); int c = -1; if (newnode == NULL) return c; else c = newnode->data; return c; } private: int count_range(BinaryTreeNode*node, int eLeft, int eRight) { if (node == NULL) return 0; // if (node->data == eLeft && node->data == eRight) // return 1; int count = 0; // Special Optional case for improving efficiency // if (eLeft <= node->data && node->data <= eRight) // return 1 + count_range(node->left , eLeft, eRight) + count_range(root->right , eLeft, eRight); if (eLeft <= node->data && node->data <= eRight) count += 1; count += count_range(node->left , eLeft, eRight); return count + count_range(node->right , eLeft, eRight); // else if (node->data < eLeft ) // return count_range(node->right, eLeft, eRight) ; // else // return count_range(root->left , eLeft, eRight); } public: int count_range(int eLeft , int eRight) { return count_range(this->root, eLeft, eRight); } }; void preorder(BinaryTreeNode * root) { if (root == NULL) return; cout << root->data << " "; preorder(root->left); preorder(root->right); } void inorder(BinaryTreeNode * root) { if (root == NULL) return; inorder(root->left); cout << root->data << " "; inorder(root->right); } int main() { #ifdef ONLINE_JUDGE freeopen("input.txt", "r", stdin); freeopen("output.txt", "r", stdin); #endif AVL obj_avl; //segmentationfault state // obj_avl.root = obj_avl.insert(30); // obj_avl.root = obj_avl.insert(31); // obj_avl.root = obj_avl.insert(30); // obj_avl.root = obj_avl.insert(30); // obj_avl.root = obj_avl.insert(30); // obj_avl.root = obj_avl.insert(60); // obj_avl.root = obj_avl.insert(30); // obj_avl.root = obj_avl.insert(30); // obj_avl.root = obj_avl.insert(30); // obj_avl.root = obj_avl.insert(30); // obj_avl.root = obj_avl.insert(40); // int option; // do { // cout << "What operation do you want to perform? " << // " Select Option number. Enter 0 to exit." << endl; // cout << "1. Insert Node" << endl; // cout << "2. Delete Node" << endl; // cout << "3. Search Node" << endl; // cout << "4. " << endl; // cout << "5. " << endl; // cout << "6. " << endl; // cout << "0. Exit Program" << endl; // cin >> option; // //Node n1; // int val; // switch (option) { // case 0: // break; // case 1: // cout << "Enter VALUE of TREE NODE to INSERT in AVL Tree: "; // cin >> val; // obj_avl.root = obj_avl.insert(val); // cout << endl; // break; // case 2: // cout << "Enter VALUE of TREE NODE to delete in AVL Tree: "; // cin >> val; // obj_avl.root = obj_avl.deleteData(val); // break; // case 3: // cout << "Enter VALUE of TREE NODE to search in AVL: "; // cin >> val; // cout << obj_avl.search(val); // break; // default: // cout << "Enter Proper Option number " << endl; // } // } while (option != 0); int n = 7; // int ins[11] = {1, 12, 23, 34, 45, 63, 67, 30, 89, 39, 4}; int ins[12] = {30, 31, 30, 30, 30, 30, 60, 30, 30, 30, 30, 40}; for (int i = 0; i < n; ++i) { obj_avl.root = obj_avl.insert(ins[i]); } cout << endl; cout << "\npreorder :"; preorder(obj_avl.root); cout << "\ninorder :"; inorder(obj_avl.root); cout << endl; int arr[10] = { -1, 9, 20, 23 , 44 , 5, 6 , 40, 50, 67 }; int k = 7; int lar[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // for (int i = 0; i < k; ++i) // { // int u; // int e = lar[i]; // cout << "\nkth largest element : " << e ; // u = obj_avl.Element_Kth_largest(e); // cout << " is:" << u; // } cout << endl; for (int i = 2; i < 8; ++i) { int l = arr[i]; int h = arr[i + 1]; if (l > h) swap(l, h); cout << "Count of nodes between [" << l << ", " << h << "] is " << obj_avl.count_range(l, h) << endl; } // for (int i = 0; i < k; ++i) // { // int u; // int e = arr[i]; // cout << "\nclosest element to : " << e ; // u = obj_avl.closest_element(e); // cout << " is:" << u; // } // cout << endl; // for (int i = 0; i < k; ++i) // { // int u; // int e = arr[i]; // cout << "\nlower bound of : " << e ; // u = obj_avl.lower_bound(e); // cout << " is:" << u; // } // cout << endl; // for (int i = 0; i < k; ++i) // { // int u; // int e = arr[i]; // cout << "\nupper bound of :" << e ; // u = obj_avl.upper_bound(e); // cout << ":" << u; // } // int count_o[10] = {30, 55, 38, 40, 60, 89, 31, 35, 47, 69}; // for (int i = 0; i < 10; ++i) // { // int s = count_o[i]; // int r ; // cout << "\n\ncount:" << s; // r = obj_avl.count_occurence(s); // cout << "\nnumber of " << s << " are :" << r ; // } // int find[10] = {30, 55, 38, 40, 60, 89, 31, 35, 47, 69}; // for (int i = 0; i < 10; ++i) // { // int s = find[i]; // int r = 0; // cout << "\n\nsearch:" << s; // r = obj_avl.search(s); // if (r) // cout << "\nyes " << s << " is found"; // else // cout << "\nno. :" << s << " is not found"; // } // cout << endl; // cout << "\npreorder :"; // preorder(obj_avl.root); // cout << "\ninorder :"; // inorder(obj_avl.root); // int del[10] = {50, 38, 60, 56, 3, 30, 60}; // for (int i = 0; i < 10; ++i) // { // int v = find[i]; // int r = 0; // cout << "\n\ndelete :" << v << endl; // r = obj_avl.search(v); // if (!r) // { // cout << "no. :" << v << " is not found"; // } // else // { // obj_avl.root = obj_avl.deleteData(v); // cout << "sucessfully deleted :" << v << endl; // cout << "preorder :"; // preorder(obj_avl.root); // cout << "\ninorder :"; // inorder(obj_avl.root); // } // } return 0; }
Comments