当树可能被频繁修改时，如何找到 BST 中的第 k 个最小元素？

Question

我正在解决问题LeetCode 230：BST 中的第 K 个最小元素。我的Python代码使用递归中序遍历，虽然与这个问题没有直接关系，但下面给出供参考。在最坏的情况下，如果我们最终访问所有节点 (

O(n)

)，则需要线性时间 (

k = n

)。

def kth_smallest(root: Optional[TreeNode], k: int) -> int:
    def dfs(node: TreeNode, count: int) -> tuple[int, int]:
        """
        :param node: Current node
        :param count: Number of nodes visited so far
        :returns: a 2-tuple consisting of the number of nodes visited, and the value of the last visited node.
            If the kth node is found, immediately returns the value of the kth node
        """
        if node.left is not None:
            # count is the number of nodes in the left subtree.
            count, val = dfs(node.left, count)
            if count == k:
                return k, val
        # count the current node.
        count += 1
        if count == k or node.right is None:
            return count, node.val
        return dfs(node.right, count)

    assert root is not None
    return dfs(root, 0)[1]

有一个后续问题：

如果BST经常被修改（即我们可以进行插入和删除操作），并且需要频繁地找到第k小值，你会如何优化？

我在想B+树。查找/插入/删除操作在

O(log n)

时间内运行。范围内出现

k

元素的范围查询需要

O(k + log n)

时间。

但是我们能比

O(n)

更快地找到 B+ 树中的第 k 个最小元素吗？请注意，我在这里提到 B+ 树是参考我的评论“我正在考虑 B+ 树”。另一种符合问题描述但问题中未提及的数据结构也可以正常工作。

Answer 1

AVL树/红黑树，每个节点存储子树的大小，为所有操作提供

O(log n)

。 这会将树变成订单统计树。

https://en.m.wikipedia.org/wiki/Order_statistic_tree

https://www.baeldung.com/cs/red-black-tree-vs-avl-tree