I am working on optimizing the Delete-Max operation in an unbalanced Binary Search Tree (BST) where frequent max deletions occur. The current approach follows:

1. Traverse to the rightmost node.
2. Remove it and adjust its parent’s reference.
3. If the removed node had a left subtree, replace it with the largest node from that subtree

Problems Faced:

• Frequent max deletions lead to an unbalanced tree, degrading search and deletion performance.
• The worst-case complexity turns into O(n) instead of O(log n) when the tree becomes skewed.

Would an AVL Tree or a Red-Black Tree be a better choice to maintain balance with frequent deletions? Are there alternative tree structures that handle frequent deletions more efficiently?