c++ - AVL 树代码 - 我不明白

Question

void insert( const Comparable & x, AvlNode * & t )
{
    if( t == NULL )
            t = new AvlNode( x, NULL, NULL );
    else if( x < t->element )
    {
            insert( x, t->left );
            if( height( t->left ) - height( t->right ) == 2 )
                    if( x < t->left->element )
                            rotateWithRightChild( t );
                    else
                            doubleWithLeftChild( t );
    }
    else if( t->element < x )
    {
            insert( x, t->right );
            if( height( t->right ) - height( t->left ) == 2 )
                    if( x < t->left->element )
                            rotateWithRightChild( t );
                    else
                            doubleWithLeftChild( t );
    }
    else
            ; // Duplicate; do nothing
    t->height = max( height( t->left ), height( t->right ) ) + 1;

}

int height( AvlNode *t ) const { return t == NULL ? -1 : t->height; }

他们如何计算树的高度？

       1
     0
  -1

高度(-1) - 高度(null) = 1 ??不平衡？

Answer 1

您的问题并非 100% 清楚。代码

AvlNode * & t

声明 t 是对非常量指针的引用。因此，函数 insert 可能会更改调用者的指针对象。由于指针可能为空，因此代码可能使用名为 height 的函数 作为处理空指针特殊情况的快捷方式:

inline int height(AvlNode * tree) {
    return tree ? tree->height : 0;
}

(只是我对高度的猜测)

在您编辑问题后添加:似乎每个节点都有一个名为 height 的成员，它保持同步并反射(reflect)从当前节点到叶子的路径的最大长度。由于空指针不指向节点，因此子树将为空，这解释了返回 -1 的 height() 中的特殊情况。