C++ Problem mit AVL Binäre Baumrotationen und Baum löschen

Question

Ich arbeite an einer AVL-Binary-Tree-Implementierung und ich habe den größten Teil des Codes außer für meine Rotationen und meine Löschfunktionen. Ich habe verschiedene Methoden der Umsetzung ausprobiert, aber ich kann immer noch nicht herausfinden, was ich falsch mache. Wenn jemand mir mit einer Lösung helfen könnte, würde es sehr geschätzt werden. Wenn ich die Auswuchtfunktion auskommentiere, wird der Code nach Bedarf funktionieren und alle Wörter aus einer importierten Textdatei einfügen, aber in dem Moment, in dem ich versuche, den Knoten auszugleichen, explodiert der Code. Und aus irgendeinem Grund gibt es ein Problem mit meinem:

löschen Knoten;

Abschnitt meines Codes, aber ich bin mir nicht wirklich sicher, warum das ein Problem wäre. Es gibt kein Problem mit der Rekursion durch den Baum gehen, aber sobald es um den Löschknotenabschnitt trifft es ein Problem hat, macht dies keinen Sinn für mich ...

Header:

#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; 
} 

Haupt:

#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; 
} 

dank im Voraus!

Answer 1

Die Zeilen node = temp; in Ihren Rotate-Funktionen ändern den lokalen Wert des Zeigers, der zu der Funktion gehört, und nicht den in der Struktur gespeicherten Wert. Wenn Sie beispielsweise rightRotate(node->right) aufrufen, ist der Wert node->right nach dem Aufruf gleich, wenn er aktualisiert werden sollte.

Mögliche Lösungen sind entweder die Übergabe des Knotenzeigers an die Rotationsfunktion als Referenz (void LinkedBinaryTree::rightRotate(Node*& node)), so dass der ursprüngliche Wert aktualisiert wird, oder die Rückgabe des aktualisierten Werts (Node *LinkedBinaryTree::rightRotate(Node* node)) und entsprechende Speicherung.

Ihre balance Funktion und die anderen Drehfunktionen können ähnlich beeinträchtigt sein.