订单统计树中节点的等级

Question

在订单统计树中,节点的等级是多少？

是由它给出的

rank = x.left.size + 1

还是通过这个功能？

OS-RANK(T, x)
{
    r = left.size + 1
    y = x

    while (y != T.root)
    {
        if (y == y.p.right) {
            r = r + y.p.left.size + 1
        }
    }

    return r
}

我真的很困惑,因为我认为它应该是简单的x.left.size + 1,因为那应该是x树的顺序树行走的位置.

Answer 1

订单统计树中的每个节点只存储其左子树(以及可选地,在其右子树中)的节点数.如果您只是读取此值,则不一定知道节点的等级,因为您不知道节点所在的顺序统计树中的位置.例如,如果您的节点位于根节点的右子树中,则需要将根目录左侧的所有节点计入排名.

如果您有一个节点并想知道它的排名,您可以使用修改后的BST查找来计算它.在伪代码中:

function rank(node root, node n):
    /* If n is the root of the tree, its rank is the number of nodes in its
     * left subtree.
     */
    if root.value == n.value:
        return n.leftSize

    /* Belongs in right subtree: */
    else if root.value < n.value:
        return rank(root.left, n)

    /* Belongs in left subtree: */
    else:
        return root.leftSize + 1 + rank(root.right, n)

希望这可以帮助!