algorithm - 红黑树包含过多的黑色节点和过少的红色节点

Question

这是我在这里提出的问题的进一步

Difficulty in writing Red Black Tree in 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 个叶节点的树。

这正常吗？这棵树的红色节点这么少？

我编写了一个函数来根据 3 条规则验证树是否有效(根始终为黑色，所有分支的黑色高度相同，红色节点没有红色子节点)，我的方法表明生成的树确实有效。

1. 黑色节点太多的问题是某些分支充满了黑色节点，如果我尝试删除一个节点，那么旋转无助于平衡树并且该分支的黑色高度总是更少比树的其他分支。

所以我的问题是……红黑树的红色节点太少正常吗？在那种情况下，你如何在删除的情况下保持树平衡？

Answer 1

没有“太多的黑节点”这样的事情。完全没有红色节点意味着树是最平衡的。将新的红色节点引入全黑树会增加其不平衡性(起初)。

在全黑树中删除黑色节点时，您将遵循删除算法，以确保保留属性。