С++ Проблема с поворотом двоичного дерева AVL и удалением дерева

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

удалить узел;

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

заголовок:

#ifndef AVLBINARYTREE_H
#define AVLBINARYTREE_H
#include <iostream>
#include <string>
using namespace std;

class LinkedBinaryTree {
private:
    struct Node {
        string word;
        Node* left;
        Node* right;
        Node* parent;
        int wordCount;
        int height;
        Node() : word(), left(NULL), right(NULL), parent(NULL), wordCount(1), height(0) {}
        Node(string s, Node* l, Node* r, Node* p) {
            word = s;
            left = NULL;
            right = NULL;
            parent = p;
            wordCount = 1;
            height = 0;
        }
    };

    Node* _root;

public:
    LinkedBinaryTree();
    ~LinkedBinaryTree();
    void destroyTree();
    void destroyTree(Node* node);
    void insert(string word);
    void display(Node* ptr, int level);
    Node* root();
    void inOrder(Node* node);
    int avlNum(Node* node);
    int getNumWords();

    void insertNode(Node* node, string word);
    int height(Node* node);
    int bfactor(Node* node);
    void fixHeight(Node* node);
    void balance(Node* node);
    void rightRotate(Node* node);
    void leftRotate(Node* node);
    void rightLeftRotate(Node* node);
    void leftRightRotate(Node* node);

    int n;
};
#endif

.cpp:

#include "AVLBinaryTree.h"
#include <algorithm>

void LinkedBinaryTree::inOrder(Node* node) {

    if (node == NULL)
        return;
    inOrder(node->left);
    cout << node->wordCount << " " << node->word << endl;
    inOrder(node->right);
}

void LinkedBinaryTree::rightRotate(Node* node) {

    Node* temp;
    temp = node->left;
    node->left = temp->right;
    //node->left->parent = node;
    temp->parent = node->parent;
    temp->right = node;
    node->parent = temp;
    node = temp;
    if (temp->parent == NULL) {
        _root = node;
    }
    fixHeight(node);
    fixHeight(node->right);
    fixHeight(node->left);
}

void LinkedBinaryTree::leftRotate(Node* node) {

    Node* temp;
    temp = node->right;
    node->right = temp->left;
    temp->parent = node->parent;
    temp->left = node;
    node->parent = temp;
    node = temp;
    if (temp->parent == NULL) {
        _root = node;
    }
    fixHeight(node);
    fixHeight(node->right);
    fixHeight(node->left);
}

void LinkedBinaryTree::rightLeftRotate(Node* node) {

    rightRotate(node->left);
    leftRotate(node);
}

void LinkedBinaryTree::leftRightRotate(Node* node) {

    leftRotate(node->right);
    rightRotate(node);
}

int LinkedBinaryTree::height(Node* node) {

    int h = 0;

    if (node != NULL) {
        h = node->height;
    }
    return h;
}

int LinkedBinaryTree::bfactor(Node* node) {

    return height(node->right) - height(node->left);
}

void LinkedBinaryTree::fixHeight(Node* node) {

    int hl = height(node->left);
    int hr = height(node->right);
    node->height = (hl > hr ? hl : hr) + 1;
}

int LinkedBinaryTree::avlNum(Node* node) {

    int leftH = height(node->left);
    int rightH = height(node->right);
    int avlNum = rightH - leftH;
    return avlNum;
}

LinkedBinaryTree::LinkedBinaryTree() {

    _root = NULL;
}

LinkedBinaryTree::~LinkedBinaryTree() {

    destroyTree();
}
void LinkedBinaryTree::destroyTree() {

    destroyTree(_root);
}
//**********************************************************
// destroyTree is called by the destructor. It deletes  
// all nodes in the tree.                                  
//**********************************************************
void LinkedBinaryTree::destroyTree(Node* node) {

    if (node != NULL) {
        if (node->left != NULL)
            destroyTree(node->left);
        if (node->right != NULL)
            destroyTree(node->right);
        delete node;
    }
}

