-
Notifications
You must be signed in to change notification settings - Fork 1
/
AVL_Insertion.cpp
101 lines (82 loc) · 2.36 KB
/
AVL_Insertion.cpp
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
struct Node
{
int data;
Node *left;
Node *right;
int height;
};
* /
class Solution
{
public:
/*You are required to complete this method */
int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left),
height(y->right)) +
1;
x->height = max(height(x->left),
height(x->right)) +
1;
return x;
}
Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left),
height(x->right)) +
1;
y->height = max(height(y->left),
height(y->right)) +
1;
return y;
}
int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
Node *insertToAVL(Node *node, int key)
{
if (node == NULL)
return (new Node(key));
if (key < node->data)
node->left = insertToAVL(node->left, key);
else if (key > node->data)
node->right = insertToAVL(node->right, key);
else
return node;
node->height = 1 + max(height(node->left),
height(node->right));
int balance = getBalance(node);
if (balance > 1 && key < node->left->data)
return rightRotate(node);
if (balance < -1 && key > node->right->data)
return leftRotate(node);
if (balance > 1 && key > node->left->data)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->data)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
};