Recall the properties of a balanced BST (AVL or Red-Black Tree) and how they ensure O(log n) time complexity for insertion, deletion, and search operations.

Consider how maintaining balance during insertions and deletions affects the tree structure and what operations are required to restore balance (rotations, recoloring, etc.).

Think about how to adapt the standard BST operations (insert, delete, search) to maintain the balance property of the chosen tree (AVL or Red-Black) while ensuring the set remains sorted.