Lenky个人站点

下面给出伸展树的自顶向下伸展的伪码，其中的L、R分别表示左树和右树且初始值为空，M为中树且初值为原伸展树；X为待查节点，T为M的根节点。 FUNC top-down-splay DO IF X小于T THEN IF... [阅读更多]

假设在当前伸展树中的X节点处进行伸展，X的父亲节点为P(X)（如果X的父亲节点存在），X的祖父节点为G(X)（如果X的祖父节点存在）。 从前面的讲述，我们知道自底向上伸展的方法是在完全查找完之后再进行的伸展操作（如果找到待查节点X，就在节点X处进行伸展操作；如果未找到待查节点X即遇到了空节点，就在最后一个非空节点处进行伸展操作），而自顶向下伸展将在节点查找的过程中就同时进行着伸展操作。 自顶向下伸展操作将伸展树分为三部分： 左树：包含所有已经知道比待查节点X小的节点。 右树：包含所有已经知道比待查节点X大的节点。 中树：包含所有其它节点。 在中树自根向下进行节点查找（每次向下比较两个节点），根据查找情况将中树中的节点移动（此处的移动是指将节点和中树的连接断开，而将节点连接到左或右树的适当位置。）到左树或右树（如有必要则会先对中树进行旋转再进行节点移动）。 初始状态时，左树和右树都为空，而中树为整个原伸展树。随着查找的进行，左树和右树会因节点的逐渐移入变大，中树会因节点的逐渐移出变小。最后查找结束（找到或遇到空节点）时组合左中右树并是伸展树自顶向下伸展方法的最终结果。 下图所给旋转为b的左右子树都存在时，并且图中只画出了待查节点比a小的情况，比a大的情况可由对称关系推出。伸展树的自顶向下伸展示意图： ... [阅读更多]

几个图就可以看明白了，伪码一的旋转过程以及结果： 伪码二的旋转过程以及结果： 结论：前述的两种伸展伪码对于同一伸展树在同一节点开始伸展最后得到的伸展树结构不一定完全一致。 ... [阅读更多]

假设在当前伸展树中的X节点处进行伸展，X的父亲节点为P(X)（如果X的父亲节点存在），X的祖父节点为G(X)（如果X的祖父节点存在）。伸展树的自底向上伸展伪码为： FUNC bottom-up-splay DO IF... [阅读更多]

假想这么一种情况，我们想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更短，那些查频率比较高的节点就应该经常处于比较靠近树根的位置，于是最直观的想法就是将每次查找访问的节点都放到树根处，这样再次查找该节点时将会很快的找到该节点。在每次查找访问节点之后对该树进行重构，将被查找的节点搬移到树根，这种自调整型式的二叉查找树就是splay... [阅读更多]