伸展树 [数据结构与算法分析 c 语言描述]

1. 概述

知识点

• 伸展树的由来
• 伸展树的概念
• 伸展树的展开

2. 伸展树的想法由来

• 二叉搜索树的最坏情况是一个单链表，复杂度为 O(N)。如果发生最坏的情况很少很少，那么我们的查找速度仍然会很快。
• 对一颗二叉搜索树进行查找，事实证明最经常查的只是其中的一部分。

基于上面，伸展树就孕育而生。
我的理解为，把经常查的关键字放到树的上面，在这个过程中优化我们的树结构；以达到控制我们所说的最坏情况很少很少。

当一个节点被访问后，它就经过一些列的操作（展开）放到跟节点上。

3. 展开

展开在思想上类似于 AVL 树的旋转，设我们要访问的节点为 X。有两种情况：

• X 的父节点为根。
• X 有父亲(P)和祖父(G)。

X 的父亲为根节点：直接旋转 X 跟 根节点。
X 有父亲节点和祖父节点：这里又分两种情况，即是 AVL 树四种情况合并成两种的内部跟外部

• 之字形 内部（左右、右左）。
• 一字型 外部（右右、左左）。

3.1 之字形

看图就明白。很简单

3.2 一字形

看图就明白，很简单

4. 最后

伸展树的节点是动态变化的，一颗最坏情况的二叉搜索树经过展开可以让树逐渐变得平衡。

本作品采用《CC 协议》，转载必须注明作者和本文链接