data-structures - 验证红黑树
问题描述
我正在尝试验证二叉树是否是红黑树。我需要检查的一些属性是:
- 根是黑色的
- 不能有 2 个连续的红色节点。
- 您需要添加空节点作为叶子节点,其颜色为黑色。
- 从叶子到根的每条路径都包含相同数量的黑色节点
不知何故,我的测试用例都通过了,但我确信我没有实现上面的数字 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
解决方案
好吧,您需要保留一个柜台:
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
像这样的东西应该工作。(在我的回答中,最左边的路径被访问了两次,第一次是获取见证计数器,第二次是因为我不想编写复杂的代码而不是第二次访问它)
推荐阅读
- bash - 无法读取 bash 管道中的所有文件行
- python - Pad_Sequences 获取 max_len 的多个参数(Keras)
- vue.js - Vue:绑定 img src 不起作用,但硬编码它起作用
- r - 闪亮的 UI 和服务器循环
- html - ng-repeat 数据闪烁然后消失
- android - android.support.design.button.MaterialButton 抛出 InflateException
- python - 如何在 Python 中将值数组插入符号函数
- pointers - Frama-c 无法证明 `char*` 以外类型的缓冲区指针的有效性
- android - 在 React Native For Android 中添加文档扫描仪
- javascript - 从 firebase 获取多个数据并将其存储在表中