如何檢查所有路徑的節點的黑色高度到它的派生樹葉？

Question

給定紅黑樹，我需要編寫一個有效的算法，檢查是否爲每個節點，從節點到後代葉子的所有路徑包含相同數量的黑色節點，即算法應該返回一個布爾值，否則爲屬性爲true或false。

Answer 1

它將返回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; 
} 

Answer 2

下面的代碼驗證是否沿任意路徑的黑色節點的數目是相同

#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; 
}