伸展树学习笔记之逐层伸展

痛定思痛。 2022-05-26 04:55 114阅读 0赞

# 伸展树 #

![70][]

# **一. 局部性** #

*  **Locality: 刚被访问过的数据，极有可能很快地再次被访问，这一现象在信息处理过程中屡见不鲜。**
 *  **BST: 刚刚被访问过的节点，极有可能很快地再次被访问；下一个将要访问的节点，极有可能就在刚被访问过节点的附近。**
 *  **连续的m次查找（m>>n=|BST|）,采用AVL共需O(mlogn)时间**

# **二. 自适应调整** #

![70 1][]

**对于典型的线性结构列表，所有元素按照它们之间的逻辑关系，排列成一个线性的序列。相邻的元素通过引用，确立前驱和后继关系。对任何一个元素的访问效率，将主要取决于它在这个序列中所具有的秩。**

*  **越靠前的元素，秩越小，访问的效率越高**
 *  **越靠后的元素，秩越大，访问的效率越低**

![70 2][]

**一旦有某个元素刚刚接受访问，立即将它移动到这个序列的最前端。因为根据局部性，接下来要访问的元素，很有可能就是我们刚刚访问的那个元素的。**

![70 3][]

**经过了足够长时间的使用之后，某一时间内，被集中访问的那些元素，都会集中到这个列表的前端去，提高访问效率。**

![70 4][]

**将BST树的画法旋转90度，在BST位于顶部的元素，访问效率相对要高，可以借助局部性，将经常要访问的元素，尽可能移送到更加接近树根的位置，也就是要尽可能地降低它们的深度。**

# 三. 旋转 #

## 3.1 之字形 ##

![70 5][]

![70 6][]

**栗子.......................................................................................................................**

![70 7][]

## 3.2 一字形 ##

![70 8][]

![70 9][]

**栗子.......................................................................................................................**

![70 10][]![70 11][]

![70 12][]

**栗子1：................................................................................................................................**

![70 13][]

![70 14][]

**栗子2：................................................................................................................................**

![70 15][]

**栗子3：................................................................................................................................**

![70 16][]

**栗子4：................................................................................................................................**

![70 17][]

# **四. 逐层伸展** #

**![70 18][]**

**访问一次结点 ，完成一次称为展开的过程**

*  **节点v一旦被访问，随即转移至树根，通过zig或者zag变换**
 *  **自下而上，逐层单旋**
 *   **zig(v->parent)**
 *   **zag(v-parent)**
 *  **指到v最终被推送至根**

# **五. 例子** #

**step1: 需要访问333**

**![70 19][]**

**step2:**

**![70 20][]**

**step3:**

**![70 21][]**

**step4:**

**![70 22][]**

**step5:**

**![70 23][]**

**step6: 最终抵达树根**

**![70 24][]**

# **六. 最坏情况** #

**![70 25][]**

# **七. 插入Insert** #

![70 26][]

![70 27][]![70 28][]

![70 29][]

# **八. 联合Join** #

# ![70 30][] #

![70 31][]

# 九 删除Delete #

![70 32][]

![70 33][]

![70 34][]

![70 35][]

(参考：[https://web.stanford.edu/class/cs166/lectures/10/Slides10.pdf][https_web.stanford.edu_class_cs166_lectures_10_Slides10.pdf])

#  #

[70]: /images/20220526/68af7908a6ae4dadb5355a5fa8fc7989.png
[70 1]: /images/20220526/c8ca24c02d514e5c8712e3df7879297b.png
[70 2]: /images/20220526/0b4900bff20940268970159dca4c337e.png
[70 3]: /images/20220526/c032ac571015415f81fc8c37f89d7e16.png
[70 4]: /images/20220526/c97907913a254a63b49d7b4ee26c7c2e.png
[70 5]: /images/20220526/61f1b2806ba0431a8267919f91de054e.png
[70 6]: /images/20220526/775d3f98a8bc4cb2b30c76437cc89643.png
[70 7]: /images/20220526/bdfa6190c0e7417584a9b5d868a8693c.png
[70 8]: /images/20220526/b36b66dcad084ef7a88d8fde39ba578b.png
[70 9]: /images/20220526/017920694e5a42dba036f39a8d8dff80.png
[70 10]: https://img-blog.csdn.net/20180904150154690?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 11]: /images/20220526/4f9f8f450eac4cbeb72f492a9f6611a8.png
[70 12]: /images/20220526/cca9c3004c5840e5bde3db57b8edd3cd.png
[70 13]: /images/20220526/1a6c327c23b74a9b88a517a78b32a294.png
[70 14]: /images/20220526/e82daf401af3472794052638b8ff51e1.png
[70 15]: /images/20220526/bd789e25f6d6492f86fefc95c39bce11.png
[70 16]: /images/20220526/8e3ef7e0c9b64b57985279050258bd6c.png
[70 17]: /images/20220526/c1490ac7f16d4d91a649e896a7e6f75d.png
[70 18]: /images/20220526/4cb8c5d9a04a44618fd5960781e11080.png
[70 19]: /images/20220526/1bd29d4d493a4d778023f96e95e41287.png
[70 20]: /images/20220526/9d697129792e4e84a75e3d586dbcf196.png
[70 21]: /images/20220526/86f0709bfda44a88b99254bb219d8a9c.png
[70 22]: /images/20220526/8e65ab39ddae442da60386ace2fc03a8.png
[70 23]: /images/20220526/e5bc00bcaa9e470a90a3e0d841d93cae.png
[70 24]: /images/20220526/c057fe7b970340219658f3305651ce66.png
[70 25]: /images/20220526/ead3dcba36cd4141adab0e17c2e7a9aa.png
[70 26]: /images/20220526/1812d5ff8ba246bd93d61b44f8b574df.png
[70 27]: https://img-blog.csdn.net/20180904103032259?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 28]: /images/20220526/c5567c8a3253458daa2dfd21fda1353b.png
[70 29]: /images/20220526/2148510c6bf04a5d985ea617078a0525.png
[70 30]: /images/20220526/1990e344bdee4a99830bf6c326b32710.png
[70 31]: /images/20220526/c4a123dc54ed4393a804f42c60834aec.png
[70 32]: /images/20220526/29345e8f91fc4f92aae04ea8be1fac2c.png
[70 33]: /images/20220526/ae19f2e11e0e43738c64b4a3b44e35cc.png
[70 34]: /images/20220526/c0790341d0d747e3a016f16f9262e79b.png
[70 35]: /images/20220526/826637a386c54c5bbcb4680a8de7e5fc.png
[https_web.stanford.edu_class_cs166_lectures_10_Slides10.pdf]: https://web.stanford.edu/class/cs166/lectures/10/Slides10.pdf