1

配列をソートする必要があります。すでに存在する種類の並べ替えとは別に、このようなアルゴリズムが機能するかどうか、およびその複雑さはどの程度かを知りたいと思っていました。

ソートする配列があります。二分探索木を作成します。

したがって、配列のすべての要素を BST に挿入し、ツリーを順番にトラバーサルするときにそれらを 1 つずつ配列に割り当てると、ソートされた結果が得られます。(ただし、ツリー ノードのため、より多くのスペースの複雑さを消費します。インプレース ソートではありません。)

int i=0;

void sort_by_inorder(node *n)
{
    if(n==NULL)
    {
        return;
    }
    sort_by_inorder(n->leftchild);
    array[i++]=n->data;
    sort_by_inorder(n->rightchild);
}

BST では重複した挿入が許可されないことはわかっているので、BST 挿入アルゴリズムを <= に変更して左のサブツリーを、または >= を右のサブツリーに変更することを検討できます。

これは良い実装になりますか (実行可能)? 複雑さは何ですか？

走査の複雑さは平均的O(n)です。そして挿入はただO(log n)です。したがって、私によると、これは効率的なアルゴリズムであることが判明するはずです。

ありがとう。

4

1 に答える 1

0

一般的な二分探索木では、実際の挿入時間は最悪でも O(n) です。操作がO（log（n））になるようにするには、バランスの取れたツリーが必要です。

したがって、一般的なBSTでは、アプローチによりO（n ^ 2）でソートできます。

于 2012-07-13T13:10:28.847 に答える