Problem mit AVL-Baumrotationen

Question

Ich habe an einem AVL-Baum für Einfügungen gearbeitet. Ich habe die Einsätze richtig funktioniert, aber jede Implementierung meiner Rotationen, die ich versucht habe, wird nicht funktionieren. Ich habe verschiedene Stellen für meine Balance ausprobiert und versuche auch, nach jeder Einfügung zu drehen, nur um zu überprüfen, ob es funktioniert, aber ich bekomme keine Drehung, um überhaupt zu schießen. Jede Hilfe, warum meine Rotationen nicht funktionieren, würde sehr geschätzt werden.

Header:

#ifndef LINKEDBINARYTREE_H 
#define LINKEDBINARYTREE_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(1) {} 
     Node(string s, Node* l, Node* r, Node* p) { 
      word = s; 
      left = NULL; 
      right = NULL; 
      parent = p; 
      wordCount = 1; 
      height = 1; 
     } 
    }; 
    Node* _root; 

public: 
    LinkedBinaryTree(); 
    ~LinkedBinaryTree(); 
    void insertNode(Node* node, string word); 
    void insert(string word); 
    void display(Node* ptr, int level); 
    Node* root(); 
    void inOrder(Node* node); 
    void rightRotate(Node* node); 
    void leftRotate(Node* node); 
    void rightLeftRotate(Node* node); 
    void leftRightRotate(Node* node); 
    int avlNum(Node* node); 
    int height(Node* node); 
    int bfactor(Node* node); 
    void fixHeight(Node* node); 
    void balance(Node* node); 

    int n; 
}; 
#endif 

CPP:

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

void LinkedBinaryTree::inOrder(Node * node) 
{ 
    if (node == NULL) 
     return; 
    inOrder(node->left); 
    cout << node->word << " " << avlNum(node) << " : " ; 
    inOrder(node->right); 
} 

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

void LinkedBinaryTree::leftRotate(Node * node) 
{ 
    Node* temp; 
    temp = node->right; 
    node->right = temp->left; 
    temp->left = node; 
    temp->parent = node->parent; 
    node = temp; 
    if (temp->parent = NULL) { 
     _root = temp; 
    } 
    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() 
{ 
} 

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); 
     } 
    } 
    else if (word > node->word) 
    { 
     if (node->right != NULL) 
      insertNode(node->right, word); 
     else { 
      node->right = new Node(word, NULL, NULL, node); 
     } 
    } 
    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); 
     n++; 
    } 
} 
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); 
    } 
} 

Haupt:

#include "LinkedBinaryTree.h" 
#include <string> 

int main() { 

    LinkedBinaryTree t; 

    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"); 
    return EXIT_SUCCESS; 
} 

Answer 1

Es gibt zahlreiche Fehler im Code, sondern derjenige, der die Drehungen verhindert ist zweite bfactor Check-in balance ist falsch. Es sollte mit -2 vergleichen.

if (bfactor(node) == -2) 

Ein weiteres Problem, das Sie haben, ist Zuweisungen unter den Bedingungen der if Aussagen in Ihren Rotate Funktionen (Steigerung Ihrer Compiler Warnstufe würden Sie davon informieren).