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ています。

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 に答える