平衡树插入节点的疑问

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3489 天前的主题，其中的信息可能已经有所发展或是发生改变。

AvlTree
Insert ( ElementType X, AvlTree T )
{
    if ( T == NULL )
    {
        /* Create and return a one-node tree */
        T = malloc( sizeof( struct AvlNode ) );
        if ( T == NULL )
            FatalError( "Out of space!!!" );
        else
        {
            T->Element = X; T->Height = 0;
            T->Left = T->Right = NULL;
        }
    }
    else
    if ( X < T->Element )
    {
        T->Left = Insert( X, T->Left );
        if ( Height( T->Left ) - Height( T->Right ) == 2 )
            if ( X < T->Left->Element )
                T = SingleRotateWithLeft( T );
            else
                T = DoubleRotateWithLeft( T );
    }
    else
    if ( X > T->Element )
    {
        T->Right = Insert( X, T->Right );
        if ( Height( T->Right ) - Height( T->Left ) == 2 )
            if ( X > T->Right->Element )
                T = SingleRotateWithRight( T );
            else
                T = DoubleRotateWithRight( T );
    }
    /* Else X is in the tree already;we'll do nothing */
    T->Height = Max( Height( T->Left ), Height( T->Right ) ) + 1;
    return T;
}

为什么会有｀if ( X < T->Left->Element )｀这个判断语句，T->left->Element不就是新插入节点的Element吗，那么它跟X不是相同的吗

height

element

left

4 条回复 • 2015-04-23 11:34:21 +08:00

illuz

2015-04-23 09:01:35 +08:00

`T->Right = Insert( X, T->Right );`
这句话是递归调用，最后插入的 X 会在 (T->Right) 子树叶子节点，或者树中已存在就不插入了，而不是一定插在 (T->Right) 子树的根节点。
所以插入后的 (T->left->Element) 并不一定是新插入节点，它跟 X 可能不是相同的。

illuz

2015-04-23 09:04:40 +08:00

复制语句复制得有点混乱，再来一次。 >.<

先看看前一句的：`T->Left = Insert( X, T->Left );`
这句话是递归调用 Insert 函数，而不是就直接插进去。
最后插入的 X 会在 (T->Left) 子树叶子节点，或者树中已存在就不插入了，而不是一定插在 (T->Left) 子树的根节点。
所以插入后的 (T->left->Element) 并不一定是新插入节点，它跟 X 可能不是相同的。

insaneDream

2015-04-23 09:10:05 +08:00

@illuz `T->Right = Insert( X, T->Right );`，如果T->Right==NULL的，那么它就会创建一个新的节点并返回给T->Right, 那么插入的X不是在T->Right这个节点上吗?

illuz

2015-04-23 11:34:21 +08:00

@makubx1 如果不是，就递归处理了，这样 X 就不在 T->Left 上了，所以说是不一定的。（都按 Left 那边来说）