Метод вставки дерева AVL вызывает ошибку сегментации - PullRequest
Новая
       6

Метод вставки дерева AVL вызывает ошибку сегментации

1 голос
/ 12 марта 2019

РЕДАКТИРОВАТЬ: insert(), кажется, работает сейчас, но есть проблема с печатью дерева. 

void AVL::preorder(Node *n) {
    if(n != nullptr) {
        cout << n->value << ", ";
        preorder(n->left);
        preorder(n->right);
    }
}

void AVL::printPreorder() {
    preorder(node);
}

Моя проблема в том, что после того, как я вставил первое значение в дерево, я не могу вставить больше. Когда я пытаюсь вставить более одного значения, программа прерывается из-за ошибки сегментации. Я не могу найти проблему здесь. Похоже, что это нарушает оператор if(), но я не знаю, что с этим не так. Сначала я писал программу, используя только struct, и она работала, но мне пришлось изменить ее, чтобы она представляла собой целый класс со структурой внутри. РЕДАКТИРОВАТЬ: добавлено main.cpp 

int main() {

    AVL avl;
    avl.insert(2);
    avl.insert(6); // breaks
    return 0;
}

avl.h 

class AVL {
public:
    struct Node {
        int value;
        int height;
        Node* left;
        Node* right;
    };
    Node* node;

    AVL();
    ~AVL();
    int getHeight(Node *tree);
    Node *newNode(int val);
    Node *rightRotate(Node *y);
    Node *leftRotate(Node *x);
    int getBalance(Node *b);
    Node *insertVal(Node *node, int thisval);
    void preorder(Node *n);
    void printPreorder();
    Node *minValNode(Node *minValNode);
    Node *remove(Node *n, int thisval);
    Node *insert(int val);
};

.cpp 

AVL::AVL() {
        node = nullptr;
    }
AVL::Node* AVL::insertVal(Node *node, int thisval) {
    if(node == nullptr) {
        return newNode(thisval);
    }

    if(thisval < node->value) {
        node->left = insertVal(node, thisval);
    }
    else if(thisval > node->value) {
        node->right = insertVal(node, thisval);
    }
    else {
        return node;
    }

    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;

    int balance = getBalance(node);

    if(balance > 1 && thisval < node->left->value) {
        return rightRotate(node);
    }
    if(balance < -1 && thisval > node->right->value) {
        return leftRotate(node);
    }
    if(balance > 1 && thisval > node->left->value) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    if(balance < -1 && thisval > node->right->value) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}
AVL::Node* AVL::insert(int val) {
    return insertVal(node, val);
}
int AVL::getHeight(Node *tree) {
    if(tree == nullptr) {
        return 0;
    } else {
        return tree->height;
    }
}
AVL::Node* AVL::newNode(int val) {
    node = new Node;
    node->value = val;
    node->height = 1;
    node->left = nullptr;
    node->right = nullptr;
    return node;
}
AVL::Node* AVL::rightRotate(Node *y) {
    Node *x = y->left;
    Node *T2 = x->right;

    x->right = y;
    y->left = T2;

    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

    return x;
}
AVL::Node* AVL::leftRotate(Node *x) {
    Node *y = x->right;
    Node *T2 = y->left;

    x->right = T2;
    y->left = x;

    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

    return y;
}
int AVL::getBalance(Node *b) {
    if(b == nullptr) {
        return 0;
    } else {
        return getHeight(b->left) - getHeight(b->right);
    }
}

1 Ответ

1 голос
/ 12 марта 2019

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

AVL::Node* AVL::insertVal(Node *node, int thisval) {
    if (node == nullptr) {
        return newNode(thisval);
    }

    if (thisval < node->value) {
        node->left = insertVal(node, thisval);
    }
    else if (thisval > node->value) {
        node->right = insertVal(node, thisval);
    }
    else {
        return node;
    }

В этом коде и вместе с основным, который вы указали, thisval > node->value имеет значение true, поэтому insertval вызывается снова с точно такими же параметрами . Таким образом, весь процесс повторяется, повторяется и повторяется до тех пор, пока вы не получите переполнение стека.

Полагаю, вы имели в виду это 

AVL::Node* AVL::insertVal(Node *node, int thisval) {
    if (node == nullptr) {
        return newNode(thisval);
    }

    if (thisval < node->value) {
        node->left = insertVal(node->left, thisval);
    }
    else if (thisval > node->value) {
        node->right = insertVal(node->right, thisval);
    }
    else {
        return node;
    }

Эта ошибка была обнаружена примерно через две минуты с помощью отладчика. На данном этапе вашего развития это, пожалуй, самая полезная вещь, которую вы можете научиться использовать.

...