是否存在满足指定时间复杂度要求的特殊数据结构？

Awesome question! Let's dive into a data structure that checks all your boxes, and break down how each operation meets the specified time complexity requirements.

核心结构：带子树大小追踪的平衡二叉搜索树（如AVL树或红黑树） #

This structure combines the ordered properties of a binary search tree (BST) with balance guarantees (to keep operations logarithmic) and subtree size tracking (to quickly locate the median/middle element).

1. Build(L, X) - O(n) 时间构建 #

To construct the structure S from an unsorted list L of n elements:

• Use quickselect (a linear-time algorithm for finding the k-th smallest element in an unsorted array) to locate the element defined by parameter X (typically the median, or a specific rank to use as the tree root). For the full list, this takes O(n) time.
• Set this element as the root of the tree.
• Split L into three groups: elements smaller than the root, the root itself, and elements larger than the root.
• Recursively build the left subtree from the smaller elements, and the right subtree from the larger elements.
• For every node, store the size of its subtree (count of nodes in the node + left subtree + right subtree). This value can be computed in constant time during the recursive build by summing the sizes of the left and right children plus one.

The total time complexity is O(n) because each level of recursion processes O(n) total elements (summing across all sublists), and the sum of quickselect operations across all levels converges to O(n).

2. Insert(y, S) - O(log n) 时间插入 #

• Perform a standard balanced BST insertion: traverse the tree to find the correct position for element y, insert it as a leaf node.
• Update the subtree size values for all ancestors of the new node (each update is a constant-time operation).
• Perform balance adjustments (rotations for AVL/red-black trees) to maintain the tree's balanced height—this takes O(log n) time since the tree's height is guaranteed to be O(log n).

3. DEL-MIN(S) - O(log n) 时间删除最小元素 #

• The smallest element in a BST is always the leftmost node (follow left child pointers until there are no more left children).
• Delete this node using standard balanced BST deletion logic, which handles cases where the node has 0, 1, or 2 children.
• Update subtree sizes for all ancestors and rebalance the tree if needed. All steps take O(log n) time.

4. DEL-MAX(S) - O(log n) 时间删除最大元素 #

• The largest element in a BST is always the rightmost node (follow right child pointers until there are no more right children).
• Delete this node using standard balanced BST deletion logic, update subtree sizes for ancestors, and rebalance the tree if required. This operation is O(log n) time.

5. DEL-MId(S) - O(log n) 时间删除中间元素 #

Assuming "middle element" refers to the median (the element at rank ceil(n/2) or floor(n/2) in the sorted list of elements in S):

• Use the subtree size values to traverse the tree and locate the node with the target rank. For example, if the total number of nodes is 7, we look for the 4th smallest element. This traversal takes O(log n) time because each step uses the left subtree size to decide whether to move left or right.
• Delete this node using standard balanced BST deletion logic, update subtree sizes for all ancestors, and rebalance the tree. All steps are O(log n) time.

为什么这个结构可行？ #

• Balance guarantees from AVL or red-black trees ensure that all traversal, insertion, and deletion operations stay within O(log n) time, as the tree height is always logarithmic in the number of nodes.
• Subtree size tracking lets us quickly locate the median without sorting the entire structure each time, which is key for the DEL-MId(S) operation's efficiency.
• The recursive build with quickselect avoids the O(n log n) cost of sorting the list first, hitting the O(n) build requirement perfectly.

内容的提问来源于stack exchange，提问作者BeginningMath