3

与えられたバランスの取れた二分木に対して、以下のようにノードペアを (ツリーをトラバースしながら) 出力するインプレース O(N) アルゴリズムを探します。

                 a

              b     c

             d e   f g

出力: bc、de、ef、fg

ここで、'a' はルート ノード、'b' は左の子、'c' は右の子などです。出力のペア 'ef' に注意してください。

以下のコメントに基づく追加情報:

  1. 「ノード ペア」は、各レベルの各隣接ペアです。
  2. 各ノードは、「左」と「右」に加えて「親」ポインタ/参照を持つことができます
  3. O(N) とインプレースを緩和する場合、もっと単純な解決策 (再帰的および反復的) はありますか?
4

2 に答える 2

3

このツリーが配列に格納されている場合、「レベル連続」になるように再配置できます (最初の要素がルート、次の 2 つがその子、次の 4 つがその子など)。問題は簡単です。

それ以外の方法で保管すると問題が発生します。幅優先トラバーサルを試すこともできますが、O(n) メモリを消費する可能性があります。

現在のレベルと現在の要素へのパス (2 進数で表される) を格納し、最後にアクセスした要素のみを格納してペアを作成できるようにすることで、O(n log n) 時間アルゴリズムを作成できると思います。O(1 + log n) メモリのみ。-> これは、実際にはバックトラッキングを使用した O(n) アルゴリズムである可能性があります (以下を参照)。

O(n) ですべてのノードを順番に訪問する簡単なアルゴリズムがあることを知っているので、「姉妹」ノードを O(n) 時間で順番に訪問するトリックがあるかもしれません。O(n log n) 時間は保証されていますが、特定のレベルで停止することができます。

自明な O(n log n) アルゴリズムもあります。指定されたレベルのノードをフィルタリングし、次のループのレベルを上げるだけです。

編集：

さて、O(1) メモリ (現在および最大レベルを追跡するための 2 つのマシン ワード サイズの変数 / 技術的には O(log log n) メモリ) を使用して O(n) で実行されるソリューションを作成しました。それ/およびいくつかのノード)、ただし、すべてのノードに親へのポインターが含まれている必要があります。この特別な構造を使用すると、O(n log n) スタックなしで、2 つのノードのみを使用して、左、上、右のいずれかのステップに進むことができます。特定の最大レベルで停止し、それを下回ることはありません。実際のレベルと最大レベル、および最大レベルで最後に遭遇したノードを追跡します。最大レベルで次のペアに遭遇した場合、明らかにそのようなペアを印刷できます。そのレベルにこれ以上ないことに気付くたびに、最大レベルを上げます。

n-1 ノード バイナリ ツリーのルート ノードから開始すると、これは 1 + 3 + 7 + 15 + ... + n - 1 回の操作になります。これは 2 + 4 + 8 + 16 + ... + n - log2n = 2n - log2n = O(n) 操作です。

特別なメンバーがなければNode* parent、このアルゴリズムは O(log n) メモリでのみ可能です。これは、順序通りのトラバーサルに必要なスタックのためです。

于 2011-08-10T00:00:08.093 に答える
2

ツリーとして次の構造があると仮定します。

struct Node
{
    Node *left;
    Node *right;
    int value;
};

ツリーをその場で変更する 3 つのパスですべてのペアを印刷できます。rightアイデアは、同じ深さでノードをポインターと一緒にリンクすることです。leftポインターに従って下にトラバースします。また、各深さのリストを null で終了しないため、深さごとに予想されるノードの数も維持します。次に、解凍​​してツリーを元の構成に復元します。

これの美しさはzip_down機能です。左のサブツリーの右の分岐が右のサブツリーの左の分岐を指すように、2 つのサブツリーをまとめて「圧縮」します。すべてのサブツリーに対してこれを行うと、rightポインターをたどることで各深さを反復できます。

struct Node
{
    Node *left;
    Node *right;
    int value;
};

void zip_down(Node *left, Node *right)
{
    if (left && right)
    {
        zip_down(left->right, right->left);
        left->right= right;
    }
}

void zip(Node *left, Node *right)
{
    if (left && right)
    {
        zip(left->left, left->right);
        zip_down(left, right);
        zip(right->left, right->right);
    }
}

void print_pairs(const Node * const node, int depth)
{
    int count= 1 << depth;

    for (const Node *node_iter= node; count > 1; node_iter= node_iter->right, --count)
    {
        printf("(%c, %c) ", node_iter->value, node_iter->right->value);
    }

    if (node->left)
    {
        print_pairs(node->left, depth + 1);
    }
}

void generate_tree(int depth, Node *node, char *next)
{
    if (depth>0)
    {
        (node->left= new Node)->value= (*next)++;
        (node->right= new Node)->value= (*next)++;

        generate_tree(depth - 1, node->left, next);
        generate_tree(depth - 1, node->right, next);
    }
    else
    {
        node->left= NULL;
        node->right= NULL;
    }
}

void print_tree(const Node * const node)
{
    if (node)
    {
        printf("%c", node->value);
        print_tree(node->left);
        print_tree(node->right);
    }
}

void unzip(Node * const node)
{
    if (node->left && node->right)
    {
        node->right= node->left->right;
        assert(node->right->value - node->left->value == 1);
        unzip(node->left);
        unzip(node->right);
    }
    else
    {
        assert(node->left==NULL);
        node->right= NULL;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    char value_generator= 'a';
    Node root;

    root.value= value_generator++;
    generate_tree(2, &root, &value_generator);
    print_tree(&root);
    printf("\n");

    zip(root.left, root.right);
    print_pairs(&root, 0);
    printf("\n");

    unzip(&root);
    print_tree(&root);
    printf("\n");

    return 0;
}

EDIT4: インプレース、O(n) 時間、O(log n) スタック スペース。

于 2011-08-10T00:16:59.783 に答える