-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathavl.cpp
More file actions
107 lines (91 loc) · 1.98 KB
/
Copy pathavl.cpp
File metadata and controls
107 lines (91 loc) · 1.98 KB
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
struct Node
{
Node* left;
Node* right;
int value;
int factor;
Node(int v)
{
value = v;
left = NULL;
right = NULL;
factor = 0;
};
struct AVL
{
Node* root;
enum {
NONE,
LEFT,
RIGHT,
};
AVL()
{
root = NULL;
}
Node* search(int v)
{
Node* n = root;
while (n) {
if (v < n->value) n = n->left;
else if (v > n->value) n = n->right;
else return n;
}
return NULL;
}
bool insert(int v)
{
if (!root) {
Node* n = new Node(v);
if (!n) return false;
root = n;
return true;
}
Node* arr[64] = {NULL};
int count = 0;
Node* tmp = root;
while (tmp) {
arr[count] = tmp;
count++;
if (v < tmp->value) {
tmp = tmp->left;
} else if (v > tmp->value) {
tmp = tmp->right;
} else {
return false;
}
}
int direction1 = NONE;
int direction2 = NONE;
Node* n = new Node(v);
if (!n) return false;
Node* last = arr[count-1];
if (v < last->value) {
last->left = n;
last->factor--;
direction1 = LEFT;
} else {
last->right = n;
last->factor++;
direction1 = RIGHT;
}
if (count <= 1) return true;
int i = count - 2;
Node* pre = NULL;
while (i >= 0) {
pre = arr[i];
if (pre->left == last) pre->factor--;
else pre->factor++;
if (pre->factor < -1) {
direction2 = LEFT;
break;
} else if (pre->factor > 1) {
direction2 = RIGHT;
break;
}
}
if (direction2 == NONE) {
return true;
}
}
};