摊还分析-伸展树
一字形旋转
类似于之字形旋转，这里作为练习的尝试解答。
一字形旋转
重要的不等式
%20%3D%20R_i(G)%20%5Ctag%7B1%7D%0A#card=math&code=R_f%28X%29%20%3D%20R_i%28G%29%20%5Ctag%7B1%7D%0A&id=QfAhr)
旋转前的树根节点是G，旋转后的树根节点是X。根的后裔个数S(i)不变，同样，根的秩R也不变。
%20%5Cge%20R_f(P)%20%5Ctag%7B2%7D%0A#card=math&code=R_f%28X%29%20%5Cge%20R_f%28P%29%20%5Ctag%7B2%7D%0A&id=QDl0t)
旋转后X是P的父节点，故X的秩大于P的秩。
%20%5Cle%20Ri(P)%20%5Ctag%7B3%7D%20%0A#card=math&code=R%7Bi%7D%28X%29%20%5Cle%20R_i%28P%29%20%5Ctag%7B3%7D%20%0A&id=INvt1)
同理，旋转前X是P的左（右）孩子，故X的秩小P的秩。
%7D%20%2B%20S_f(G)%20%5Cle%20S_f(X)%20%5Ctag%7B4%7D%0A#card=math&code=S_i%7B%28X%29%7D%20%2B%20S_f%28G%29%20%5Cle%20S_f%28X%29%20%5Ctag%7B4%7D%0A&id=UCBAL)
旋转前，X有子树A和B；旋转后G有子树C和D，X有子树A和P（包含子树B，C，D和结点G）。旋转后X的后裔数量不少于前两者的和。
由上式，结合不等式（见书上）可以导出，
%20%2B%20Rf(G)%20%5Cle%202R_f(X)%20-%202%20%5Ctag%7B5%7D%0A#card=math&code=R%7Bi%7D%28X%29%20%2B%20R_f%28G%29%20%5Cle%202R_f%28X%29%20-%202%20%5Ctag%7B5%7D%0A&id=z3TgG)
证明过程
%20%2B%20Rf(P)%20%2BR_f(G)%20-%20R_i(G)%20-%20R_i(P)%20-%20R_i(X)%20%5C%5C%0A%20%3D%26%202%20%2B%20R_f(P)%20%2BR_f(G)%20-%20R_i(P)%20-%20R_i(X)%20%5C%5C%0A%20%5Cle%26%202%20%2B%20R_f(X)%20%2B%20R_f(G)%20-%20R_i(P)%20-%20R_i(X)%20%5C%5C%0A%20%5Cle%26%202%20%2B%20R_f(X)%20%2B%20R_f(G)%20-%202R_i(X)%20%5C%5C%0A%20%5Cle%26%202%20%2B%20R_f(X)%20%2B%20%5B2R_f(X)%20-%202%20-%20R_i(X)%5D%20-%202R_i(X)%20%5C%5C%0A%20%3D%26%203(R_f(X)%20-%20R_i(X))%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0AAT%7Bzig-zig%7D%20%3D%26%202%20%2B%20R_f%28X%29%20%2B%20R_f%28P%29%20%2BR_f%28G%29%20-%20R_i%28G%29%20-%20R_i%28P%29%20-%20R_i%28X%29%20%5C%5C%0A%20%3D%26%202%20%2B%20R_f%28P%29%20%2BR_f%28G%29%20-%20R_i%28P%29%20-%20R_i%28X%29%20%5C%5C%0A%20%5Cle%26%202%20%2B%20R_f%28X%29%20%2B%20R_f%28G%29%20-%20R_i%28P%29%20-%20R_i%28X%29%20%5C%5C%0A%20%5Cle%26%202%20%2B%20R_f%28X%29%20%2B%20R_f%28G%29%20-%202R_i%28X%29%20%5C%5C%0A%20%5Cle%26%202%20%2B%20R_f%28X%29%20%2B%20%5B2R_f%28X%29%20-%202%20-%20R_i%28X%29%5D%20-%202R_i%28X%29%20%5C%5C%0A%20%3D%26%203%28R_f%28X%29%20-%20R_i%28X%29%29%0A%5Cend%7Baligned%7D%0A&id=EXPte)
