使用以下内容扩展树数据结构：

• 让你的树成为“线程”，也就是说，给每个节点添加一个父引用。
• 维护对具有最大值的节点（“最右边”节点）的引用。在添加/删除节点时保持它最新。

有了这些信息，你就可以避免从根到最右边节点的第一次下降，并立即开始收集值。如果二叉树是平衡的，那么最右边的节点将位于（或接近）树的底层。然后，以反向inorder顺序沿着树遍历--以找到𝑘最大值的节点--将使你遍历O（）的边数𝑘。
替代结构，如B+树和跳跃列表，也可以提供𝑘对𝑘它们存储的最大值的O（）访问。