RedBlackTree: insert loses nodes (e.g. 1,3,2,4,5 -> "3,4,5"); two root causes not covered by #561 #2229

Inserting unique keys into RedBlackTree silently drops nodes and breaks the red-black properties. No remove is involved; inserts alone do it.

import RedBlackTree from './src/data-structures/tree/red-black-tree/RedBlackTree';

const tree = new RedBlackTree();
[1, 3, 2, 4, 5].forEach((v) => tree.insert(v));
tree.toString();   // "3,4,5"   expected "1,2,3,4,5"
tree.contains(1);  // false
tree.contains(2);  // false

More cases:

• 1,3,2,4 gives a red-red violation: 2B(1R, 3R(., 4R)).
• 1,4,2,3,5,6 throws TypeError: null is not an object (evaluating 'node.meta').
• 6,2,1,3,7,4,5 produces unequal black heights under node 2.
• In a randomized test (3,000 trees, 60 unique random inserts each, invariants checked after every insert), 3,000 / 3,000 trees end up broken.

There are three independent causes:

1. (Known, PR Fix RedBlackTree rotations #561.) In leftRightRotation / rightLeftRotation, setLeft/setRight clear the parent pointer of the node being replaced even when that node has already been re-attached elsewhere, leaving parentNode.parent === null.

2. (New.) In leftLeftRotation (lines 141–151) and rightRightRotation (216–226), parentNode.setRight(grandParentNode) correctly sets grandParentNode.parent = parentNode. Then grandGrandParent.setLeft(parentNode) replaces its old child, which is grandParentNode, and nulls grandParentNode.parent again. Later, line 105 (if (newGrandParent.parent === null) this.root = newGrandParent) promotes an inner node to root, and everything outside its subtree is lost.

3. (New.) After a rotation the new subtree root is black, but line 113 calls this.balance(newGrandParent) anyway. balance() only checks the parent's colour (line 53), not whether node itself is red, so a black node under a red parent triggers a second, wrong rotation.

Applying the fixes cumulatively on 3,000 random sequences:

Suggested fix:

• In BinaryTreeNode.setLeft/setRight, only detach the old child if it still points back: if (this.left && this.left.parent === this) this.left.parent = null;, and the same for right. This covers (1) and (2), and also the AVL parent-link bugs in Bug in AVL Tree rorateLeftLeft and rotateRightRight #325.
• At the top of balance(), return early unless node is the root or node is red.

Found with property-based testing against a sorted-array model (harness).

Found during an independent property-based audit of this repo (full report and reproducible harness: https://github.com/devladpopov/algorithm-autopsy/tree/main/autopsy-02).