1. 概述
知识点
- 伸展树的由来
- 伸展树的概念
- 伸展树的展开
2. 伸展树的想法由来
- 二叉搜索树的最坏情况是一个单链表，复杂度为 O(N)。如果发生最坏的情况很少很少，那么我们的查找速度仍然会很快。
- 对一颗二叉搜索树进行查找，事实证明最经常查的只是其中的一部分。
基于上面，伸展树就孕育而生。 我的理解为，把经常查的关键字放到树的上面，在这个过程中优化我们的树结构；以达到控制我们所说的最坏情况很少很少。
当一个节点被访问后，它就经过一些列的操作（展开）放到跟节点上。
3. 展开
展开在思想上类似于 AVL 树的旋转，设我们要访问的节点为 X。有两种情况：
- X 的父节点为根。
- X 有父亲(P)和祖父(G)。
X 的父亲为根节点：直接旋转 X 跟 根节点。 X 有父亲节点和祖父节点：这里又分两种情况，即是 AVL 树四种情况合并成两种的内部跟外部
- 之字形 内部（左右、右左）。
- 一字型 外部（右右、左左）。
3.1 之字形
看图就明白。很简单
3.2 一字形
看图就明白，很简单
4. 最后
伸展树的节点是动态变化的，一颗最坏情况的二叉搜索树经过展开可以让树逐渐变得平衡。
