1

在顺序统计树中，节点的等级是多少？

它是由

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树的 inorder tree walk 中的位置。

4

2 回答 2

6

顺序统计树中的每个节点仅存储其左子树（以及，可选地，其右子树）中的节点数。如果你只是读取这个值，你不一定知道节点的排名，因为你不知道该节点在顺序统计树中的位置。例如，如果您的节点位于根节点的右子树中，则需要将根节点左侧的所有节点都考虑在内。

如果您有一个节点并且想知道它的排名，您可以使用修改后的 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)

希望这可以帮助！

于 2013-07-17T19:15:09.670 回答
0

代码中的所有内容都是正确的，但是您必须在每次迭代后再添加一个命令来更新指针“y”的值。y = y。p;

正确的算法将是

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 
    } 
y = y. p;
} 
return r 
}
于 2017-12-14T13:57:34.697 回答