data-structure/AVLTree at master · rakeshmalviya1985/data-structure · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/******************************************************************************
Find more detail on @equalConnect Coach youtube

*******************************************************************************/

#include <iostream>
using namespace std;

struct node
{
  int key;
  node* left;
  node* right;
  int height;
};

node* newNode(int key)
{
    node* newPtr = new node();
    newPtr->key = key;
    newPtr->right = NULL;
    newPtr->left = NULL;
    newPtr->height = 1;
}
int max(int height1 , int height2)
{
    if(height1 > height2)
      return height1;
    else
      return height2;
}
int height(node *root)
{
    if(root == NULL)
       return 0;
    return root->height;
}
int getBalaceFactor(node* root)
{
    if(root == NULL)
    return 0;

    return height(root->left) - height(root->right);
}

node* rightRotate(node* root)
{
    if(root == NULL)
      return NULL;

    node* tmpLeft   = root->left;
    node* tmpChRight = tmpLeft->right;
    tmpLeft->right = root;
    root->left = tmpChRight;
    root->height = max(height(root->left) , height(root->right)) + 1;

    tmpLeft->height = max(height(tmpLeft->left) , height(tmpLeft->right)) + 1;


    return tmpLeft;

}

node* leftRotate(node* root)
{
    if(root == NULL)
      return NULL;

    node* tmpRight = root->right;
    node* tmpChLeft = tmpRight->left;

    tmpRight->left = root;
    root->right = tmpChLeft;
    root->height = max(height(root->left) , height(root->right)) + 1;
    tmpRight->height  = max(height(tmpRight->left) , height(tmpRight->right)) + 1;

    return tmpRight;
}

node* insert(node* root , int key)
{
    if(root == NULL)
    return newNode(key);

    if(key > root->key)
       root->right = insert(root->right , key);
    else if(key < root->key)
       root->left = insert(root->left , key);
    else
       return root;

    root->height = max(height(root->left) , height(root->right))+1;


    int balFactor = getBalaceFactor(root);


    if(balFactor > 1 && key < root->left->key)
       return rightRotate(root);
    else if( balFactor < -1 && key > root->right->key)
       return leftRotate(root);
    else if( balFactor > 1 && key > root->left->key  )
    {
         root->left = leftRotate(root->left);
         return rightRotate(root);
    }
    else if( balFactor < -1 && key < root->right->key)
    {
       root->right = rightRotate(root->right);
       return leftRotate(root);
    }
       return root;
}


int main()
{
    cout<<"Hello World";

    return 0;
}