雅乐网

计算机技术、学习成长

计算机 » 数据结构 » 常用数据结构C++实现(5):伸展树

常用数据结构C++实现(5):伸展树

伸展树也是一种平衡二叉搜索树,但它的平衡是在平均意义下的。伸展树中n次操作,每次的均摊复杂度是O(logn) 。而单独的一次操作,可能达到O(n)的复杂度。那么,与AVL相比,伸展树的优势又在哪里呢?

伸展树中,每次会把访问到的结点通过单旋和双旋移动到树的根部,这样下次在访问该结点时,就可以极大地节省时间。也就是说,伸展树可以很好地满足数据访问的局部性。假设在一段时间内,访问的元素有k个,k << n ,则伸展树会达到比AVL更好的性能。

此外,伸展树与AVL相比,对平衡的约束较小,因此更加容易实现。

查找和伸展

伸展树中,查找到相应元素后,通过旋转把该结点移动到根部,这个过程为splay(x) 。

这个过程也要用到AVL中的旋转,如果待上升结点为x,要看x的父节点和爷爷结点。具体有2种情况:

1. 2010031717354266

这种情况逐层旋转,x绕p旋转,然后绕g旋转。这和AVL的双旋一致。

2.2010031717355587

这种情况先绕G旋转,再绕P旋转。这种情况和AVL中不一样。

c++实现

https://github.com/yalewoo/cpp-data-structure

SplayBinTree.h

SplayBinTree.cpp

 

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/data_structure_cpp_5_splay_binary_tree.html

上一篇:

下一篇:

我要评论

验证码*: 0 + 1 =