Speicherlecks beim Zusammenführen von zwei AVL-Bäume

So, ich habe eine Zuweisung zu erstellen, die ein AVL-Baum der Klasse. Alles perfekt funktioniert und keine Lecks, außer für die Funktion zum Zusammenführen von zwei Bäumen - Alle Bäume gemacht durch diese Funktion verursacht ein Speicherleck.

Die Funktion funktioniert wie folgt - Sie erstellen eine sortierte array von jedem Baum und mischen Sie Sie in einem array. Dann rufen Sie eine rekursive Funktion, die erstellt einen Baum aus diesem array, und das ist die Funktion, schafft das Leck.

Ich habe versucht, ändern Sie die Funktion so, das gibt einen Knoten, aber das scheint nicht zu helfen. im moment ist die Funktion bekommt einen Zeiger auf den Knoten erstellt werden muss, und reserviert Speicher gibt.

Ich will noch einmal darauf hinweisen, dass regelmäßig Bäume nicht dazu führen, keine Lecks, so dass das problem wahrscheinlich in der merge-Funktion und nicht den Destruktor.

class AVLNode {
public:
    T key_m;
    S value_m;
    int balance_m;
    AVLNode *left_m;
    AVLNode *right_m;
    AVLNode *parent_m;

    AVLNode(const T &key = T(), const S &value = S(), AVLNode *parent = nullptr) : key_m(key),
                                                             value_m(value),
                                                             balance_m(0),
                                                             parent_m(parent),
                                                             left_m(nullptr),
                                                             right_m(nullptr) {}

    ~AVLNode() {
        delete left_m;
        delete right_m;
    }
}
class AVLTree {

private:
     AVLNode<T,S>* root;
public:

    ~AVLTree(){
     delete root;
     }
}


/*The recursive function which causes the leak. 
it has a parent function I haven't added here since it's not very relevent */
template<class T, class S>
void
AVLTree<T, S>::mergeTrees(AVLNode<T, S> *nodeArr, int start, int end,
                          AVLNode<T, S> *parent, AVLNode<T,S>* nodeToIntialize) {
    if(!nodeArr){
        throw MemError();
    }
    if(start > end){
        return;
    }
    int mid = (start+end)/2;
    T key = nodeArr[mid].key_m;
    S value = nodeArr[mid].value_m;
    nodeToIntialize = new AVLNode<T,S>(key, value, parent); // <- the problem
    (nodeToIntialize)->parent_m = parent;
    mergeTrees(nodeArr, start, mid-1, nodeToIntialize, nodeToIntialize->left_m);
    mergeTrees(nodeArr, mid+1, end, nodeToIntialize, (nodeToIntialize)->right_m);
}

Also ich Teste diesen Baum mit einem Programm generiert zufällige Bäume für mich, und dann führt diese zusammen und prüft die regelmäßige Baum-und die zusammengeführte Bäume für Gleichgewicht und bestellen, etc. Das Programm funktioniert, aber dies ist die valgrind-Ausgabe: https://i.imgur.com/Av885xr.png (Alle Undichtigkeiten sind aus der gleichen Zeile, die ich markiert man als Beispiel)

An diesem Punkt habe ich nichts dagegen nur das umschreiben der gesamten Funktion, könnte wirklich helfen. Danke.