Question
I need answers to this question. please help me.
5.1 (20 points) Give a pseudocode for an efficient algorithm that given a binary tree T, the nodes of which are colored red or black, checks if T is a red-black tree. In case it detects that the input tree is not a red-black tree, it should provide a reason for that (e.g. the tree is not a BST, the root is not black a red node has a red child, or paths from a node to descendant leaves contain different number of blaclk nodes). Analyze the running time of the algorithm. The proposed algorithm should have the best possible asymptotic running time. 5.2 (30 points) Implement your algorithm. We will represent binary trees as follows. We will number the positions of a binary tree in the following manner (level by level, left to right) 6 17 18 19 20 21 22 23 24 25 That is, the nodes are numbered as one would encounter them when traversing the tree breadth-first. The specification of a tree will be as (position, value,color), where position and value are numbers, and color cE [r, b). For example the sequence (1,65.b (2.50) 3,80,b) (4,10,b) (5,60,b) (6,70. (8,5) (,62.r) represents the following tree: equence of triplets. Each triplet has the fo Notice, that the specification contains only internal nodes of the tree. The leaves (black nil nodes) are not listed in the specification Notice, that internal node with position i has parent at position i/2 (integer division), left child at position 2i, and right child at position 2i+1 You may assume that triplets are separated by spaces and there are no spaces inside triplets Assume that in any sequence representing a tree the triplets will be listed in order of increasing position numbers. Assume that values of the keys are integers from 1 to 10(incluive). You do not need to check for correctness of the input. You may assume that the input is always correct, that is, it does correspond to a binary tree with nodes colored red or black. Your program should read the tree specification from a file, convert it into a binary tree with colored nodes, check whether the tree is a red-black tree, and output its answer. If the tree is not a red-black tree then it should provide a reason for that as mentioned earlier The following are sample files with tree specifications: trestxt- a red-black tree treeL.txt not a red-black tree because it is not a BST tree2.txt- not a red-black tree because a red node has a red child tree3ixt- not a red-black tree because paths from a node to descendant leaves contain different number of black nodes
Explanation / Answer
PROPERTIES OF RED BLACK TREES:
How to check them?
1)check if any node is not either red or black then it is nor RB tree
2) check if the root is black. If(root==black)
3) for each x whose x.CHILD==Null should be of black color.
4) if x.CHILD is red, the check that x.LEFT.CHILD and x.RIGHT.CHILD are black.
5) check that the number of black nodes in each subtree is the same.
** Check that the tree is a binary tree as well.
##TO check black height is same or not
#define RED 0
#define BLACK 1 // define red color as 0 and black color as 1
struct RBTree {
int data;
struct rbt *left;
struct rbt *right;
int p_color; // parent color
int nodes_count; // to store number of nodes present including self
int level; // to store level of each node
};
typedef struct RBTree RBTree_t;
int check_rbt_black_height(RBTree_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(" Black nodes are not same”);
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(RBTree_t *root)
{
if(root && root->p_color == RED) return 1;
return 0;
}
