AVL树
- 目标：加快搜索
- 工具：BST
- 困难：Tp = O( height ), but the height can be as bad as O( N ).
平均搜索时间
默认：
The height of an empty tree is defined to be –1.
同理，只有一个节点的高度是0
一个空的二叉树是高度平衡的
If T is a nonempty binary tree with and as its left and right subtrees, then T is height balanced
(1) TL and TR are height balanced, and
(2) | hL - hR | ≤ 1 where hL and hR are the heights of TL and TR , respectively.
注意BF的取值只有可能是 -1，0，1
进行一次简单的旋转，就是把MAY的节点往上抬
- RR旋转
The trouble maker Nov is in the right subtree’s right subtree of the trouble finder Mar. Hence it is called an RR rotation.
也就是说最后一次插入的节点位于出现问题的节点的右边的右边
出现问题的节点不一定是根结点
- LR旋转
插入节点之后出现在了出问题节点的左边的右边，我们就称为LR旋转
- RL旋转
插入节点之后出现在了出问题节点的右边的左边，我们就称为LR旋转
Let nh be the minimum number of nodes in a height balanced tree of height h. Then the tree must look like
我们从中引入非波拉契数
Tp = O( h )where h is the height of the tree.因此我们可以得到搜索AVL树的时间复杂度是
Splay树
- 目标：Any M consecutive tree operations starting from an empty tree take at most O(M log N) time.
- 执行下面的旋转的操作
- 执行插入操作
Splaying not only moves the accessed node to the root, but also roughly halves the depth of most nodes on the path.
伸展不仅将访问节点移动到根节点，而且还将路径上大多数节点的深度大致减半。
执行上面的操作，使得更加完善和严谨
- 执行删除操作
- 均摊分析
- 目的：Any M consecutive operations take at most O(M log N) time.
- 均摊分析时间的边界界限
- worst-case bound ≥ amortized bound ≥ average-case bound
- 聚合分析
Show that for all n, a sequence of n operations takes worst-case time T(n) in total. In the worst case, the average cost, or amortized cost, per operation is therefore T(n)/n.
证明对于所有n个操作，n个操作的序列在最坏情况下的总时间为T(n)。因此，在最坏情况下，每次操作的平均开销(或平摊开销)为T(n)/n。
- 核算方法
Accounting method
如下面所表示的一样进行分析
对splay树进行均摊分析
zig操作
zig-zag操作
zig-zig操作
使用摊还分析
势能分析方法
关键词：
算法 复杂度分析 势能分析法在算法复杂度分析过程中，势能分析法是一种非常重要的技术。本文详细介绍了势能分析的思路和原理，并用几个例子加以具体说明。
1.简述
势能分析是一种非常重要的复杂度分析方法，它和其他的一些分析方法可以认为是本质相同的。尤其是面对一些简单问题的时候，我们可能会感觉它们没什么差别。但是当遇到复杂的情形的时候，累加法、借款贷款法就不是那么方便和直观了。它可以帮我们理性分析一些经常被感性理解的复杂度，或者是帮我们证明一些算法即便在某些情况下很耗时但是均摊上依然很优秀。
它的英文 Amortized Analysis 也翻译作摊还分析，这个翻译其实更直观一些。它所做的事情其实就是把消耗大的操作给消耗小的操作“匀”一点，这就是摊还/平摊。那么到底应该怎么“匀”？什么情况下“匀”？我们可以用形式化的语言来简洁明了地描述这件事。
2.数学语言
计算每一步的代价
3.为什么我们要这样做
为什么要这么做呢？这看起来这是一个很无聊的事情，我们给一个和式加了一个正数，显然变大了；然后把这个正数拆成了许多个数的和，分散拆到了和式的每一项里。这整个过程非常的 trivial ，看不出来有什么意义。
想要理解势能的意义，我们只需要一个口诀即可：让消耗大的那一步操作势能大大的降！这个口诀可以帮助我们理解势能的意义。我们把每一步的代码看成了：原本的代价+势能的变化。所以如果原本的代价很大我们让势能大下降，这样就把原本的代价抵消了，也就是所谓的摊还。当然这样做当然不是无止境的，不能每一步都让势能下降，毕竟最终我们要求终点的势能是要大于起点的势能的。所以到时候让代价小的操作的势能上升就可以实现把代价大的操作的代价摊到代价小的操作上了。
那么这样的正确性是很显然的啦，我们不要去想每一步亏了多少赚了多少，我们只需要知道我们最开始的那个式子：最终势能相较于一开始是上升的，所以我们这样做只会让总体的代价变大，对于分析上界不会带来问题。
4.一些例子
splay树
势能分析面对这种类型的数据结构会非常有优势，它们往往单次操作最坏复杂度很高，但是均摊复杂度很优秀，一般来说这种数据结构也比较好写。
课件上不加说明的直接给出了势能函数，然后简单分类讨论了一下证明了复杂度的正确性。分类讨论比较无趣冗杂，课件和网络上资料也很多，这里我们主要讨论这个势能函数是怎么想到的。
其实还是那个口诀：让消耗大的那一步操作势能大大的降！
考点是AVL树的插入操作如何执行
根据旋转以及变换之后可以得到答案B
重点在于模拟一下AVL树的旋转
这道题目还是比较复杂的，因此需要熟悉每一步的操作，然后细致一点就可以做出来，答案选D
注意splay树的三种操作
(T) The result of inserting keys 1 to 2k−1 for any k>4 in order into an initially empty skew heap is always a full binary tree.
(T) The right path of a skew heap can be arbitrarily long.
(T) All of the Zig, Zig-zig, and Zig-zag rotations not only move the accessed node to the root, but also roughly half the depth of most nodes on the path.
这道题就是纯定义，比较玄学，回归ppt重看
回归最原本的思想，因此答案选D
消耗大的那一步操作势能大大的降！
这是基本的原则，并且刚开始的时候势能函数取到最小值
把左子树的最大子节点移到根节点，或者把右子树的最小子节点移到跟节点，然后再在原来的树的基础上进行相应的正常操作即可
注意
balance factor 的概念
- 首先复习一下什么是完全二叉树，最后一层不一定全部填满，如果最后一层全部填满，那叫做完美二叉树
- 在一个B树中访问索引项时，如果是倒排文件索引，那么范围搜索是昂贵的。
- 倒排文件索引是一种索引方法，通常用于全文搜索，其中索引项指向含有特定关键字的文档或记录。在B树中进行范围搜索意味着必须访问多个索引项，并且可能涉及多个磁盘读取操作，这使得操作成本较高。
所以我们希望这个操作前后势能可以对应地下降。那么这个操作对局面的改变是什么呢？当然是栈里的元素变少了。所以我们又能很自然的想到势能函数：栈里的元素个数。这样的话 k-pop 虽然耗时，但是也让元素个数对应的变少，进而使得势能下降。
因此，关键点就是让那个消耗大的步骤的势能大大降低
因此，在完成ads势能分析的题目的时候，我们只需要思考：
- 思考什么操作的代价最大
- 思考这个操作会对局面产生什么样的影响，局面会发生什么变化
- 如何把这种方法进行量化，将这种变化映射到势能函数的降低上面去
- 记住一个重要的思想：势能函数的作用是将消耗大的步骤的势能大大降低