Splay Tree is a #202112121746, like 202112121857, that could balance itself.
Details
- See on Wikipedia
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