-1down votefavorite I am trying to find the best root for my binary search tree.
ID: 3606230 • Letter: #
Question
-1down votefavorite
I am trying to find the best root for my binary search tree. i.e. this is my binary search tree.
then I save them in an array in the form of inOrder walk.
| 23 | 25 | 41 | 42 | 49 | 53 | 55 |.........
............................................
so the ones pointing the arrows are the nodes that ill try to see which one is the best root 41, 42, 53.(the array can be bigger and ill take the odd indexes of the array with a given Depth of the tree). I know the tree might already be balance but this is an experiment so bare with me please.
So i have to try every single odd index as my new root and compare each height with the previous one and like that i can determine which one is my best hight. i.e. if i decided 25 is my new root i can have a tree like this
so for each I check and compare the height with the previous node in the array and i return the node that it will give me the best node. So far i tried this:
-1down votefavorite
I am trying to find the best root for my binary search tree. i.e. this is my binary search tree.
42 / / 25 53 / / 23 41 49 55 / / / /
then I save them in an array in the form of inOrder walk.
| 23 | 25 | 41 | 42 | 49 | 53 | 55 |.........
............................................
so the ones pointing the arrows are the nodes that ill try to see which one is the best root 41, 42, 53.(the array can be bigger and ill take the odd indexes of the array with a given Depth of the tree). I know the tree might already be balance but this is an experiment so bare with me please.
So i have to try every single odd index as my new root and compare each height with the previous one and like that i can determine which one is my best hight. i.e. if i decided 25 is my new root i can have a tree like this
25 25 42 or 53 / 53 42 /
so for each I check and compare the height with the previous node in the array and i return the node that it will give me the best node. So far i tried this:
void rebalance(){ //this is the size for the array and NumDepth is defined at the constructor int size = (pow (2,(numDepth +1) )-1); Node* Array2 [size]; int i = 0; int bestH = 0; Node* temp; for (int i=0; i < size; i++){ Array2[i]= new Node(); Array2[i]= NULL; } //this function will be the one creates the inOrder walk and saves my nodes inside the array storeInOrder(rootBST, Array2, i, numDepth); temp = shortestBST(Array, rootBST, bestH, height); } Node* shortestBST(Node *root[], Node* root, int &bestHeigth, int sizeA) { //root is my main tree basically //this is how i know that i have to use the odd numbers in the array for(int i= 1; i< sizeA; i+=2){ //inside here I am supposed to do a recursion to check every node inside the array to check the node that is the best //they gave me a hint saying that i can point the nodes in the array to the ones in my main tree to create the tree with the new testing root in order to check if that node can create a best tree but i don't know how to do that using recursion //each of my nodes hold a key, a height and a size of a subtree , left to point to the left and a right to point to the right } } Node::Node() { sizeSub=0; height=1; key=0; left=NULL; right=NULL; }
Explanation / Answer
void rebalance(){
int size = (pow (2,(numDepth +1) )-1); 25 25
42 or 53
Node* Array2 [size]; 53 42
int i = 0;
int bestH = 0;
Node* temp;
for (int i=0; i < size; i++){
Array2[i]= new Node();
Array2[i]= NULL;
}
//this function will be the one creates the inOrder walk and saves my nodes inside the array
storeInOrder(rootBST, Array2, i, numDepth);
temp = shortestBST(Array, rootBST, bestH, height);
}
Node* shortestBST(Node *root[], Node* root, int &bestHeigth, int sizeA) {
//root is my main tree basically
//this is how i know that i have to use the odd numbers in the array
for(int i= 1; i< sizeA; i+=2){
//inside here I am supposed to do a recursion to check every node inside the array to check the node that is the best
//they gave me a hint saying that i can point the nodes in the array to the ones in my main tree to create the tree with the new testing root in order to check if that node can create a best tree but i don't know how to do that using recursion
//each of my nodes hold a key, a height and a size of a subtree , left to point to the left and a right to point to the right
}
}
Node::Node() {
sizeSub=0;
height=1;
key=0;
left=NULL;
right=NULL;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.