lundi 26 septembre 2022

Making a BST from a sorted array

I am having issues building out a bst function that takes in a pointer to an array and a size. I believe I have it mostly figured out, until I build out the right subtree. The pseudo goes: check if it's done when size is zero, otherwise, find the middle point of the array, and insert that value. Then that roots left will be finding the middle of the array to the left of roots value and right will find the middle of the array to the right of roots value and repeat recursively until the arrays have been broken down enough that they have no size. Here is what I have so far.

template <typename T> // sorted array -> tree
tree_node<T>* tree_from_sorted_list(const T* a, int size){
    if (size == 0){
        return nullptr;
    }
    
    int mid = size/2;
    tree_node<T>* root = nullptr;
    
    tree_insert(root, a[mid]);

    root->_left = tree_from_sorted_list(a, mid-1);
    root->_right = tree_from_sorted_list();

    return root;
}

I can't figure out how to implement root->_right. Ive been told the solution would be (a, a+index+1) but I am not sure what that means. How would this be converted to an int so that the recursive call then gets that array from to the right of the value that is being inserted?

Aucun commentaire:

Enregistrer un commentaire