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
122
123
124
| #include<iostream>
#include<cstdio>
using namespace std;
class Node {
public:
int data;
int height;
Node *left;
Node *right;
};
Node *newNode(int data) {
Node* node = new Node();
node->data = data;
node->height = 1;
node->left = NULL;
node->right = NULL;
return node;
}
int getHeight(Node* node) {
if (node == NULL)
return 0;
return node->height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
int getBalance(Node* node) {
if (node == NULL)
return 0;
return getHeight(node->left) - getHeight(node->right);
}
Node *rightRotate(Node* y) {
Node *x = y->left;
Node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(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(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y;
}
Node *insert(Node *node, int data){
if (node == nullptr) {
return (newNode(data));
}
if (data < node->data) {
node->left = insert(node->left, data);
}
else if (data > node->data) {
node->right = insert(node->right, data);
}
else {
return node;
}
node->height = 1 + max(getHeight(node->left), getHeight(node->right));
int balance = getBalance(node);
if (balance > 1 && data < node->left->data) {
return rightRotate(node);
}
if (balance < -1 && data > node->right->data) {
return leftRotate(node);
}
if (balance > 1 && data > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && data < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void printTree(Node *root) {
if (root == NULL) {
return;
}
printTree(root->left);
cout << root->data << " ";
printTree(root->right);
}
int main() {
Node *root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
printTree(root);
return 0;
}
|