Untitled
unknown
plain_text
7 months ago
2.3 kB
0
Indexable
Never
#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; }