how to create a full binary tree with empty nodes

Question

i'm working on merging 2 template AVL trees into 1 tree with a complexity of total num of nodes in both trees (which is tricky) - the right algorithm is to build a full binary tree with the amount of nodes of total - if total is equal to power of 2 minus 1, or to create a full binary tree with more nodes than total ( the next power of 2) and cut the unnecessary leaves (dif between total and the next power of 2) while the nodes are template also and should be empty. how can i build a full binary tree with empty nodes without any key comparing ( i can't have any keys since the nodes are template)?

my template node is:

class avl_node{
private:
    friend class avl_tree;
    //design to contain dinamically allocated key and data only!
    //assumption- every node uses it's own data and key- no data or key are the
    //same memory for different nodes!
    Key *key;
    T *data;
    avl_node *parent;
    avl_node *right;
    avl_node *left;
    int height;
    int balance;
    int maxHeight(int h1,int h2){
        return (h1 > h2) ? h1:h2;
    }

public:
    avl_node(Key* key=nullptr, T* data=nullptr): key(key),data(data),right(nullptr),left(nullptr),parent(nullptr),height(0),balance(0){}
    //no setKey since this is an invariant from node creation
    virtual ~avl_node(){
        delete key;
        delete data;
        delete right;
        delete left;
    }
    virtual bool insert( Key* key,  T* data,avl_node *& to_fix_from);
    virtual avl_node * findNode(const Key& key);
    virtual void updateStats() {
        if(left && right){
            height=maxHeight(left->height,right->height)+1;
            balance=left->height-right->height;
            return;
        }
        if(!left && right){
            height=right->height+1;
            balance=-right->balance;
            return;
        }
        if(left &&!right){
            height=left->height+1;
            balance=left->height;
            return;
        }
        this->height=0;
    }

};

the issue is- Key is a template parameter- so i can't decide ,for example, to make a for loop on the amount of nodes needed and create some simple key (according to for-loops'counter) and insert it- since insert needs some option to compare.

i'm editing the question: i found out here , i can dinamically allocate an array of empty nodes and recursively assign every node with left and right as in binary search (on the array indexes). new question :can i free every node one by one from the a pointer to this node- although they were allocated in an array? because i wanted to stay with only one root and treat it like a tree with the compatible delete function.

Explain your problem in more details. How is it related to C++? — Kirill Kobelev
What does "the nodes are template" mean? Do you know how to construct one node the way you want? What if the total number of nodes is not 2^n-1? — Beta

Kirill Kobelev Kirill Kobelev · Accepted Answer · 2016-12-01T19:12:28

The question is not absolutely clear form what are you trying to achieve. Building a full empty tree is relatively straightforward. You do not need any keys at this point. They will be all NULL. You can do something like this:

avl_node *avl_node::BuildAvlSubtree(int height_needed)
{
    if (height_needed <= 0)
        return nullptr;
    auto node = new avl_node();
    node->left = BuildAvlSubtree(height_needed-1);
    node->right = BuildAvlSubtree(height_needed-1);
    return node;
}

This function should be a static member of the avl_node class because it accesses the private members.

how to create a full binary tree with empty nodes

1 Answers