# Implement the «splay tree» data structure (an adaptively
# self-balancing binary search tree). Provide at least the following
# operations:
#
#  • ‹insert›  – add an element to the tree (if not yet present)
#  • ‹find›    – find a previously added element (return a ‹bool›)
#  • ‹erase›   – remove an element
#  • ‹to_list› – return the tree as a sorted list
#  • ‹filter›  – remove all elements failing a given predicate
#  • ‹root›    – obtain a reference to the root node
#
# Nodes should have (at least) attributes ‹left›, ‹right› and
# ‹value›. The class which represents the tree should be called
# ‹SplayTree›.

# You can find the required algorithms online (wikipedia comes to
# mind, but also check out ‹https://is.muni.cz/go/uvcjn9› for some
# intuition how the tree works).

# The main operation is ‘splaying’ the tree, which moves a
# particular node to the root, while rebalancing the tree. How
# balanced the tree actually is depends on the order of splay
# operations. The tree will have an «expected» logarithmic depth
# after a random sequence of lookups (splays). If the sequence is
# not random, the balance may suffer, but the most-frequently looked
# up items will be near the root. In this sense, the tree is
# self-optimizing.

# Note: it's easier to implement ‹erase› using splaying than by using
# the ‘normal’ BST delete operation:
#
#  1. splay the to-be-deleted node to the root, then
#  2. join its two subtrees L and R:
#     ◦ use splay again, this time on the largest item of the
#       left subtree L,
#     ◦ the new root of L clearly can't have a right child,
#     ◦ attach the subtree R in place of the missing child.