Testing Red-Black Tree Validity After Sequential Insertions on Batch-Built Trees

[devarajabc]

I performed batch_size + 20 additional rb_insert operations on a tree built using rb_batch_build_balanced.
This experiment was also designed to test whether rb_insert can rebalance the "All Black tree" if it is not a valid red-black tree.
However, the result shows that it fails to do so.

 /* Commit batch to empty tree */
rb_batch_commit(&batch_tree, &batch);
assert_property_tree_valid(&batch_tree, "batch insertion into empty tree");
for (int i = 0; i < batch_size+20 ;i++){
    rb_insert(&batch_tree, &nodes[batch_size+i]);
    assert_property_tree_valid(&batch_tree, "batch insertion into empty tree with extra insertions");
}

Case 1: Perfect BST (batch_size = 2ⁿ − 1)

Result: Passes validation, because an all-black perfect tree is a valid red-black tree.

Validated after batch insertion into empty tree (nodes: 127, black_height: 7)
Validated after batch insertion into empty tree with extra insertions (nodes: 128, black_height: 7)
Validated after batch insertion into empty tree with extra insertions (nodes: 129, black_height: 7)
…
Validated after batch insertion into empty tree with extra insertions (nodes: 273, black_height: 7)

Case 2: One Longer Path (batch_size = 2ⁿ)

Result: Fails "single children are red" check after first extra insertion.

Case 3: One Shorter Path (batch_size = 2ⁿ+1)

Result: Fails "single children are red" check after first extra insertion.

Case 4: Case 2 + Case 3 but only check the result after batch_size + 20 insertions

Result: Fails "single children are red" check

---

There is another bug: Property 5 is a consequence of Property 4, so the log output is incorrect.
It currently shows:

Red-Black Tree Properties (The Fundamental 5):
  Property 1 - Node colors (red/black): PASS
  Property 2 - Null nodes are black: PASS
  Property 3 - Red nodes have black children: PASS
  Property 4 - Black height consistency: PASS
  Property 5 - Single children are red: FAIL

However, if Property 5 fails, then Property 4 (black height consistency) should also fail.

[devarajabc]

Since rb_validation_t initializes every property to true by default:

/* Initialize all 5 fundamental properties as valid */
        .node_colors = true,
        .null_nodes_black = true,
        .red_children_black = true,
        .black_height_consistent = true,
        .single_child_red = true,

the code can report false positives if a property has not actually been validated or if validation is interrupted part-way through. The function currently returns as soon as it detects a failure, so some tests may never run, leaving their default value of true unchanged.

To prevent this, the result type should support an additional state such as NONE or NOT_YET to indicate that validation is incomplete.

But it will change the whole testing logic