- #include<iostream>
- using namespace std;
- struct node{
- int data;
- node *L, *R;
- };
- class AVL{
- node *root;
- public:
- AVL(){
- root=NULL;
- }
- int height(node *temp);
- int max(int a, int b);
- node* LL(node *);
- node* RR(node *);
- node* LR(node *);
- node* RL(node *);
- node* insert(node* temp,int key);
- };
- int AVL::max(int a, int b){
- return (a > b)?a:b;
- }
- int AVL:: height(node *temp){
- if(temp == NULL){
- return -1;
- }
- if(temp -> L == NULL && temp -> R == NULL){
- return 0;
- }
- return(1 + max(height(temp -> L), height(temp -> R)));
- }
- node * AVL:: LL(node *parent){
- node *temp = parent -> L;
- parent -> L = temp -> R;
- temp -> R = parent;
- return temp;
- }
- node * AVL:: RR(node *parent){
- node *temp = parent -> R;
- parent -> R = temp -> L;
- temp -> L = parent;
- return temp;
- }
- node * AVL:: LR(node *parent){
- parent -> R = RR(parent -> L);
- parent = LL(parent);
- return parent;
- }
- node * AVL:: RL(node *parent){
- parent -> R = RR(parent -> R);
- parent = LL(parent);
- return parent;
- }
- node* AVL::insert(node* temp,int key){
- node *nn=new node;
- nn->data=key;
- nn->L=NULL;
- nn->R=NULL;
- if(temp==NULL){
- temp=new node;
- temp->data=key;
- temp->L=temp->R=NULL;
- }
- else{
- if(key<temp->data){
- temp->L=insert(temp->L,key);
- if((height(temp->L))-height(temp->R)==2){
- if(key<temp->L->data)
- temp=LL(temp);
- else
- temp=LR(temp);
- }
- }
- else{
- temp->R=insert(temp->R,key);
- if((height(temp->L))-height(temp->R)==-2){
- if(key<temp->L->data)
- temp=RR(temp);
- else
- temp=RL(temp);
- }
- }
- }
- return temp;
- }
- int main(){
- AVL b;
- b.insert(b.root,5);
- return 0;
- }
[text] vt
Viewer
Editor
You can edit this paste and save as new: