-
Notifications
You must be signed in to change notification settings - Fork 0
/
AVL Tree Deletion.java
99 lines (79 loc) · 2.56 KB
/
AVL Tree Deletion.java
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
class Sol {
static int height(Node node) {
if (node == null)
return 0;
return node.height;
}
static int getBalance(Node node) {
if (node == null)
return 0;
return height(node.left) - height(node.right);
}
static Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
static Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
static Node minValueNode(Node node) {
Node current = node;
while (current.left != null)
current = current.left;
return current;
}
public static Node deleteNode(Node root, int data) {
if (root == null)
return root;
if (data < root.data)
root.left = deleteNode(root.left, data);
else if (data > root.data)
root.right = deleteNode(root.right, data);
else {
if ((root.left == null) || (root.right == null)) {
Node temp = null;
if (root.left == null)
temp = root.right;
else
temp = root.left;
if (temp == null) {
temp = root;
root = null;
} else
root = temp;
} else {
Node temp = minValueNode(root.right);
root.data = temp.data;
root.right = deleteNode(root.right, temp.data);
}
}
if (root == null)
return root;
root.height = Math.max(height(root.left), height(root.right)) + 1;
int balance = getBalance(root);
if (balance > 1 && getBalance(root.left) >= 0)
return rightRotate(root);
if (balance > 1 && getBalance(root.left) < 0) {
root.left = leftRotate(root.left);
return rightRotate(root);
}
if (balance < -1 && getBalance(root.right) <= 0)
return leftRotate(root);
if (balance < -1 && getBalance(root.right) > 0) {
root.right = rightRotate(root.right);
return leftRotate(root);
}
return root;
}
}