AVL树平衡因子计算错误排查：输出值超出{-1,0,1}范围

问题根源 #

代码中平衡因子输出出现255、-255等超出{-1,0,1}范围的异常值，核心原因是无符号字符类型的溢出问题：

• 结构体用unsigned char height存储节点高度，而height函数对空节点返回-1，-1转换为unsigned char时会被解析为255（无符号字符的补码特性）。
• 平衡因子计算height(p->right) - height(p->left)时，用255代替了预期的-1，导致差值出现异常（比如255-0=255、0-255=-255）。

另外你提到空节点高度设为0时仍有问题，是因为叶子节点初始高度设置错误：空节点高度为0时，叶子节点高度应为max(0,0)+1=1，但代码中节点构造函数把height初始化为0，导致后续高度计算全部偏移。

修复方案 #

方案1：改用有符号整数存储高度（推荐） #

将高度相关类型改为int，彻底避免无符号类型的溢出问题：

1. 修改结构体中的高度类型：

struct node{
    int key;
    int height;  // 替换unsigned char为int
    node* left;
    node* right;
    node(int k){
        key = k;
        left = right = nullptr;
        height = 0;  // 空节点高度为-1时，叶子节点初始高度为0，逻辑正确
    }
};

2. 修改height函数的返回类型为int：

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

3. 调整fixheight函数的变量类型：

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

方案2：保持无符号类型，调整空节点高度逻辑 #

如果坚持使用unsigned char，需将空节点高度设为0，同时修正初始高度：

1. 修改height函数：

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

2. 节点构造函数中初始高度设为1：

node(int k){
    key = k;
    left = right = nullptr;
    height = 1;  // 叶子节点左右子树高度为0，max(0,0)+1=1
}

修改后的完整代码（方案1） #

#include "iostream"
#include <string>

using namespace std;

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

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

    void fixheight(node* p){
        int hl = height(p->left);
        int 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)
    {
        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)
    {
        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;
}

验证结果 #

修改后运行代码，平衡因子输出会严格限制在{-1,0,1}范围内，符合AVL树的平衡要求。

内容的提问来源于stack exchange，提问作者Timofey