[hackathon] FreeTree is FreeList on autotune

[Andrei Alexandrescu via Digitalmars-d-announce]

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