V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
insaneDream
V2EX  ›  编程

平衡树插入节点的疑问

  •  
  •   insaneDream · 2015-04-23 08:50:16 +08:00 · 2628 次点击
    这是一个创建于 3487 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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不是相同的吗

    4 条回复    2015-04-23 11:34:21 +08:00
    illuz
        1
    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
        2
    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
        3
    insaneDream  
    OP
       2015-04-23 09:10:05 +08:00
    @illuz `T->Right = Insert( X, T->Right );`,如果T->Right==NULL的,那么它就会创建一个新的节点并返回给T->Right, 那么插入的X不是在T->Right这个节点上吗?
    illuz
        4
    illuz  
       2015-04-23 11:34:21 +08:00
    @makubx1 如果不是,就递归处理了,这样 X 就不在 T->Left 上了,所以说是不一定的。(都按 Left 那边来说)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3433 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 04:42 · PVG 12:42 · LAX 20:42 · JFK 23:42
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.