Splay的插入操作
正如前篇博文所讲的，Splay树是一种自平衡的数据结构，最后一个访问的键总是根。插入操作和二叉搜索树的插入类似，额外多了一些步骤来保证新插入的键称为新的根节点。
以下是插入键值k到一个Splay Tree的不同情况
- root是空：我们简单的分配一个新的节点，并将它作为root返回
- splay（伸展）给定的键值k。如果k已经存在，那么它称为新的根节点。如果不存在，那么最后访问的叶子节点称为新的根节点。
- 如果新的根节点和k相同，什么都不做因为k已经存在了。
- 否则，分配内存产生新的节点，并且将k和根的键值比较。
- 如果k比根的键值小，将root作为新节点的右孩子，复制root的左孩子作为新节点的左孩子，并且使root的左孩子置为NULL。
- 如果k比跟的键值大，将root作为新节点的左孩子，复制root的右孩子作为新节点的右孩子，并且使root的右孩子置为NULL。
- 将新节点返回，作为整棵树的根。
感觉Splay很大程度上是可以基于AVL树进行修改的，其中左旋、右旋、左右旋、右左旋操作是相同的，只是splay有splay操作。具体实现有时间会仔细看看，在下面参考的链接中有。
参考
https://www.geeksforgeeks.org/splay-tree-set-2-insert-delete/?ref=lbp