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
- 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.
- 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?