难度书面红黑树在F＃ [英] Difficulty in writing Red Black Tree in F#
本文介绍了难度书面红黑树在F＃的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我写一个红黑树在F＃中。
我已经写了code是如下。我现在面临两个问题与此code
- 平衡树的状态的，当树有一个XYR或RXY型的不平衡，我必须重新着色的2父节点和IF盛大的父节点不是树，那么它应该被重新着色，以及根的规则。
这里的困难是，在递归的方法，我只能得到下一个节点上工作..所以它很难知道什么是根节点。
- 在为了解决上述，我增加了一个整数叫高度，我的节点类型（节点类型=节点为int *为int *的颜色）。这使我的模式匹配code在balanceTree功能pretty的长... ...但问题是，当我重新着色的祖父母树变得不平衡，因为盛大，盛大的父母和大父母能够红色的这是不允许的。
有人可以推荐解决问题的清洁方式。
键入颜色=
| ř
|乙
类型树=
|对INT *色* *树树节点
|空洞
让countNodes树=
让REC incrCount =功能
|空 - ＆GT; 0
|节点（_，_，N1，N2） - ＆GT; 1+（incrCount N1）+（incrCount n2）的
incrCount树
让isTreeValid树=
让getTreeBlackNodeHeight树=
让REC getNodeHeight ACC =功能
|空 - ＆GT; ACC + 1
|节点（_中，R中，n1，_） - ＆GT; getNodeHeight ACC N1
|节点（_，乙内，其中n1，_） - ＆GT; getNodeHeight（ACC + 1）N1
getNodeHeight 0树
让isRootNodeBlack =功能
|空 - ＆GT;真正
|节点（_，B，_，_） - ＆GT;真正
|节点（_，R，_，_） - ＆GT;假
让拍摄areAllBlackHeightsSame高度ACC =功能
|空 - ＆GT;
如果（ACC + 1）=身高则为true否则返回false
|节点（_ R，N1，N2） - ＆GT; areAllBlackHeightsSame高度ACC N1和放大器;＆安培; areAllBlackHeightsSame高度ACC N2
|节点（_，乙，N1，N2） - ＆GT; areAllBlackHeightsSame高度（ACC + 1）N1和放大器;＆安培; areAllBlackHeightsSame高度（ACC + 1）N2
让allRedsMustHaveBlackChildren树=
让getRootNodeColor =功能
|空 - ＆GT; Color.B
|节点（_，Y，_，_） - ＆GT; ÿ
让REC checkChildColor =功能
|空 - ＆GT;真正
|节点（_ R，N1，N2） - ＆GT; getRootNodeColor N1 = Color.B和放大器;＆安培; getRootNodeColor N2 = Color.B和放大器;＆安培; checkChildColor N1和放大器;＆安培; checkChildColor N2
|节点（_，乙，N1，N2） - ＆GT; （checkChildColor n1）的＆安培;＆安培; （checkChildColor N2）
checkChildColor树
（areAllBlackHeightsSame（getTreeBlackNodeHeight树）0树）及和放大器; （isRootNodeBlack树）及＆安培; （allRedsMustHaveBlackChildren树）
让我们将x =树
让REC createNode =功能
|空 - ＆GT;如果（countNodes树）= 0，则节点（X，B，空，空）其他节点（X，R，空，空）
|节点（i，C，N1，N2），当x＆GT;我 - ＆GT;节点（I，C，N1，（createNode N2））
|节点（i，C，N1，N2）当X;我 - ＆GT;节点（i，C，（createNode N1），n2）的
|节点（i，_，_，_）当X = 1 - ＆GT; failwith节点已经存在
| _ - ＆GT; failwith未知
createNode树
让colorToggle =功能
| （I，B） - ＆GT; （I，R）
| （I，R） - ＆GT; （I，B）
让balanceTree树=
让REC余额=功能
|节点（GPV，B，节点（P1V，R，节点（C1V，R，A，B），C），节点（P2V，R，D，E）） - ＆GT;平衡（节点（GPV，B，节点（P1V，B，节点（C1V，R，A，B），C），节点（P2V，B，D，E）））
|节点（GPV，B，节点（P1V，R，A，节点（C2V，R，B，C）），节点（P2V，R，D，E）） - ＆GT;平衡（节点（GPV，B，节点（P1V，B，A，节点（C2V，R，B，C）），节点（P2V，B，E，E）））
|节点（GPV，B，节点（P1V，R，A，B），节点（P2V，R，节点（C1V，R，C，D），E）） - ＆GT;平衡（节点（GPV，B，节点（P1V，B，A，B），节点（P2V，B，节点（C1V，R，C，D），E）））
|节点（GPV，B，节点（P1V，R，A，B），节点（P2V，R，C，节点（C2V，R，D，E））） - ＆GT;平衡（节点（GPV，B，节点（P1V，B，A，B），节点（P2V，B，C，节点（C2V，R，D，E））））
|节点（GPV，乙，X4，节点（PV中，R，X1，节点（栽培品种中，R，X2，X3））） - ＆GT;平衡（节点（PV，B节点（GPV中，R，X 4，X 1），节点（栽培品种中，R，X2，X3）））
|节点（GPV，乙，X4，节点（PV中，R，节点（栽培品种中，R，X1，X2），×3）） - ＆GT;平衡（节点（PV，B节点（GPV中，R，X 4，节点（栽培品种，B，X1，X2）），×3））
|节点（GPV，B节点（PV中，R，X1，节点（栽培品种中，R，X2，X3）），4个） - ＆GT;平衡（节点（PV，B，X1，节点（GPV中，R，节点（栽培品种中，R，X2，X3），4个）））
|节点（GPV，B节点（PV中，R，节点（栽培品种中，R，X1，X2），×3），4个） - ＆GT;平衡（节点（PV，B（节点（栽培品种中，R，X1，X2）），节点（GPV中，R，X3，X4）））
|节点（i，X，N1，N2） - ＆GT;节点（i，X，（n1的平衡），（平衡N 2））
|空 - ＆GT;空洞
平衡树
并[d的EntryPoint＆GT]
让主要的args =
//令t1 =节点（（35，B）的节点（（20，R），节点（（10，B）的节点（（5，R），空，空），空），节点（（25， B）中，空，空）），节点（（85，R），节点（（55，B）的节点（（40，R），空，空），节点（（70，R），空，空） ），节点（（100，B）中，空，空）））
让T2 = [1 .. 6] |＆GT; List.fold（ACC乐趣I-＆GT;插入我ACC）空
printfn是树有效期：％B（isTreeValid T2）
让T3 = balanceTree T2
printfn是树有效期：％B（isTreeValid T3）
0
解决方案
在F＃标准ML风格的实现看起来是这样的：
键入颜色= R |乙
类型'一棵树= E | T颜色*的一棵树*'A *'一棵树
让余额=功能
| B，T（R，T（R，A，X，B）中，y，c）中，Z，D
| B，T（R，A，X，T（R，B，Y，C）），Z，D
| B，A，X，T（R，T（R，B，Y，C），Z，D）
| B，A，X，T（R，B，Y，T（R，C，Z，D）） - ＆GT; T（R，T（B，A，X，B），Y，T（B，C，Z，D））
|山坳，A，X，B - ＆GT; T（COL，A，X，B）
让我们将x S =
让REC插件=功能
| Ë - ＆GT; T（R，E，X，E）
| T（COL，A，Y，B）为s - ＆GT;
如果x＆LT; y，则
平衡（COL，INS A，Y，B）
ELIF X - GT; y，则
平衡（COL，A，Y，INS B）
其他
小号
比赛插件s的
| T（_，A，Y，B） - ＆GT; T（B，A，Y，B）
|笔 - ＆GT; Ť
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 =
let rec incrCount = function
| Empty -> 0
| Node(_, _, n1, n2) -> 1 + (incrCount n1) + (incrCount n2)
incrCount tree
let isTreeValid tree =
let getTreeBlackNodeHeight tree =
let rec getNodeHeight acc = function
| Empty -> acc + 1
| Node(_, R, n1, _) -> getNodeHeight acc n1
| Node(_, B, n1, _) -> getNodeHeight (acc + 1) n1
getNodeHeight 0 tree
let isRootNodeBlack = function
| Empty -> true
| Node(_, B, _, _) -> true
| Node(_, R, _, _) -> false
let rec areAllBlackHeightsSame height acc = function
| Empty ->
if (acc + 1) = height then true else false
| Node(_, R, n1, n2) -> areAllBlackHeightsSame height acc n1 && areAllBlackHeightsSame height acc n2
| Node(_, B, n1, n2) -> areAllBlackHeightsSame height (acc + 1) n1 && areAllBlackHeightsSame height (acc + 1) n2
let allRedsMustHaveBlackChildren tree =
let getRootNodeColor = function
| Empty -> Color.B
| Node(_, y, _, _) -> y
let rec checkChildColor = function
| Empty -> true
| Node(_, R, n1, n2) -> getRootNodeColor n1 = Color.B && getRootNodeColor n2 = Color.B && checkChildColor n1 && checkChildColor n2
| Node(_, B, n1, n2) -> (checkChildColor n1) && (checkChildColor n2)
checkChildColor tree
(areAllBlackHeightsSame (getTreeBlackNodeHeight tree) 0 tree) && (isRootNodeBlack tree) && (allRedsMustHaveBlackChildren tree)
let insert x tree =
let rec createNode = function
| Empty -> if (countNodes tree) = 0 then Node(x, B, Empty, Empty) else Node(x, R, Empty, Empty)
| Node(i, c, n1, n2) when x > i -> Node(i, c, n1, (createNode n2))
| Node(i, c, n1, n2) when x < i -> Node(i, c, (createNode n1), n2)
| Node(i, _, _, _) when x = i -> failwith "Node already exists"
| _ -> failwith "unknown"
createNode tree
let colorToggle = function
| (i, B) -> (i, R)
| (i, R) -> (i, B)
let balanceTree tree =
let rec balance = function
| Node(gpv, B, Node(p1v, R, Node(c1v, R, a, b), c), Node(p2v, R, d, e)) -> balance (Node(gpv, B, Node(p1v, B, Node(c1v, R, a, b), c), Node(p2v, B, d, e)))
| Node(gpv, B, Node(p1v, R, a, Node(c2v, R, b, c)), Node(p2v, R, d, e)) -> balance (Node(gpv, B, Node(p1v, B, a, Node(c2v, R, b, c)), Node(p2v, B, e, e)))
| Node(gpv, B, Node(p1v, R, a, b), Node(p2v, R, Node(c1v, R, c, d), e)) -> balance (Node(gpv, B, Node(p1v, B, a, b), Node(p2v, B, Node(c1v, R, c, d), e)))
| Node(gpv, B, Node(p1v, R, a, b), Node(p2v, R, c, Node(c2v, R, d, e))) -> balance (Node(gpv, B, Node(p1v, B, a, b), Node(p2v, B, c, Node(c2v, R, d, e))))
| Node(gpv, B, x4, Node(pv, R, x1, Node(cv, R, x2, x3))) -> balance (Node(pv, B, Node(gpv, R, x4, x1), Node(cv, R, x2, x3)))
| Node(gpv, B, x4, Node(pv, R, Node(cv, R, x1, x2), x3)) -> balance (Node(pv, B, Node(gpv, R, x4, Node(cv, B, x1, x2)), x3))
| Node(gpv, B, Node(pv, R, x1, Node(cv, R, x2, x3)), x4) -> balance (Node(pv, B, x1, Node(gpv, R, Node(cv, R, x2, x3), x4)))
| Node(gpv, B, Node(pv, R, Node(cv, R, x1, x2), x3), x4) -> balance (Node(pv, B, (Node(cv, R, x1, x2)), Node(gpv, R, x3, x4)))
| Node(i, x, n1, n2) -> Node(i, x, (balance n1), (balance n2))
| Empty -> Empty
balance tree
[<EntryPoint>]
let main args =
//let t1 = Node((35, B), Node((20, R), Node((10, B), Node((5, R), Empty, Empty), Empty), Node((25, B), Empty, Empty)), Node((85, R), Node((55, B), Node((40, R), Empty, Empty), Node((70, R), Empty, Empty)), Node((100, B), Empty, Empty)))
let t2 = [1 .. 6] |> List.fold (fun acc i-> insert i acc) Empty
printfn "Is Tree Valid : %b" (isTreeValid t2)
let t3 = balanceTree t2
printfn "is Tree Valid : %b" (isTreeValid t3)
0
解决方案
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 balance = function
| B, T (R, T (R,a,x,b), y, c), z, d
| B, T (R, a, x, T (R,b,y,c)), z, d
| B, a, x, T (R, T (R,b,y,c), z, d)
| B, a, x, T (R, b, y, T (R,c,z,d)) -> T (R, T (B,a,x,b), y, T (B,c,z,d))
| col, a, x, b -> T (col, a, x, b)
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
这篇关于难度书面红黑树在F＃的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
