Splay树

伸展树,添加,删除,等一些列操作后都需要执行一个splay的操作,整个平衡树的核心就是splay操作,通常是讲某个节点splay到根部,splay操作的复杂度是O(logn)。伸展树其实很简单,但是写起来有一种淡淡的忧伤,毕竟代码量很大。

基本旋转操作:

rotate

在基础旋转操作上的旋转操作:

zig

zig-zig

zig-zag

以上旋转操作时限了splay树的splay操作,splay树的所有操作都基于splay操作,此操作让splay树的复杂度均摊是logn

伪静态版:

 

静态版:

 

动态版:

LEAVE A COMMENT