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

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 листовых узлов.

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

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

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

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

Answer 1

Нет такой вещи, как «слишком много черных узлов». Никакие красные узлы вообще не означают, что дерево является самым сбалансированным. Введение новых красных узлов в все-черное дерево увеличивает его дисбаланс (сначала).

При удалении черного узла во все черном дереве вы следуете алгоритму удаления, который гарантирует сохранение свойств.