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
