是否有平衡的BST,每个节点保持子树大小?

有没有 balanced BST 还跟踪每个节点中子树大小的结构?

在里面 Java , TreeMap 是一棵红黑树,但不提供每个节点的子树大小。

之前,我确实编写了一些BST,可以跟踪每个节点的子树大小,但它并不平衡。

问题是:

• 有没有可能实现这样一个树,同时保持 ( O(lg(n)) (用于基本操作) ?
• 如果是,那么是否有任何第三方库提供这样的impl?
  A. JAVA impl很棒,但是其他语言 (例如 c , go ) 也会有帮助。

顺便说一句:

• 子树大小应在每个节点中保持跟踪。
  这样就可以在不遍历子树的情况下得到大小。

可能的应用:

• 记录物品的等级,它们的价值 (排名取决于) 可能会随时改变。