伸展树splay单旋PK双旋

为什么要有双旋转呢？遇到左孩子就右转，右孩子就左转不行么？

试想一下如果当前是一条链的话，在查询完最深的节点后，只用N个单旋把节点单旋上去的话，splay操作后的树仍然是一条链，如图1-1至图1-5：

Splay <wbr>Tree

Splay <wbr>Tree

Splay <wbr>Tree

Splay <wbr>Tree

Splay <wbr>Tree

但若是用双旋的话情况就不同了，如图2-1至2-5：



Splay <wbr>Tree



Splay <wbr>Tree

Splay <wbr>Tree

Splay <wbr>Tree

Splay <wbr>Tree

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/noip/p/3111169.html