前言 Splay（伸展树）是一种灵活多变的高级数据结构，可以很方便的执行各种动态的区间操作。由丹尼尔·斯立特 Daniel Sleator 和罗伯特·恩卓·塔扬 Robert Endre Tarjan 在 1985 年发明。 Splay 是一颗二叉搜索树，它建立在二叉搜索树（BST）之上，当然也是平衡树的一种，下面简单介绍一下 BST 与平衡树： 首先介绍 BST，也就是所有平衡树的开始，他的名字是二叉查找树. 给定一棵二叉树，每一个节点有一个权值,命名为关键码，而 BST 性质就是，对于树中任何一个节点…