Saturday, November 30, 2013

Advantages

Here's some of the advantages of splay trees.

First of all, splay trees are much simpler to implement than
other trees such as AVL or red-black trees.  They are basically
plain old binary search trees with one extra operation,
splaying. In the average case, they have performance comparable
to other balanced trees, and they also have a small memory
footprint as they use no more memory than a plain binary search
tree.  For comparison, every node of an AVL tree has an
additional height field, and every node of a red-black tree has
an additional color field. Finally, splay trees have no issue
with identical keys, wheres AVL trees, for example, do not
support identical keys.

No comments:

Post a Comment