Red Black Tree contains too many black nodes and too few red nodes

Question

This is further to the question I had asked here

Difficulty in writing Red Black Tree in F#

Based on previous inputs, I have created this program.

open System;

type Color = | R | B 

type tree = 
    | Node of int * Color * tree * tree
    | Leaf

let blackHeight tree = 
    let rec innerBlackHeight accm = function
        | Leaf -> accm + 1
        | Node(_, B, l, r) -> List.max [(innerBlackHeight (accm + 1) l); (innerBlackHeight (accm + 1) r)]
        | Node(_, R, l, r) -> List.max [(innerBlackHeight accm l); (innerBlackHeight accm r)]        
    innerBlackHeight 0 tree    

let isTreeBalanced tree = 
    let rec isBlackHeightSame = function
        | Node(n, c, l, r) -> 
            if (blackHeight l) = (blackHeight r) then 
                true && (isBlackHeightSame l) && (isBlackHeightSame r)
            else 
                false
        | Leaf -> true
    let isRootBlack = function
        | Node(n, c, _, _) -> 
            if c = B then 
                true 
            else 
                false
        | _ -> false
    let rec twoConsequtiveReds = function
        | Leaf -> true
        | Node(_, R, Node(_, R, _, _), _) -> false
        | Node(_, R, _, Node(_, R, _, _)) -> false
        | Node(_, _, l, r) -> (twoConsequtiveReds l) && (twoConsequtiveReds r)

    ((isBlackHeightSame tree) && (isRootBlack tree) && (twoConsequtiveReds tree))

let balance  = function 
    | Node (gpn, B, Node(pn, R, Node(cn, R, a, b), c), d) -> Node(pn, R, Node(cn, B, a, b), Node(gpn, B, c, d))
    | Node (gpn, B, a, Node(pn, R, b, Node(cn, R, c, d))) -> Node(pn, R, Node(gpn, B, a, b), Node(cn, B, c, d))
    | Node (gpn, B, Node(pn, R, a, Node(cn, R, b, c)), d) -> Node(cn, R, Node(pn, B, a, b), Node(gpn, B, c, d))
    | Node (gpn, B, a, Node(pn, R, Node(cn, R, b, c), d)) -> Node(cn, R, Node(gpn, B, a, b), Node(pn, B, c, d))    
    | Node (n, c, l, r) -> Node(n, c, l, r)
    | _ -> failwith "unknown pattern"

let rec insert x tree = 
    let rec insertInner = function
        | Node(n, c, l, r) when x < n -> balance (Node(n, c, insertInner l, r))
        | Node(n, c, l, r) when x > n -> balance (Node(n, c, l, insertInner r))
        | Node(n, c, l, r) as node when x = n -> node
        | Leaf -> Node(x, R, Leaf, Leaf)
        | _ -> failwith "unknown pattern"
    match (insertInner tree) with
    | Node(n, _, l, r) -> Node(n, B, l, r)
    | t -> t

let rec findLowest = function
    | Node(n, _, Leaf, _) -> n
    | Node(_, _, l, _) -> findLowest l
    | _ -> failwith "Unknown pattern"

let rec countNodes = function
    | Node(_, c, l, r) -> 
        let (x1, y1, z1) = countNodes l
        let (x2, y2, z2) = countNodes r
        if c = B then
            (1 + x1 + x2, y1 + y2, z1 + z2)
        else
            (x1 + x2, 1 + y1 + y2, z1 + z2)
    | Leaf -> (0, 0, 1)

let rec delete x tree = 
    let rec innerDelete = function
        | Node(n, c, l, r) when x < n -> balance (Node(n, c, innerDelete l, r))
        | Node(n, c, l, r) when x > n -> balance (Node(n, c, l, innerDelete r))
        | Node(n, c, Leaf, Leaf) when x = n -> Leaf
        | Node(n, c, l, Leaf) when x = n -> balance l
        | Node(n, c, Leaf, r) when x = n -> balance r
        | Node(n, c, l, r) when x = n ->  balance (Node((findLowest r), c, l, r))
        | _ -> failwith "unexpected pattern"
    match (innerDelete tree) with
    | Node(n, _, l, r) -> Node(n, B, l, r)
    | t -> t

let generateNums n = 
    seq {for i in 0 .. n - 1 -> i}

[<EntryPoint>]
let main args = 
    let mutable tree = Leaf
    for i in generateNums 100000 do 
        tree <-insert i tree    
    printfn "%A" tree
    printfn "%i" (blackHeight tree)
    printfn "%b" (isTreeBalanced tree)
    let (bc, rc, lc) = countNodes tree
    printfn "black nodes %i red nodes %i leaf nodes %i" bc rc lc
    0

The problems which I am facing is

1. For a tree of 0 to 99999 it produces a tree with 99994 black nodes 6 red nodes and 100001 leaf nodes.

Is this normal? that the tree has so few red nodes?

I have written a function to validate if the tree is valid based on the 3 rules (root is always black, black height is same for all branches and red nodes don't have red children) and my method says that the generated tree is indeed valid.

2. the problem with too many black nodes is that is that certain branches are full of black nodes and if i try to delete a node, then rotations don't help in balancing the tree and the black height of that branch is always less than the other branches of the tree.

So my questions are... is it normal for a red black tree to have too few red nodes? in that case how do you keep the tree balanced in case of deletions?

Answer 1

There's no such thing as "too many black nodes". No red nodes at all means the tree is the most balanced. Introducing new red nodes into an all-black tree increases its imbalance (at first).

When deleting a black node in an all-black tree you follow the deletion algorithm, which ensures that the properties are preserved.