c++ - 二分探索木での品質の抽出

Question

二分探索木の要素より少ないすべての要素の数を見つけるための効率的な方法はありますか？C ++でプロシージャまたは実装を見つけようとしましたが、見つかりませんでした。だからあなたが持っていたと言う：

      8
    /   \
   3     10
  / \      \
 1   6      14

10未満のノード数を見つけたい場合は、4を取得できます。

Answer 1

特定のノードの下にあるノードの数が（一定時間内に）わかっている場合は、次のようにするだけです。

int BinarySearchTree::countLessThan(const Node *n, const T &value) const {
    if (n->value >= value) {
        // The value has to be in the left sub-tree, so continue searching there:
        if (n->left)
            return countLessThan(n->left, value);
        else
            return 0;
    } else {
        // The value has to be in the right sub-tree, so continue searching there
        // but include the whole left sub-tree and myself:
        int count = 1;
        if (n->left)
            count += n->left->count();
        if (n->right)
            count += countLessThan(n->right, value);
        return count;
    }
}

ルートノードでアルゴリズムを開始します。

int BinarySearchTree::countLessThan(const T &value) const {
    countLessThan(root, value);
}

ライブの例はここで見ることができます：http：//ideone.com/JcpjeK

これは次のツリーで実行されます（14と10を入れ替えたので、10は14の左の子になることができます。これは、私の迅速でダーティなBST実装では、左の子が既に存在する場合にのみ右の子が許可されるためです）。

      8
    /   \
  3       14
 / \     /
1   6   10

Answer 2

あなたはこのようなことをすることができます：

int res = countLessThan(root, value, 0); // res is your answer

次に、これを実装します。

int BTree::countLessThan(node *currNode, int value, int count)
{            
        if(currNode->left != NULL)
                count = countLessThan(currNode->left, value, count);

        if(currNode->value >= value)
                return count;
        count++;

        if(currNode->right != NULL)
                count = countLessThan(currNode->right, value, count);

       return count;

}

Answer 3

1. std::mapまたはstd::setをBSTとして使用している場合は、std::map::lower_boundメンバー関数を以下と組み合わせて使用​​できstd::distanceます。

   auto count = std::distance(bst.begin(), bst.lower_bound(target));
   

2. それ以外の場合は、関数を使用できますが、コンテナーがランダムアクセスイテレーターを実装していることを前提としているため、std::lower_boundフラットコンテナー（）でのみ最適になります。std::vector

   auto count = std::distance(
       bst.begin(), std::lower_bound(bst.begin(), bst.end(), target));