Учитывая красно-черное дерево, мне нужно написать эффективный алгоритм, который проверяет, содержат ли для каждого узла все пути от узла до дочерних листьев одинаковое количество черных узлов, т. е. алгоритм должен возвращать логическое значение, если свойство истинно, или ложно в противном случае.
Как проверить черную высоту узла для всех путей к его дочерним листьям?
comment
Вы можете начать с ослабления проблемы: что, если она не должна быть эффективной, а просто правильной?
- person Scott Hunter   schedule 13.12.2012
Ответы (2)
Это вернет черную высоту RB-дерева. Если высота равна 0, дерево является недопустимым красно-черным деревом.
int BlackHeight(NodePtr root)
{
if (root == NULL)
return 1;
int leftBlackHeight = BlackHeight(root->left);
if (leftBlackHeight == 0)
return leftBlackHeight;
int rightBlackHeight = BlackHeight(root->right);
if (rightBlackHeight == 0)
return rightBlackHeight;
if (leftBlackHeight != rightBlackHeight)
return 0;
else
return leftBlackHeight + root->IsBlack() ? 1 : 0;
}
person
healthy
schedule
12.12.2012
Я не понимаю обозначения в последней строке со знаком вопроса и двоеточием... не могли бы вы пояснить?
- person Georges Krinker; 13.12.2012
Прочитайте это как оператор if, если это проще!
- person Black Jack 21; 18.11.2018
Ниже код проверяет, одинаково ли количество черных узлов на любом пути
#define RED 0
#define BLACK 1
struct rbt {
int data;
struct rbt *left;
struct rbt *right;
int parent_color; // parent link color
uint64_t nodes_count; // to store number of nodes present including self
int level; // to store level of each node
};
typedef struct rbt rbt_t;
int check_rbt_black_height(rbt_t *root)
{
if(!root) return 1;
else {
int left_height = check_black_violation(root->left);
int right_height = check_black_violation(root->right);
if (left_height && right_height && left_height != right_height) {
printf("Error: Black nodes are not same @level=%d\n", root->level);
exit(1);
}
if (left_height && right_height)
// do not increment count for red
return is_color_red(root) ? left_height : left_height + 1;
else
return 0;
}
}
int is_color_red(rbt_t *root)
{
if(root && root->parent_color == RED) return 1;
return 0;
}
person
Rajendra
schedule
13.11.2013