自顶向下伸展树。

Question

SplayTree Splay(int e, Position X)
{
    static struct SplayNode Header;
    Position LeftTreeMax, RightTreeMin;
    
    Header.left = Header.right = NullNode;
    LeftTreeMax = RightTreeMin = &Header;
    NullNode->element = e;

    while (e != X->element)
    {
        if (e < X->element)
        {

            if (e < X->left->element)
                X = SingleRotateWithLeft(X);
            if (X->left == NullNode)
                break;
            //将旋转之后的X连接到右侧树上
            RightTreeMin->left = X;
            RightTreeMin = X;
            X = X->left;
        }
        else
        {
            if (e > X->right->element)
                X = SingleRotateWithRight(X);
            if (X->right == NullNode)
                break;

            //后来的x会覆盖之前的啊。
            LeftTreeMax->right = X;
            LeftTreeMax = X;
            X = X->right;
        }
    }
    LeftTreeMax->right = X->left;
    RightTreeMin->left = X->right;
    X->left = Header.right;
    X->right = Header.left;
    return X;
}

这个代码我有个地方不明白：

LeftTreeMax->right = X;
LeftTreeMax = X;

这里，如果我这个树X很深，单旋转了好几次，那么每次旋转不都会把之前保存的给覆盖了，这样最后在连接整理的时候，得到的不就不包含所有的节点。

请大家指教，谢谢~~

这个代码出自数据结构与算法分析，第12章。