我的ALV树平衡因子计算不正确

Question

为什么我的输出不正确？代码应该打印范围为 {-1, 0, 1} 的平衡因子，但我得到： 0 255 0 -255 -255 -255 0 -1 0 0 0 254。当我将 nullptr 节点的高度设置为 0 时，树计算正确，但平衡因子计算不正确。我真的不明白我的错误在哪里。看起来代码应该可以正常工作，但事实并非如此。

#include "iostream"
#include <string>

using namespace std;

class AVL_Tree{
private:
    struct node{
        int key;
        unsigned char height;
        node* left;
        node* right;
        node(int k){
            key = k;
            left = right = nullptr;
            height = 0;
        }
    };

    unsigned char height(node* p){
        return p?p->height:(-1);
    }

    void fixheight(node* p){
        unsigned char hl = height(p->left);
        unsigned char hr = height(p->right);
        p->height = (hl>hr ? hl : hr) + 1;
    }

    node* rotateright(node* p){
        node* q = p->left;
        p->left = q->right;
        q->right = p;
        fixheight(p);
        fixheight(q);
        return q;
    }

    node* rotateleft(node* q) // левый поворот вокруг q
    {
        node* p = q->right;
        q->right = p->left;
        p->left = q;
        fixheight(q);
        fixheight(p);
        return p;
    }

    node* balance(node* p){
        fixheight(p);
        if (balancefactor(p) == 2){
            if (balancefactor(p->right) < 0){
                p->right = rotateright(p->right);
            }
            return rotateleft(p);
        }
        if (balancefactor(p) == -2){
            if (balancefactor(p->left) > 0){
                p->left = rotateleft(p->left);
            }
            return rotateright(p);
        }
        return p;
    }

    node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
    {
        if( !p ) return new node(k);
        if( k<p->key )
            p->left = insert(p->left,k);
        else
            p->right = insert(p->right,k);
        return balance(p);
    }
    void printfactors(node* curr){
        if (curr){
            printfactors(curr->left);
            cout << balancefactor(curr) << " ";
            printfactors(curr->right);
        }
    }
    int balancefactor(node* p){
        return height(p->right) - height(p->left);
    }

    node* root;
public:

    AVL_Tree(int x){
        root = new node(x);
    }

    void insert(int k){
        root = insert(root, k);
    }

    void printfactors(){
        printfactors(root);
    }
};

int main(){
    srand(time(nullptr));
    int a = rand() % 101;
    AVL_Tree tree(20);
    tree.insert(10);
    tree.insert(11);
    tree.insert(12);
    tree.insert(5);
    tree.insert(3);
    tree.insert(15);
    tree.insert(18);
    tree.insert(25);
    tree.insert(23);
    tree.insert(24);
    tree.insert(22);

    tree.printfactors();

    return 0;
}

Answer 1

主要问题是

height

函数的返回类型：它设置为

unsigned char

，但它可以返回 -1，这将被解释为 255。

将该返回类型更改为

char

。

另一个潜在问题是旋转可能会影响旋转节点的parent的平衡因子。因此，在代码中的多个位置，您应该在此类父节点上调用

fixheight

。