nullptr = узел назначается неправильно

Question

пожалуйста, не углубляйтесь в меня слишком сильно, я все еще постоянно учусь и столкнулся с проблемой при попытке построить дерево AVL. Выполняя итерацию по дереву при вставке, я иду до достижения nullptr, создаю новый узел и назначаю этот ptr для nullptr. Значение никогда не принимается, хотя. Может кто-нибудь найти ошибку и объяснить мне? ты!

#ifndef AVLTree_hpp
#define AVLTree_hpp

#include <stdio.h>
#include <stack>
template<typename T>
class AVLTree{
private:
    struct Node{
        T val;
        Node* left;
        Node* right;
        int height;

        Node(T V)
        :left{nullptr},right{nullptr}
        {
            val = V;
        }
        ~Node(){

        }
    };
    Node* head;
    void rightRotate(Node*& node);
    void leftRotate(Node*& node);
    void leftRight(Node*& node);
    void rightLeft(Node*& node);


public:
    AVLTree();
    ~AVLTree();
    AVLTree(const AVLTree &c);
    AVLTree(AVLTree &&c);
    AVLTree &operator=(const AVLTree &c);
    AVLTree &operator=(AVLTree &&c);
    void add(T value);
    int getHeight(Node* n);
};

template <typename T>
AVLTree<T>::AVLTree()
    :head{nullptr}{
}
template <typename T>
AVLTree<T>::~AVLTree(){

}

template <typename T>
void AVLTree<T>::rightRotate(Node*& node){
    Node* temp = node;
    node = node->left;
    Node* leftLL = node->right;
    temp->left = leftLL;
    node->right = temp;
}
template <typename T>
void AVLTree<T>::leftRotate(Node*& node) {
    Node* temp = node;
    node = node->right;
    Node* yL = node->left;
    temp->right = yL;
    node->left = temp;
}
//left right condition
template <typename T>
void AVLTree<T>::leftRight(Node*& node) {
    leftRotate(node->left);
    rightRotate(node);
}

//right left condition
template <typename T>
void AVLTree<T>::rightLeft(Node*& node){
    rightRotate(node->right);
    leftRotate(node);
}
template <typename T>
void AVLTree<T>::add(T value){
    if(head==nullptr){
        head = new Node(value);
        return;
    }
    std::stack<Node*> st;
    Node* it = head;
    while(it!=nullptr){
        st.push(it);
        if(value <= it->val){
            it = it->left;
        }else{
            it=it->right;
        }
    }
//here is where the it is not assigned to the new node pointer. 
//I have tested it and the node is created, "it" just does not hold the value at any point.
    it = new Node(value);
    int count = 0;
    while(!st.empty()){
        int balance = getHeight(st.top()->left) - getHeight(st.top()->right);
        if(balance > 1){
            if(st.top()->left!= nullptr&&st.top()->left!=nullptr){
                leftRotate(st.top());
            }else{
                leftRight(st.top());
            }
        }else if(balance<-1){
            if(st.top()->right!=nullptr&&st.top()->right!=nullptr){
                rightRotate(st.top());
            }else{
                rightLeft(st.top());
            }
        }
        st.pop();
        if(++count==4){
            break;
        }
    }
}
template <typename T>
int AVLTree<T>::getHeight(Node* n){
    int max =0;
    if(n!=nullptr){
        max = std::max(getHeight(n->left),getHeight(n->right))+1;
    }
    return max;
}


#endif /* AVLTree_hpp */

Answer 1

Рассмотрим упрощенную версию вашего кода:

#include <iostream>

struct Linked {
    Linked* next;
};

int main(int argc, char** argv) {
    Linked l0 {nullptr};

    // Case 1: Does not work
    std::cout << "case 1" << std::endl;
    Linked* node = l0.next;
    node = new Linked {nullptr};
    std::cout << "node=" << std::hex << node << std::endl;
    std::cout << "l0.next=" << std::hex << l0.next << std::endl;
    free(node);
    std::cout << std::endl;

    // Case 2: Works
    std::cout << "case 2" << std::endl;
    l0.next = new Linked {nullptr};
    std::cout << "l0.next=" << std::hex << l0.next << std::endl;
    free(l0.next);
    l0.next = nullptr;
    std::cout << std::endl;

    // Case 3: Works
    std::cout << "case 3" << std::endl;
    Linked** nodeP = &(l0.next);
    *nodeP = new Linked {nullptr};
    std::cout << "*nodeP=" << std::hex << *nodeP << std::endl;
    std::cout << "l0.next=" << std::hex << l0.next << std::endl;
    free(l0.next);
    l0.next = nullptr;
}

Какие выходы:

$ ./main 
case 1
node=0x7fba0d400620
l0.next=0x0

case 2
l0.next=0x7fba0d400620

case 3
*nodeP=0x7fba0d400620
l0.next=0x7fba0d400620

• Случай 1 : не работает, потому что новыйNode присваивается копии левого / правого дочернего указателя (т.е. не фактического дочернего узла от родительского узла)
• Случай 2 : работает какожидается, поскольку новый узел назначается непосредственно одному из дочерних узлов родителя.
• Случай 3 : также работает, потому что вместо назначения нового узла копии дочернего указателя вы назначаетеэто указатель, ссылающийся на указатель на самого ребенка. В этом отношении случаи 2 и 3 эквивалентны.

Answer 2

It является копией указателя, и ее обновление не влияет на исходный указатель. Вам нужно сделать что-то вроде этого:

Node* it = head;
bool left = true;
while(it!=nullptr){
    st.push(it);
    left = value <= it->val;
    if(left){
        it = it->left;
    }else{
        it=it->right;
    }
}
it = new Node(value);
if (left){
    stack.top()->left = it;
} else {
    stack.top()->right = it;
}