C++ AVL 이진 트리 회전 및 트리 삭제와 관련된 문제

Question

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 

통화 당 : 재귀 트리를 통과하지만 곧 그것이 문제가 삭제 노드 부분 안타 아무 문제가 없습니다, 이것은 나에게 아무 의미 ...

헤더를하지 않습니다 : 사전에

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

감사 :

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

주요

!

Answer 1

회전 기능의 node = temp; 줄이 함수에 속한 포인터의 로컬 값을 변경하고 이 아닌 트리에 저장된 값을 변경합니다. 예를 들어 rightRotate(node->right)으로 전화를 걸면 node->right의 값은 통화 후에 업데이트해야합니다.

가능한 해결책은 노드 값 포인터를 회전 함수에 참조 (void LinkedBinaryTree::rightRotate(Node*& node))로 전달하여 원래 값이 업데이트되거나 업데이트 된 값 (Node *LinkedBinaryTree::rightRotate(Node* node))을 반환하고 올바르게 저장하는 것입니다.

balance 함수와 다른 회전 함수도 비슷하게 영향을받을 수 있습니다.