Splay Tree

Splay Tree is a #202112121746, like 202112121857, that could balance itself.

Details

Analysis

  • It guarantees M of consecutive tree operations will only take \(O(M \log N)\) of time
  • There will no bad input sequence in this Tree which will improve future operations
  • This Tree will have a \(O(\log N)\) amortised cost per operation
  • The worst case time cost for all operations is \(O(N)\) which is infrequent
  • This Tree is simpler to program compare to 202112121857
Links to this page
#data-structure #tree