On 5/5/15 2:23 PM, Timon Gehr wrote:

- Perhaps it would make sense to splay instead of rotating to root?

## Advertising

`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