Проверьте красное черное дерево

Question

Я пытаюсь проверить, является ли двоичное дерево красно-черным. Вот некоторые свойства, которые мне нужно проверить:

1. Корень черный
2. Не может быть 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

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

Нечто подобное должно работать. (в моем ответе самый левый путь посещается дважды, первый раз, чтобы получить счетчик свидетелей, второй раз, потому что я не хочу писать сложный код, чтобы не посещать его во второй раз)