#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 = 5;
int ins[11] = {1, 12, 23, 34, 45, 63, 67, 30, 89, 39, 4};
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;
}