Difficulty in writing Red Black Tree in F#

Question

I am writing a red black tree in F#. the code which I have written is below. I am facing 2 problems with this code - The rules of balancing the tree state that when the tree has a XYr or rXY type of imbalance I must recolor the 2 parent nodes and IF the grand parent node is not ROOT of the tree then it should be recolored as well. The difficulty here is that in the recursive approach I only get the next node to work on.. so its hard to know what is the root node. - IN order to solve the above, I added another integer called height to my Node type (type node = Node of int * int * color). That made my pattern matching code in balanceTree function pretty long... but the problem is that when I recolor the grandparent the tree becomes imbalanced because the grand-grand-parent and grand-parent can be red in color which is not allowed. Can someone recommend a clean way of resolving the issue. ``` type Color = | R | B type tree = | Node of int * Color * tree * tree | Empty let countNodes tree…

Accepted Answer

Standard ML-style implementation in F# looks like this:

```
type color = R | B
type 'a tree = E | T of color * 'a tree * 'a * 'a tree

let insert x s = 
  let rec ins = function
    | E                  -> T (R,E,x,E)
    | T (col,a,y,b) as s ->
        if x < y then
          balance (col, ins a, y, b)
        elif x > y then
          balance (col, a, y, ins b)
        else
          s
  match ins s with
  | T (_,a,y,b) -> T (B,a,y,b)
  | t -> t
```

Difficulty in writing Red Black Tree in F#

Solution

Problem