java - 插入和搜索二叉搜索树

Question

我的 BST 有问题。我应该构建的 BST 有一个隐式的“等级”，节点在其中排序。例如，当插入一个新的节点时，我得到了一个存储在节点中的值以及插入它的等级。换句话说，BST 应该存储一个序列。我的插入函数似乎可以工作，但偶尔会出现小错误，选择函数在不应该抛出 NullPointerException 时抛出。

Node.java

RBST.java

RBSTTest.java

public void insertNormal(int team, int rank)
{
    root = insertNormal(root, team, rank);
}

 /**
 * Insert the data team at position rank into node T. This is the normal
 * insert routine without any balancing.
 */
private Node insertNormal(Node T, int team, int rank)
{
    assert (rank >= 1 && rank <= T.getSize() + 1) : "rank should be between 1 and size of the tree <"
        + (T.getSize() + 1) + ">";

    if (T == null)
    {
        return new Node(team);
    }

    if (getRank(T) >= rank)
    {
        T.setLeft(insertNormal(T.getLeft(), team, rank));
    }
    else
    {
        T.setRight(insertNormal(T.getRight(), team, rank));
    }
    T.incSize();

    return T;
}


public Node select(int rank)
{
    return select(root, rank);
}

/**
 * The select method that returns the node in the tree at position rank.
 */
private Node select(Node T, int rank)
{
    if (T == null || getRank(T) == rank)
        return T;

    assert (rank >= 1 && rank <= T.getSize()) : "rank should be between 1 and size of the tree <" + T.getSize()
        + "> ";

    if (getRank(T) > rank)
        T = T.getLeft();
    else
        T = T.getRight();

    return select(T, rank);
}

public int getRank(Node T)
{
    return (T.getLeft() == null ? 1 : T.getLeft().getSize() + 1);
}

Answer 1

二叉搜索树的构造有点奇怪。显然你事先知道球队的排名。在这种情况下，您通常会将团队排名存储在 Node 中。然后您可以稍后轻松检索排名。这样，您也不会被迫按照队伍的顺序添加队伍。

您当前的 getRank() 方法目前并不实际检索排名。请注意，如果您现在按排名顺序添加团队，您将得到一个非常低的树，其子树始终位于右侧，而左侧始终为 null。这也可能是您的错误来源:getRank() 将始终返回 1。