Description : As you know, when you insert values to a tree, the values greater
ID: 3716609 • Letter: D
Question
Description:
As you know, when you insert values to a tree, the values greater will go to the right side and the values smaller go to the left side. The tree will be extremely skewed if you insert values in the order from the smallest to the largest or from the largest to the smallest. For example, if you insert 31 values 1, 2, 3, …, 31 in the listed order, the tree will look like:
The tree becomes a list (with the depth of 30) and it is not optimized for the search.
Your task is to write a member function to optimize the tree to make the depth of the tree to be (Log2(n+1))-1 (n is the number of nodes). For example, the above tree will be optimized to:
You can see the depth of the tree becomes 4. The tree of this structure is the best for the search. Please keep it in mind: your optimizing algorithm should not be hardcoded and should be able to apply to all binary trees regardless the content of the trees.
Instruction and Test:
Develop an algorithm and implement it in a public member function called Optimize() with void return. To test your code, insert following code into your main function:
Tree<int> optTree;
int depth;
for(int i=1; i<32; i++){ //insert values 1,2,3,..., 31
optTree.insertNode(i);
}
optTree.inOrderTraversal(); //you will output 1 2 3 ... 31
std::cout << std::endl;
std::cout << "The depth of the tree is: " << optTree.getDepth() << std::endl;
//you will output 30 as the depth
optTree.Optimize();
optTree.inOrderTraversal(); //you will output 1 2 3 ... 31
std::cout << std::endl;
std::cout << "The depth of the tree after optimized is: " << optTree.getDepth() << std::endl;
//the output depth will be 4
Explanation / Answer
// OptmizeTree.cpp
#include<iostream>
#include<stdlib.h>
using namespace std;
// Creates a class for Node
class Node
{
public:
int data;
Node *leftLink;
Node *rightLink;
int height;
};// End of structure
// Function to get maximum of two integers
int max(int, int);
// Function to get height of the tree
int height(Node *temp)
{
// Checks if node temp is null then return zero as height
if (temp == NULL)
return 0;
// Otherwise return the height
return temp->height;
}// End of function
// A utility function to get maximum of two integers
int max(int first, int second)
{
return (first > second)? first : second;
}// End of function
// Function that allocates a new node with the given keyValue and NULL left and right pointers.
Node* createNewNode(int keyValue)
{
// Creates a new node
Node* newNode = new Node();
// Assigns parameter data
newNode->data = keyValue;
// Assigns left and right link to null
newNode->leftLink = NULL;
newNode->rightLink = NULL;
// new node is initially added at leaf
newNode->height = 1;
// Returns the root
return(newNode);
}// End of function
// Function to insert a new node with given keyValue
Node* insertNode(Node* newNode, int keyValue)
{
// Checks if the tree is empty, return a new node
if (newNode == NULL)
return (createNewNode(keyValue));
// Otherwise, recur down the tree
if (keyValue < newNode->data)
newNode->leftLink = insertNode(newNode->leftLink, keyValue);
else if (keyValue > newNode->data)
newNode->rightLink = insertNode(newNode->rightLink, keyValue);
// return the (unchanged) node pointer
return newNode;
}// End of function
// Function to right rotate subtree rooted with tempNode See the diagram given above.
Node *rightRotate(Node *tempNode)
{
Node *leftL = tempNode->leftLink;
Node *T2 = leftL->rightLink;
// Perform rotation
leftL->rightLink = tempNode;
tempNode->leftLink = T2;
// Update heights
tempNode->height = max(height(tempNode->leftLink), height(tempNode->rightLink))+1;
leftL->height = max(height(leftL->leftLink), height(leftL->rightLink))+1;
// Return new root
return leftL;
}// End of function
// A utility function to left rotate subtree rooted with tempNode See the diagram given above.
Node *leftRotate(Node *tempNode)
{
Node *leftL = tempNode->rightLink;
Node *T2 = leftL->leftLink;
// Perform rotation
leftL->leftLink = tempNode;
tempNode->rightLink = T2;
// Update heights
tempNode->height = max(height(tempNode->leftLink), height(tempNode->rightLink))+1;
leftL->height = max(height(leftL->leftLink), height(leftL->rightLink))+1;
// Return new root
return leftL;
}// End of function
// Function to get Balance factor of node tempNode
int getBalance(Node *tempNode)
{
// Checks if the temp node is null return null
if (tempNode == NULL)
return 0;
// Otherwise return subtract value of height right link from height left link
return height(tempNode->leftLink) - height(tempNode->rightLink);
}// End of function
// Recursive function to insert keyValue in subtree rooted with newNode and returns new root of subtree.
Node* insertOptimize(Node* newNode, int keyValue)
{
// Perform the normal BST insertion
if (newNode == NULL)
return(createNewNode(keyValue));
// Checks if parameter key value is less than the newNode data
if (keyValue < newNode->data)
// Recursively calls the function with left child
newNode->leftLink = insertOptimize(newNode->leftLink, keyValue);
// Otherwise checks if parameter key value is greater than the newNode data
else if (keyValue > newNode->data)
// Recursively calls the function with right child
newNode->rightLink = insertOptimize(newNode->rightLink, keyValue);
// Equal keys are not allowed in BST
else
return newNode;
// Update height of this ancestor newNode
newNode->height = 1 + max(height(newNode->leftLink), height(newNode->rightLink));
// Get the balance factor of this ancestor newNode to check whether this newNode became unbalanced
int balance = getBalance(newNode);
// If this newNode becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && keyValue < newNode->leftLink->data)
return rightRotate(newNode);
// Right Right Case
if (balance < -1 && keyValue > newNode->rightLink->data)
return leftRotate(newNode);
// Left Right Case
if (balance > 1 && keyValue > newNode->leftLink->data)
{
newNode->leftLink = leftRotate(newNode->leftLink);
return rightRotate(newNode);
}// End of if condition
// Right Left Case
if (balance < -1 && keyValue < newNode->rightLink->data)
{
newNode->rightLink = rightRotate(newNode->rightLink);
return leftRotate(newNode);
}// End of if condition
// return the (unchanged) newNode pointer
return newNode;
}// End of function
// Function for optimizing node
Node * Optimize()
{
Node *root = NULL;
// Loops 31 times
for(int i = 1; i <= 31; i++)
// Calls the function to optimize
root = insertOptimize(root, i);
}// End of function
// Function to print in order traversal of the tree.
void inOrder(Node *root)
{
// Checks if root is not null
if(root != NULL)
{
// Recursively calls the function with left child
inOrder(root->leftLink);
// Displays the root value
cout<<root->data<<" ";
// Recursively calls the function with right child
inOrder(root->rightLink);
}// End of if condition
}// End of function
// Function to compute the "maxDepth" of a tree -- the number of nodes along the longest path from the root root
// down to the farthest leaf root.
int maxDepth(Node* root)
{
// Checks if root is null then return 0 as height
if (root == NULL)
return 0;
// Otherwise
else
{
// Compute the depth of each subtree left
int lDepth = maxDepth(root->leftLink);
// Compute the depth of each subtree right
int rDepth = maxDepth(root->rightLink);
// Finds the largest and returns it
if (lDepth > rDepth)
return(lDepth+1);
else
return(rDepth+1);
}// End of else
}// End of function
// main function definition
int main()
{
// Creates root node
Node *root = NULL;
// Constructing tree
// loops 31 times and inserts the node
for(int i = 1; i <= 31; i++)
root = insertNode(root, i);
cout<<" In-order traversal of the tree is ";
inOrder(root);
cout<<" The depth of the tree is:"<<maxDepth(root);
// Calls the function to optimize
root = Optimize();
cout<<" In-order traversal of the optimize tree is ";
inOrder(root);
cout<<" The depth of the tree is:"<<maxDepth(root);
return 0;
}// End of main function
Sample Output:
In-order traversal of the tree is
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
The depth of the tree is:31
In-order traversal of the optimize tree is
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
The depth of the tree is:5