Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- using namespace std;
- struct node{
- string data;
- node *L, *R;
- };
- class AVL{
- node *root;
- public:
- AVL(){
- root = NULL;
- }
- int height(node *temp);
- int max(int a, int b);
- //int balancefactor(node *n);
- node * LL(node *);
- node * RR(node *);
- node * LR(node *);
- node * RL(node *);
- node *getroot(){
- return this -> root;
- }
- void inorder(node *t){
- if(t != NULL){
- inorder(t -> L);
- cout << t -> data << " ";
- inorder(t -> R);
- }
- }
- node *insert(node *temp,int key){
- // node *temp=root;
- 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 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)));
- }
- /*int AVL::balancefactor(node *n){
- if (n == NULL){
- return 0;
- }
- return height(n -> L) - height( n-> 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;
- }
- int main(){
- AVL a;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement