赤黒木ならば葉までの黒ノード数を返し
赤黒木でないならば0を返す関数で考えると
・自分が葉ならば1を返す
・自分が赤ノードならば左右に赤ノードがあればNG(0を返す)
・右左の子に対して再帰
・左右の子いずれかが赤黒木でない場合はNG
・再帰関数の結果が左右で異なる場合はNG
・自分が黒ノードならば1を増やす
・結果を返す
という処理になります。
以下、サンプルプログラムです。
int is_rb_tree(Node *node)以外は確認用に作ったものなので
かなり無理やりです
(一応、Wikipedia「赤黒木」の初めにある図を作成しています)
----------
#include <stdio.h>
// 色
#define BLK 0
#define RED 1
typedef struct _Node {
int col;
int value;
struct _Node *left;
struct _Node *right;
} Node;
// 赤黒木判定関数
// 戻り値: 1以上…自ノードから葉までの黒ノード数 0…赤黒木でない
int is_rb_tree(Node *node)
{
int cnt_l, cnt_r;
int ret;
// 葉チェック
if (node == NULL) return 1;
// 赤→赤チェック
if (node->col == RED) {
if (node->left != NULL && node->left->col == RED) return 0;
if (node->right != NULL && node->right->col == RED) return 0;
}
// 数字の大小チェック
if (node->left != NULL && node->left->value > node->value) return 0;
if (node->right != NULL && node->right->value < node->value) return 0;
// 左右の赤黒木チェック
cnt_l = is_rb_tree(node->left);
if (cnt_l == 0) return 0;
cnt_r = is_rb_tree(node->right);
if (cnt_r == 0) return 0;
// 左右の葉までの黒数比較
if (cnt_l != cnt_r) return 0;
ret = cnt_l;
// 自ノードが黒なら+1
if (node->col == BLK) ret++;
return ret;
}
void add_node(Node *node, Node *left, int value_l, Node *right, int value_r)
{
int col_next = node->col == BLK ? RED : BLK;
if (node == NULL) return;
// left
node->left = left;
if (left != NULL) {
left->value = value_l;
left->col = col_next;
left->left = NULL;
left->right = NULL;
}
// right
node->right = right;
if (right != NULL) {
right->value = value_r;
right->col = col_next;
right->left = NULL;
right->right = NULL;
}
}
int main()
{
Node nodes[10];
int ret;
nodes[0].col = BLK; nodes[0].value = 13;
add_node(&nodes[0], &nodes[1], 8, &nodes[2], 17);
add_node(&nodes[1], &nodes[3], 1, &nodes[4], 11);
add_node(&nodes[2], &nodes[5], 15, &nodes[6], 25);
add_node(&nodes[3], NULL, 0, &nodes[7], 6);
add_node(&nodes[6], &nodes[8], 22, &nodes[9], 27);
ret = is_rb_tree(&nodes[0]);
printf("%d\n", ret);
return 0;
}
