CSE 2320 Lab Assignment 4 Due August 6, 2018 Goals: 1. Understanding of red-blac
ID: 3918941 • Letter: C
Question
CSE 2320 Lab Assignment 4 Due August 6, 2018 Goals: 1. Understanding of red-black tree structural constraints 2. Application of recursion. Requirements: 1. Write a linear-time program to test whether a binary tree satisfies the red-black tree properties. The simple input format corresponds to preorder traversal. An "R" corresponds to a red tree node, a "B" to a black tree node, and a""to the sentinel. If a tree includes n data nodes, then the sentinel will be processed n + 1 times. The input ABC D EF GH IJ corresponds to the tree GH IJK (This line is not part of the input) Submit your program on Blackboard by 1245 pim on August 6. One of the comment lines should indicate the compilation command used on OMEGA 2. Getting Started: I. The following test cases are useful BRB..B. .BR..R.. BBRB. . B..BR..R. .BB..BR. .RB..B. 2. Your program may print any debugging information that you choose, but the last line of your output should indicate from your data whether or not the tree satisfies the red-black tree properties. Your program must echo the tree recursively structure. Likewise, your code for reading the tree must be recursive 3. Your program should not prompt for an input file name. The maximum length for the input string is 200 symbols 4. Pointers are not necessary for implementing this assignment. Simple tables are sufficient.Explanation / Answer
The below code will output from entered nodes whether tree is balance like Red Black or not:
CODE:
/* Program to check if a given Binary Tree is balanced like a Red-Black Tree */
#include <iostream>
using namespace std;
struct Node
{
int key;
Node *left, *right;
};
/* utility that allocates a new Node with the given key */
Node* newNode(int key)
{
Node* node = new Node;
node->key = key;
node->left = node->right = NULL;
return (node);
}
// Returns returns tree if the Binary tree is balanced like a Red-Black
// tree. This function also sets value in maxh and minh (passed by
// reference). maxh and minh are set as maximum and minimum heights of root.
bool isBalancedUtil(Node *root, int &maxh, int &minh)
{
// Base case
if (root == NULL)
{
maxh = minh = 0;
return true;
}
int lmxh, lmnh; // To store max and min heights of left subtree
int rmxh, rmnh; // To store max and min heights of right subtree
// Check if left subtree is balanced, also set lmxh and lmnh
if (isBalancedUtil(root->left, lmxh, lmnh) == false)
return false;
// Check if right subtree is balanced, also set rmxh and rmnh
if (isBalancedUtil(root->right, rmxh, rmnh) == false)
return false;
// Set the max and min heights of this node for the parent call
maxh = max(lmxh, rmxh) + 1;
minh = min(lmnh, rmnh) + 1;
// See if this node is balanced
if (maxh <= 2*minh)
return true;
return false;
}
// A wrapper over isBalancedUtil()
bool isBalanced(Node *root)
{
int maxh, minh;
return isBalancedUtil(root, maxh, minh);
}
/* Driver program to test above functions*/
int main()
{
Node * root = newNode(10);
root->left = newNode(5);
root->right = newNode(100);
root->right->left = newNode(50);
root->right->right = newNode(150);
root->right->left->left = newNode(40);
isBalanced(root)? cout << "Balanced" : cout << "Not Balanced";
return 0;
}
Output: Balanced
Note: Reference Taken from https://ide.geeksforgeeks.org