# Re: [hackathon] FreeTree is FreeList on autotune

```On 5/5/15 2:23 PM, Timon Gehr wrote:
```
```- Perhaps it would make sense to splay instead of rotating to root?
```

```
```
Just read the wikipedia article... haven't done anything related to splay trees since college!
```
```
Looks like my code effectively implements a splay tree for the simple reason that all successful find operations are followed by remove, and all insertions are at root.
```
Per Wikipedia:

* Insertion
To insert a value x into a splay tree:

Insert x as with a normal binary search tree.
Splay the newly inserted node x to the top of the tree.

```
(my note: that's what I do, and I suspect for a leaf rotating to the root is identical to splaying to the root)
```
ALTERNATIVE:

```
Use the split operation to split the tree at the value of x to two sub-trees: S and T. Create a new tree in which x is the root, S is its left sub-tree and T its right sub-tree.
```
* Deletion

```
To delete a node x, use the same method as with a binary search tree: if x has two children, swap its value with that of either the rightmost node of its left sub tree (its in-order predecessor) or the leftmost node of its right subtree (its in-order successor). Then remove that node instead. In this way, deletion is reduced to the problem of removing a node with 0 or 1 children. Unlike a binary search tree, in a splay tree after deletion, we splay the parent of the removed node to the top of the tree.
```
```
(my note: that's what I do except the splaying the parent part, which I need to think whether it's useful)
```
```
(Another note: I need to optimize for the pattern remove node/reinsert same node, perhaps with a quick test upon insertion whether I can just make the new node the root.)
```

Andrei

```