1function insert(root, val) {
2 const z = bstInsert(root, val); // 新节点着红色
3 return insertFixup(root, z);
4}
5function insertFixup(root, z) {
6 while (z.parent && z.parent.red) {
7 const gp = z.parent.parent;
8 if (uncle && uncle.red) {
9 // 情况1: 父叔皆红 → 重着色，z 上移
10 parent.red = false; uncle.red = false;
11 gp.red = true; z = gp;
12 } else {
13 // 情况2/3: 先转成同侧，再旋转祖父
14 if (外侧) { z = z.parent; rotate(z); }
15 parent.red = false; gp.red = true; rotate(gp);
16 }
17 }
18 root.red = false; // 根始终为黑
19 return root;
20}