Красно-черное дерево содержит слишком много черных узлов и слишком мало красных узлов

Это продолжение вопроса, который я задал здесь

Сложность при написании Red Black Tree на F #

Основываясь на предыдущих материалах, я создал эту программу.

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

Проблемы, с которыми я сталкиваюсь, это

1. Для дерева от 0 до 99999 он создает дерево с 99994 черными узлами, 6 красными узлами и 100001 листовыми узлами.

Это нормально? что в дереве так мало красных узлов?

Я написал функцию для проверки правильности дерева на основе трех правил (корень всегда черный, высота черного одинакова для всех ветвей, а красные узлы не имеют красных дочерних элементов), и мой метод говорит, что сгенерированное дерево действительно действительный.

2. проблема со слишком большим количеством черных узлов заключается в том, что некоторые ветви заполнены черными узлами, и если я попытаюсь удалить узел, то вращения не помогут сбалансировать дерево, а высота черного этой ветви всегда меньше, чем у другой. ветви дерева.

Итак, мои вопросы ... нормально ли, что на красно-черном дереве слишком мало красных узлов? в таком случае, как сохранить баланс дерева в случае удалений?