树-伸展树(Splay Tree)

伸展树概念

伸展树(Splay Tree)是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。

(01) 伸展树属于二叉查找树,即它具有和二叉查找树一样的性质:假设x为树中的任意一个结点,x节点包含关键字key,节点x的key值记为key[x]。如果y是x的左子树中的一个结点,则key[y] <= key[x];如果y是x的右子树的一个结点,则key[y] >= key[x]。

(02) 除了拥有二叉查找树的性质之外,伸展树还具有的一个特点是:当某个节点被访问时,伸展树会通过旋转使该节点成为树根。这样做的好处是,下次要访问该节点时,能够迅速的访问到该节点。

假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法,在每次查找之后对树进行重构,把被查找的条目搬移到离树根近一些的地方。伸展树应运而生,它是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。

相比于"二叉查找树"和"AVL树",学习伸展树时需要重点关注是"伸展树的旋转算法"。

伸展树实现

伸展树的节点包括的几个组成元素:

(01) key -- 是关键字,是用来对伸展树的节点进行排序的。

(02) left -- 是左孩子。

(03) right -- 是右孩子。

旋转算法

算法描述:rotate left/rotate right –> link left/link right –> assemble

(a):伸展树中存在"键值为key的节点"。 * 将"键值为key的节点"旋转为根节点。

(b):伸展树中不存在"键值为key的节点",并且key < tree->key。

b-1 "键值为key的节点"的前驱节点存在的话,将"键值为key的节点"的前驱节点旋转为根节点。

b-2 "键值为key的节点"的前驱节点不存在的话,则意味着,key比树中任何键值都小,那么此时,将最小节点旋转为根节点。

(c):伸展树中不存在"键值为key的节点",并且key > tree->key。

c-1 "键值为key的节点"的后继节点存在的话,将"键值为key的节点"的后继节点旋转为根节点。

c-2 "键值为key的节点"的后继节点不存在的话,则意味着,key比树中任何键值都大,那么此时,将最大节点旋转为根节点。

上一篇:第一百三十三节,JavaScript,封装库--弹出登录框


下一篇:keras与tensorboard结合使用