0

優れたRichard Bucklandの講義をいくつか見たり、バイナリ ツリーを試したりしましたが、実装方法が完全にはわかりません。以下は私がどこまで行ったかです。 

class Tree(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

t = Tree(4, Tree(2, Tree(1), Tree(3)), Tree(6, Tree(5), Tree(7)))

バイナリ ツリーを使用して解決できる簡単な問題の例を教えてください。ツリーを作成するために提示されるデータや、実際にどのように使用できるかがよくわかりません。他の誰かのソースコードが欲しくないので、いくつかの例をグーグルで検索するのが怖い. 私は自分で実装を解決したいと考えています。しかし、これを行う前に、解決すべき問題が必要だと感じています。理想的には、かなり些細な例の問題を 2 つ、次にいくつかの中間的な問題を示したいと思います。

4

2 に答える 2

1

上記のコードは、バイナリ ツリーの「有効な」実装です...既に完成しています。ノード ( Trees と呼びます) があり、各ノードは 0、1、または 2 つの子を持つことができます。編集実際、実装を使用して空のツリーを実装できないことに気付きましたが、それはちょっとした問題です。

これはセマンティックなことですが、「ある種重要」です。二分木自体は、実際には問題にはまったく使用されません。標準のバイナリ ツリーはあまり役に立ちません。各ノードが最大 2 つの子を持つツリーにすぎません。このリンクは、私が言っていることを明確にする必要があります (おそらく、あなたの質問に対する十分な回答が含まれています): https://stackoverflow.com/a/2159506。

あなたが実際に興味を持っているのは、追加のプロパティを持つ「バランスのとれた二分探索木」だと思います。特に、左から右に「順序付け」されています (これは漠然とした説明ですが、実際には「左の子は親とその兄弟よりも小さい」と言いたいわけではありません)。一部の実装では等しい)。また、深さが制限されています（オブジェクトを含む高さO(log(n))の木はありません...これは単なるリンクリストです）。nn

とにかく、あなたの質問に答えるには: ちょっと退屈ですが、一般的な提案は、ヒープや辞書などの抽象的なデータ構造を実装することです。用語に注意してください。ヒープは二分探索木を使用して実装できます。定義上、ヒープはどの実装にも関連付けられていません。特定の操作を実行できることのみが必要です (例:peek(), min(), add()など)。バイナリ ツリーのようなプリミティブ データ構造を選択することは、ヒープを生成するために必要です (そうでなければ、頭の中に浮かんでいるこの抽象的なものにすぎません)。バランスの取れた二分探索木を選択すると、これらの操作に時間の複雑さも与えられます (たとえば、バランスの取れた二分探索木で実装されたヒープにはO(log(n)) peek(). 詳細については、wiki リンクを参照してください。http://en.wikipedia.org/wiki/Heap_(data_structure)#Comparison_of_theoretic_bounds_for_variants )。

ヒープを作成したら、アルゴリズムがヒープを使用している問題を調べることができます...たくさんあります。k線形時間で th 番目に大きい要素を見つけたいとします。ヒープ (ただし、これを証明するには少し注意が必要です)。プリムのアルゴリズムを実装したい場合はどうしますか? ヒープ。最悪のケースで任意のオブジェクトをソートしたい場合はどうしますO(n log(n))か? ヒープソート (実際には高速ではないため、通常はヒープソートを使用しないことに注意してください)。

于 2013-05-12T11:56:09.380 に答える
0

さて、これを試してみてください：http://www.spoj.com/problems/TREE/

またはこれ: http://www.spoj.com/problems/THREECOL/

http://www.spoj.com/problems/NWERC11B/

これらの問題は些細なことではなく、時間がかかりますが、ここから確実に学ぶことができます。

基本的に、何らかの方法でバイナリ ツリーを本質的に必要とする膨大な数の問題があります。たとえば、命題論理で推論アルゴリズムを構築します。

はい、Sedgewick のアルゴリズムを理解できれば、たとえば、非常に役立つ二分探索木に関する章があります。

于 2013-05-12T10:26:50.100 に答える