验证红黑树

Question

我正在尝试验证一个二叉树是否为红黑树。需要检查的一些属性包括：

1. 根节点为黑色
2. 不能有连续的红色节点。
3. 您需要添加空节点作为叶子节点，其颜色取为黑色。
4. 从叶子到根的每条路径上包含相同数量的黑节点

我的所有测试用例都通过了，但我确定我没有实现上面的第4个要求。

如何检查从根到 Empty（末端）的任何深度是否具有相同数量的黑色节点？

我将我的树定义为：

type 'a tree = Empty | T of color * 'a tree * 'a * 'a tree 

我的代码通过与一些不良情况进行匹配来判断当前树的状态，如果匹配，则返回false。否则，在左右分支上调用递归函数。

let rec good_RB t = match t with
   | Empty -> true
   | T (R, T (R, _, _, _), _, _)
   | T (R , _, _, T (R, _, _, _)
     -> false
   | T (_, lft, _, rgt) -> good_RB lft && good_RB rgt

- Adam Ralphus

---

实际上第四个测试是：从叶子到根的每条路径包含相同数量的黑节点。 - Lhooq

我修改了你的代码，添加了“Empty”情况。 - Lhooq

@Lhooq 谢谢你的帮助。 - Adam Ralphus

Answer 1

好的，您需要设置一个计数器：

let rec nb_blacks_lftmst acc = function
  | Empty -> acc
  | T (c, lft, _, _) ->
    nb_blacks_lftmst (match c with R -> acc | B -> acc + 1) lft

let good_count = function
  | Empty -> true
  | T (_, lft, _, rgt) ->
    let cpt = nb_blacks_lftmst 0 lft in
    let rec aux acc = function
      | Empty -> acc = cpt
      | T (c, lft, _, rgt) ->
        let acc = match c with R -> acc | B -> acc + 1 in
        aux acc lft && aux acc rgt
    in
    aux 0 lft && aux 0 rgt

像这样应该可以正常工作。（在我的答案中，最左侧的路径被访问了两次，第一次是为了获取证人计数器，第二次是因为我不想编写复杂的代码来避免第二次访问它）

- Lhooq