Question

must be coded in c++ without any STL libraries sadly :( so im struggling on this problem, any help would be greatly appreciated, thanks in advance! :) assignment is due tomorrow and im really struggling on this last question :(

a. Begin by implementing a BST for integers. The underlying structure is a linked list. You
need these methods:
i. BST(); -- Constructor
ii. void put (int) – Inserts a value into the BST.
iii. Void put(int[] a) – Inserts an entire array ‘a’ into the BST.
iv. int search(int key) – Searches for a value in the BST. If found, return the key. If
not found, return 0 and print ‘Value not found!’ to the console. Additionally, print out the total number of comparisons needed (whether the key is found or
not).
v. int returnSize(); -- returns the total number of nodes in the BST.
See Slides 3-10 on Binary Search Trees to see how a BST might be structured with these
methods. The implementation is effectively the same as shown.
b. Now, we will attempt to balance the tree after the values have been inserted.
Implement these methods:
i. int[] a sortedTree(); -- Outputs the tree in sorted order of an array.
ii. BST balanceTreeOne(); -- Balances the tree by creating a new BST and inserting
the values of the sorted array in a way such that the tree height is balanced.
Linear insertion of the sorted values would be the worst possible height.
c. During Red-Black Trees, we discussed the concept of ‘rotations’. Rotations of a node
involve pushing a node to the left or right and reconnecting the parent/children nodes.
Please see Slides 26-29 of the Balanced Search Tree lectures to see what occurs in
rotations. Implement these methods for your BST:
i. Node rotateRight(Node h) – Rotates a given node h to the right and returns the
new parent node after rotation. See the Slides for detail.
1. Note! You need to update the code here to cancel the function if there
are no left subchildren!
ii. Node rotateLeft(Node h) – Rotates a given node h to the left and returns the
new parent node after rotation. See the slides for detail.
1. Note! You need to update the code here to cancel the function is there
are no right subchildren!
iii. void transformToList(); -- Performs a series of right rotations on the BST until
the BST is just a linked list oriented to the right. The logic is like so:
1. Begin at the root, and check if there are left subchildren. If there are,
rotate the root to the right.
2. If the root *still* has left children after rotating, continue rotating right
until there are no more left children at the root.
3. Move to the right. Check if this parent node has left children. If so,
rotateRight on the parent. Continue doing so until there are no more
left children.
4. Repeat all the way down until there are no more nodes that have left
children. The tree is now a right-leaning linked list.
d. We will now attempt to balance the BST without creating new memory, as we did in
Part b. Implement these methods:
i. void balanceTreeTwo(); -- Restructures the BST. It will do this by following this
logic:
1. First, restructure the tree by calling transformToList(); to turn it into a
right-leaning linked list.
2. Compute the parameter ? = (? + 1) − 2
⌊log2 ?⌋
.
a. N is the total number of nodes, ⌊log2 ?⌋ means to compute the
floor of log2 ?.
3. From the root of the tree (which is now a right-leaning linked list),
perform left rotations on every odd node until ? odd nodes have been
rotated.
a. Example: Imagine a list 0->1->2->3->4. If ? = 2, then we
perform rotateLeft() on the ‘0’ node and the ‘2’ node. That’s
exactly ? odd nodes.
4. Compute the parameter ? = ⌊log2 ?⌋ − 1.
5. For K times, compute left rotations on the remaining right-leaning odd
nodes.
a. In the example list above, we did left rotations on 2 odd nodes.
If we ignore the new left links and just look at the right links, we
have 1->3->4. We would do left rotations on 1 and 4.
6. Congratulations, the tree is now balanced!
e. Include a PDF, Problem2.PDF. Include these parts:
i. How does the algorithm of balanceTreeTwo(); balance the tree -- why does this
work? Explain it for all steps.
ii. What is the total time complexity of the balanceTreeOne(); function in the
average case? Consider how this function worked. balanceTreeOne(); first calls
sortedTree(); then creates a new BST out of that. The cost of this should be
?(??????????????) = ?(??????????) + ?(???(???[?])). You will fill this in
for the actual values.
iii. What is the space complexity of the balanceTreeOne(); function?
iv. What is the total time complexity of the balanceTreeTwo(); function? Perform a
similar analysis to I, where you sum up the cost of the internal operations.
v. What is the space complexity of balanceTreeTwo();?

Answer 1

bst.cpp

#include<iostream>

using namespace std;

//binary tree structure

struct Node

{

int data;

struct Node *left,*right;

};

class BST

{

public :

Node *root;

BST() //constructor (i)

{

root=NULL;

}

//Create a node

Node *newNode(int num)

{

Node *newnode=new Node;

newnode->data=num;

newnode->left=newnode->right=NULL;

return newnode;

}

//Recursive method to insert in BST

Node * insert(Node *root,int data) //insert in Binary search Tree

{

Node *newnode=newNode(data);

if(root==NULL)

{

root=newnode;

return root;

}

if(root->data>data)

root->left=insert(root->left,data); //insert in left if data is less than root data **change this line in your algorithm

else

root->right=insert(root->right,data); //insert in right if data is greater than root data ** change this line your algorithm

  

return root;  

}

//insert a num in BST (ii)

void put(int num)

{

root=insert(root,num);

}

//insert array in BST (iii)

void put(int a[])

{

while(*(a+1))

{

root=insert(root,*a);

a++;

}

}

//inorder recursive method

void inorderRec(Node *root)

{

if(root)

{

inorderRec(root->left);

cout<<root->data<<" ";

inorderRec(root->right);

}

}

//recursive method to search num in BST

int searchRec(Node *root,int num)

{

if(root==NULL)

return 0;

if(root->data==num)

return root->data;

if(root->data>num)

return searchRec(root->left,num);

  

return searchRec(root->right,num);

}

//recursive function to find size of tree

int nodeCount(Node *root)

{

if(root==NULL)

return 0;

return 1+nodeCount(root->left)+nodeCount(root->right);  

}

int returnSize() //return size (v)

{

return nodeCount(root); //return recursively

}

int search(int key) //search key (iv)

{

return (searchRec(root,key)); //search number recursively

}

void inorder()

{

inorderRec(root); //print inorder recursively

}

};// end of class BST

int main()

{

BST ob;

ob.put(15); //insert in binary search tree

int a[]={9,30,51,23,11,5,7,10};

ob.put(a);//insert array in binary search tree

cout<<" Binary Search tree inorder : ";

ob.inorder(); //print inorder to check data in tree

if(ob.search(23)) //search function

cout<<"\n 23 found in Binary Search Tree";

else

cout<<"\n Not found Binary Search Tree";

if(ob.search(90))

cout<<"\n 23 found in Binary Search Tree";

else

cout<<"\n 90 Not found Binary Search Tree";   

cout<<"\n Number of nodes in Binary Search Tree : "<<ob.returnSize(); //return size of Binary search Tree

return 0;

}

OUTPUT

Binary Search tree inorder : 5 7 9 10 11 15 23 30 51
23 found in Binary Search Tree
90 Not found Binary Search Tree
Number of nodes in Binary Search Tree : 9