Корневой узел класса дерева не обновляется

Question

Я пытаюсь написать класс дерева AVL на C++, и я начинаю с того, что просто пишу код для обычного BST, но у меня есть проблема. Проблема у меня с моей функцией вставки. Я пытаюсь вставить элементы в дерево, которое, кажется, на самом деле не делает этого. Я не совсем уверен, почему это не так, моя догадка в том, что я меняю дерево внутри функций, но я ничего не делаю, чтобы сохранить эти изменения, и я не знаю, как это сделать тот.

#ifndef AVLTREE_H
#define AVLTREE_H
#include <iostream>

template <class K, class V>
struct AVLNode{
    K Key;
    V Value;
    AVLNode<K,V> *left;
    AVLNode<K,V> *right;
};

template <class K, class V>
class AVLTree{
    public:
        AVLTree();
        ~AVLTree();
        void insert(const K& Key, const V& Value);
        void print_AVL();
    private:
        void print_AVL2(AVLNode<K,V> *node);
        void insert2(AVLNode<K,V> *node, const K& Key, const V& Value);
        AVLNode<K,V> *root;
};

template <class K, class V>
AVLTree<K,V>::AVLTree(){
    root = nullptr;
}

template <class K, class V>
AVLTree<K,V>::~AVLTree(){
    delete root;
}
template <class K, class V>
void AVLTree<K,V>::insert(const K& Key, const V& Value){
    std::cout << "Trying to insert " << Key << ", " << Value << std::endl;
    insert2(root, Key, Value);
}

template <class K, class V>
void AVLTree<K,V>::insert2(AVLNode<K,V> *n, const K& Key, const V& Value){
    std::cout << n << std::endl;
    if(n== nullptr){
        n = new AVLNode<K,V>;
        n->Key = Key;
        n->Value = Value;
        n->parent = nullptr;
        n->left = nullptr;
        n->right = nullptr;
    }
    else if(n->Key > Key){
        insert2(n->left, Key, Value);
    }
    else{
        insert2(n->right, Key, Value);
    }
    std::cout << n << std::endl;
}

template <class K, class V>
void AVLTree<K,V>::print_AVL(){
    print_AVL2(root);
}


template <class K, class V>
void AVLTree<K,V>::print_AVL2(AVLNode<K,V> *n){
    std::cout << n << std::endl;
    if(n == nullptr){
        return;
    }
    print_AVL2(n->left);
    std::cout << "Name, ID: " << n->Value << ", " << n->Key << std::endl;
    print_AVL2(n->right);
}


#endif

Моя основная функция выглядит так:

#include "AVLTree.hpp"
#include <iostream>

int main() 
{
    AVLTree<std::string,std::string> Tree;
    Tree.insert("Hello","World");
    Tree.print_AVL();
    return 0;
}

Answer 1

Помните, даже в C++, если явно не указано иное, параметры передаются по значению. Таким образом, это:

void AVLTree<K,V>::insert2(AVLNode<K,V> *n, const K& Key, const V& Value)

в сочетании с этим:

n = new AVLNode<K,V>;

будет делать немного больше, чем назначить результат new вызвать к автоматической переменной n это исчезнет, ​​как только эта функция вернется.

Если вы хотите сохранить этот результат, передайте указатель по ссылке:

void AVLTree<K,V>::insert2(AVLNode<K,V>*& n, const K& Key, const V& Value)
// reference to the caller's pointer ===^

изменилось как в decl, так и в реализации. Остальные parent Указатель на необъявленный член, который я оставляю для вас, чтобы исправить, а также последующую утечку памяти у неразрушенных потомков корневого узла, как только вы начнете добавлять больше узлов в дерево.