AVL 树旋转问题

Question

我一直在研究用于插入的 AVL 树。我的插入物工作正常，但我尝试过的每一次轮换实施都不起作用。我一直在尝试不同的位置来保持平衡，也只是在每次插入后尝试旋转以检查它是否有效，但我根本没有旋转开火。非常感谢任何关于为什么我的轮换不起作用的帮助。

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

主要内容：

#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

您的代码中有许多错误，但阻止旋转的错误是第二个 bfactor 签入 balance 不正确。它应该与 -2.

进行比较

if (bfactor(node) == -2)

您遇到的另一个问题是 Rotate 函数中 if 语句的条件赋值（提高编译器警告级别会通知您这些）。

AVL 树旋转问题

Issue with AVL tree rotations

c++

rotation

avl-tree