注本文旨在让菜鸟掌握Splay的各种操作大牛勿看勿鄙视-Read.PDFVIP

伸展树操作详解 By Ma Shuo 注：本文旨在让菜鸟掌握 Splay 的各种操作，大牛勿看、勿鄙视 一、二叉有哪些信誉好的足球投注网站树(BST——Binary Search Tree) 二叉有哪些信誉好的足球投注网站树是一颗满足如下性质的二叉树：左子树值=根节点值=右子树值。因此理 论上我们可以在 O(logN) 的时间内完成插入、删除、查找等操作。是一种在“动态维护”中 效果相当不错的数据结构。但由于题目数据的原因，可能造成二叉查找树并不平衡（严重的 时候可能退化为线性），致使插入、删除、查找等操作的复杂度退化为 O(N) 。为了尽量保持 二叉有哪些信誉好的足球投注网站树的平衡，我们需要去维护二叉有哪些信誉好的足球投注网站树——平衡二叉树。 二、平衡二叉树(BBST——Balance Binary Search Tree) I、首先介绍所有平衡二叉树都需要进行的操作——旋转(Rotate) 下面我们以右旋（ZIG ）为例来分析旋转操作，我们想把 X 通过右旋旋转到目前 Y 的 位置。我们知道 Y 的左子树中所有节点权值都小于等于 Y ，于是我们完全可以让 X 的 右子树去充当 Y 的左子树，由于Y 节点权值大于 X ，我们又可让 Y 来充当 X 的右子树， 通过这样的旋转操作，X 便到了目前 Y 的位置。 II、一般常用的平衡二叉树有如下两类： 1、Treap ：即Tree+Heap，为每一个节点随机引入一个权值，通过维护这些权值满足堆 的性质来尽量保证树的平衡。由于随机权值的引入，能尽量保证树的平衡性，但仍 然会存在不稳定的因素。 2 、Splay：即本文所要讲解重点——伸展树。伸展树不能保证每次操作都是O(logN) 的 复杂度，但却能保证 m 次操作的复杂度为 O(mlogN)，伸展树的复杂度分析采用了 平摊的思想，利用会计方法进行证明。 III、严格保持平衡的树——AVL ： AVL 通过平衡因子的引入，使一颗树左右子树的树高差严格保持不大于 1。因此在 所有平衡二叉树中，AVL 的效果最好，但其编程复杂度较大，在平衡编程复杂度与时 间效率的情况下，不推荐使用。 伸展树操作详解 By Ma Shuo 三、伸展树(Splay) 在此将通过程序语言的描述更加形象的解读伸展树的各种操作。 1、程序初始化部分： 我们观察到，二叉有哪些信誉好的足球投注网站树的许多操作具有对称性，因此我们完全可以利用这种对称 性将涉及到左右子树的两个操作合并为同一个，这样便可大大降低编程复杂度。 其中关键便是对于某一节点左右儿子的纪录： Sons:Array[1..MaxP,1..2] Of LongInt; 另外我们仍然需要纪录的便是某一节点的父节点以及以这一节点构成的子树共有 多少节点。 Father,Count:Array[1..MaxP] Of LongInt; 2 、旋转操作 3、伸展操作 伸展操作 Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转操作将伸展 树 S 中的元素 x 调整至树的根部的操作。 在旋转的过程中，要分三种情况分别处理： 1)Zig 或Zag操作：节点 x 的父节点y是根节点。 2) Zig-Zig 或Zag-Zag操作：节点 x 的父节点y不是根节点，且 x 与y同时是各 自父节点的左孩子或者同时是各自父节点的右孩子。 伸展树操作详解 By Ma Shuo 3)Zig-Zag 或 Zag-Zig操作：节点 x的父节点 y不是根节点，x 与y 中一个是其父节点 的左孩子而另一个是其父节点的右孩子。 4、 查