void LinkedBinaryTree::insertNode(Node* node, string word) {

    if (word < node->word) {
        if (node->left != NULL)
            insertNode(node->left, word);
        else {
            node->left = new Node(word, NULL, NULL, node);
            n++;
            fixHeight(node->left);
        }
    }
    else if (word > node->word) {

        if (node->right != NULL)
            insertNode(node->right, word);
        else {
            node->right = new Node(word, NULL, NULL, node);
            n++;
            fixHeight(node->right);
        }
    }
    else if (word == node->word) {
        node->wordCount++;
    }
    balance(node);
}

void LinkedBinaryTree::insert(string word) {

    if (_root == NULL) {
        _root = new Node(word, NULL, NULL, NULL);
        n++;
    }
    else {
        insertNode(_root, word);
    }
}
void LinkedBinaryTree::display(Node* ptr, int level) {

    int i;
    if (ptr != NULL)
    {
        display(ptr->right, level + 1);
        printf("\n");
        if (ptr == _root)
            cout << "Root -> ";
        for (i = 0; i < level && ptr != _root; i++)
            cout << "        ";
        cout << ptr->word;
        display(ptr->left, level + 1);
    }
}

LinkedBinaryTree::Node * LinkedBinaryTree::root() {

    return _root;
}

void LinkedBinaryTree::balance(Node* node) {

    fixHeight(node);
    if (bfactor(node) == 2) {
        if (bfactor(node->right) < 0)
            rightRotate(node->right);
        else
            leftRotate(node);
    }
    if (bfactor(node) == -2) {
        if (bfactor(node->left) > 0)
            leftRotate(node->left);
        else
            rightRotate(node);
    }
}

int LinkedBinaryTree::getNumWords() {

    return n;
}

главный:

#include "AVLBinaryTree.h"
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <vector>
#include <functional>

int main(int argv, char *argc[]) {

    LinkedBinaryTree t;
    string word("Test."), lastword("");

    for (int i = 0; i < argv; i++)
        cout << argc[i] << endl;

    if (argv < 2) {
        cerr << "No input file specified" << endl;
        system("pause");
        exit(1);
    }
    for (int count = 1; count < argv; count++)
    {
        ifstream input(argc[count]);
        if (!input) {
            cerr << "Cannot open input file" << argc[count] << endl;
            system("pause");
            exit(1);
        }
        while (input >> word)
        {
            transform(word.begin(), word.end(), word.begin(), ::tolower);

            word.erase(remove_if(word.begin(), word.end(), ispunct));

            t.insert(word);
        }
    }

    t.inOrder(t.root());
    cout << endl;

    cout << "--------" << endl;
    cout << t.getNumWords() << "  " << "Total number of different words";
    cout << endl;


    /*t.insert("Yes");
    t.insert("No");
    t.insert("Maybe");
    t.insert("Hopefully");
    t.insert("Absolutely");

    t.display(t.root(), 1);

    cout << endl;
    cout << endl;

    t.inOrder(t.root());
    */

    system("PAUSE");

    t.~LinkedBinaryTree();

    return EXIT_SUCCESS;
}

заранее спасибо!


person NeerP84    schedule 20.11.2017    source источник


Ответы (1)


Строки node = temp; в функциях поворота изменяют локальное значение указателя, принадлежащего функции, а не значение, хранящееся в дереве. Например, когда вы вызываете rightRotate(node->right), значение node->right остается тем же после вызова, когда оно должно быть обновлено.

Возможные решения включают либо передачу указателя узла в функцию поворота в качестве ссылки (void LinkedBinaryTree::rightRotate(Node*& node)), чтобы обновить исходное значение, либо возврат обновленного значения (Node *LinkedBinaryTree::rightRotate(Node* node)) и его сохранение соответствующим образом.

Ваша функция balance и другие функции вращения могут быть затронуты аналогичным образом.

person 1201ProgramAlarm    schedule 20.11.2017
comment
Спасибо, что взглянули на мой код, ранее я пытался вернуть обновленное значение и сохранить его, но это не решило проблему. Я также только что попытался изменить свои функции, чтобы вместо этого передать указатель узла, но он все еще делает то же самое. Как только я доберусь до своего 5-го узла вставки, он будет потерян, и вращение не произойдет. еще раз спасибо - person NeerP84; 20.11.2017