Splay Tree - Advantages

Advantages

Good performance for a splay tree depends on the fact that it is self-optimizing, in that frequently accessed nodes will move nearer to the root where they can be accessed more quickly. The worst-case height—though unlikely—is O(n), with the average being O(log n). Having frequently used nodes near the root is an advantage for nearly all practical applications (also see Locality of reference), and is particularly useful for implementing caches and garbage collection algorithms.

Advantages include:

  • Simple implementation—simpler than other self-balancing binary search trees, such as red-black trees or AVL trees.
  • Comparable performance—average-case performance is as efficient as other trees.
  • Small memory footprint—splay trees do not need to store any bookkeeping data.
  • Possibility of creating a 'persistent data structure' version of splay trees—which allows access to both the previous and new versions after an update. This can be useful in functional programming, and requires amortized O(log n) space per update.
  • Working well with nodes containing identical keys—contrary to other types of self-balancing trees. Even with identical keys, performance remains amortized O(log n). All tree operations preserve the order of the identical nodes within the tree, which is a property similar to stable sorting algorithms. A carefully designed find operation can return the leftmost or rightmost node of a given key.

Read more about this topic:  Splay Tree

Famous quotes containing the word advantages:

    But there are advantages to being elected President. The day after I was elected, I had my high school grades classified Top Secret.
    Ronald Reagan (b. 1911)

    When the manipulations of childhood are a little larceny, they may grow and change with the child into qualities useful and admire in the grown-up world. When they are the futile struggle for love and concern and protection, they may become the warped and ruthless machinations of adults who seek in the advantages of power what they could never win as children.
    Leontine Young (20th century)

    If we help an educated man’s daughter to go to Cambridge are we not forcing her to think not about education but about war?—not how she can learn, but how she can fight in order that she might win the same advantages as her brothers?
    Virginia Woolf (1882–1941)