1function insert(root, value) {
2 if (!root) return new AVLNode(value);
3 if (value < root.value)
4 root.left = insert(root.left, value);
5 else if (value > root.value)
6 root.right = insert(root.right, value);
7 else return root; // duplicate
8
9 // Update height
10 root.height = 1 + max(height(root.left),
11 height(root.right));
12
13 // Compute balance factor
14 const bf = height(root.left) - height(root.right);
15
16 // LL rotation
17 if (bf > 1 && value < root.left.value)
18 return rotateRight(root);
19
20 // RR rotation
21 if (bf < -1 && value > root.right.value)
22 return rotateLeft(root);
23
24 // LR rotation
25 if (bf > 1 && value > root.left.value) {
26 root.left = rotateLeft(root.left);
27 return rotateRight(root);
28 }
29
30 // RL rotation
31 if (bf < -1 && value < root.right.value) {
32 root.right = rotateRight(root.right);
33 return rotateLeft(root);
34 }
35
36 return root; // balanced
37}
38
39function rotateRight(z) {
40 const y = z.left;
41 const T3 = y.right;
42 y.right = z;
43 z.left = T3;
44 updateHeight(z); updateHeight(y);
45 return y;
46}
47
48function rotateLeft(z) {
49 const y = z.right;
50 const T2 = y.left;
51 y.left = z;
52 z.right = T2;
53 updateHeight(z); updateHeight(y);
54 return y;
55}