Splay Tree
<aside> 💡 A Splay Tree is a rebalancing tree data structure where data that is constantly accessed at the top of the tree. Splay Trees have an amortized time complexity of $O(log \space n)$ meaning that with n operations the $\frac{total \space time}{n} = log \space n$. The total time of n operations is$\space n \space log \space n$ .
</aside>
<aside> 💡 A splay tree will be fixed after each operation (insertion, deletion, accesses, etc.). Fixed in the context of splay trees means to “splay” the node we inserted, deleted, etc. “Splaying” means to bringing a node to the root.
</aside>
| Operation | Action |
|---|---|
insert() |
Splay the inserted node (move it to the root). |
access() |
Splay the accessed node (move it to the root). |
delete() |
Splay the node (move it to the root), then delete it. |