AVL树插入仅平衡最深的不平衡节点？

Question

在AVL树中，有一种方法只能在插入后检查树中节点的平衡，这样，如果找到了不平衡的节点，则该节点将重新平衡，并且树中没有其他更高的节点需要检查余额？

[当前，当我以递归方式将一个节点插入树中并返回调用堆栈时，如果树中较低位置的某个节点已经处于平衡状态，则不需要检查每个节点是否平衡。我在下面包含了我的代码。

void insertion( const int & val, Node * & s ) //assumes you are entering a unique value into the tree.
{
    if( s == nullptr ) //leaf or empty root
        s = new Node{ val, nullptr, nullptr };

    else if( val < s->element ) //go left
        insertion( val, s->left );

    else if( s->element < val ) //go right
        insertion( val, s->right );

    balFix(s); //Checks and fixes balance if needed.
}

Answer 1

如果节点的高度增加，则其父节点将增加高度（如果父节点以前是平衡的），或者将保持其之前的高度（如果父节点以前是不平衡的）。一旦您到达一个这样的父母（其身高与插入前的身高相同），就可以停下来。您可以使insertion和balFix返回bool：当高度增加时，将返回true，而当高度不增加时，则返回false。 insertion可以看起来像这样：