Untitled

 avatar
unknown
plain_text
2 years ago
2.3 kB
1
Indexable
#include <iostream>
using namespace std;
struct node{
	int key;
    struct node* left;
	struct node* right;
	int height;
};
int getheight(struct node* n){
	if(n=NULL)
	   return 0;
	return n->height;
}
struct node* createnode( int key){
	struct node* newnode= new node;
	newnode ->key = key;
	newnode->left=NULL;
	newnode->right=NULL;
	newnode->height=1;
	return newnode;
}
int max (int a,int b){
	return (a>b)?a:b;
}
int getBalanceFactor(struct node* n){
	if(n=NULL){
		return 0;
	}
	return getheight(n->left) - getheight(n->right);
}
struct node* rightRotate(struct node* y){
	struct node* x=y->left;
	struct node* T2=x->right;
	x->right=y;
	y->left=T2;
	
	x->height =max(getheight(x->right), getheight(x->left))+1;
	y->height =max(getheight(y->right), getheight(y->left))+1;
	return x;
}
struct node* leftRotate(struct node* x){
	struct node* y=x->right;
	struct node* T2=y->left;
	y->left=x;
	x->right=T2;
	
	
	x->height =max(getheight(x->right), getheight(x->left))+1;
	y->height =max(getheight(y->right), getheight(y->left))+1;
	return y;
}
struct node* insert(struct node* node , int key){
	if(node==NULL)
	  return createnode(key);
	   
	 if(key < node->key)
	   node->left = insert(node->left, key);
    	if(key > node->key)
	   node->right = insert(node->right, key);
	    node->height = 1 + max(getheight(node->left), getheight(node->right));
	int bf =getBalanceFactor(node);
	
	//left left case
	if(bf>1 && key<node->left->key){
		return rightRotate(node);
	}
	// right right case
	 if(bf<-1 && key>node->right->key){
		return leftRotate(node);
	}
	// left right case
    	if(bf>1 && key>node->left->key){
		node->left=leftRotate(node->left);
		return rightRotate(node);
	}
	// right left case
	     if(bf<-1 && key>node->right->key){
		node->right=rightRotate(node->right);
		return leftRotate(node);
	}
	return node;
}
void inorder(struct node* root){
	
	if(root!=NULL){
		inorder(root->left);
	    cout<<" "<<root->key;
		inorder(root->right);
	}
}
int main(){
	struct node* root = NULL;
 	root = insert(root, 60);
	root = insert(root, 3);
	root = insert(root, 77);
	root = insert(root, 55);
	root = insert(root, 1);
	root = insert(root, 10);
	inorder(root);
	return 0;	
}