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)


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.)


Reply via email to