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

Question

Я пытаюсь написать класс AVL Tree в C++ и im, начиная с простого написания кода для нормального 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 ===^ 

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