0

ソートされたツリーとは何か、バイナリ ツリーと avl および and and ... を理解しようとしましたが、ソートされたツリーがソートされる理由はまだわかりません。また、ソートされたツリーでの検索とソートされていないツリーでの検索の複雑さ (Big-Oh) は何ですか? あなたが私を助けてくれることを願っています。

4

5 に答える 5

5

二分木

二分木には、バランス型とアンバランス型の 2 つの主なタイプがあります。バランスの取れたツリーは、ツリーの高さ (高さ = ルートと最も遠い子の間のノードの量) をできるだけ均一に保つことを目的としています。バランス ツリーにはいくつかのタイプのアルゴリズムがあり、最も有名なのは AVL ツリーと RedBlack ツリーの 2 つです。AVL ツリーと RedBlack ツリーの両方での挿入/削除/検索操作の複雑さは、O(log n)またはそれ以上です。これは重要な部分です。他の自己均衡化アルゴリズムは、AA-、Splay-、および Scapegoat-tree です。

バランスのとれたツリーは、ツリーに対するすべての削除または挿入操作の後、アルゴリズムがツリーを内省してバランスが取れていることを確認し、そうでない場合はこれを修正しようとするという事実から、バランスが取れているというプロパティ (および名前) を取得します (これは行われます)。アルゴリズムごとに異なります) ツリー内でノードを回転させます。

通常の (または不均衡な) 二分木は、その構造を変更してバランスを保つことはなく、ほとんどの場合、時間の経過とともに非常に非効率になるリスクがあります (特に値が順番に挿入されている場合)。ただし、パフォーマンスに問題がなく、主にソートされたデータ構造が必要な場合は、そうする可能性があります。アンバランス ツリーでの挿入/削除/検索操作の複雑さは、O(1) (ルートが必要な場合の最良のケース) から O(n) (すべてのノードを順番に挿入し、最大のノードが必要な場合の最悪のケース) の範囲です。 )

ある種のランダム化を使用して、ツリーが完全に不均衡にならないようにする、ランダム化されたバイナリ ツリーと呼ばれる別のバリ​​エーションが存在します (リンク リストと同じです)。

于 2009-05-31T09:53:00.627 に答える
2

二分探索木は、すべてのノードが 2 つの子ノードを持つ「ツリー」構造です。
左側のノードはすべてその親よりも小さいというプロパティを持ち、右側のノードはすべてその親よりも大きいです。

二分木で興味深いのは、木が適切にソートされている場合、O(log n) の値を検索できることです。たとえば、LinkedList で同じ検索を行うと、O(n) の検索速度が得られます。

データ構造を学習するための最良の方法は、グーグルで一日かけてウィキペディアの記事を読むことです。
これで始められるかもしれません
http://en.wikipedia.org/wiki/Binary_search_tree

于 2009-05-31T09:37:56.400 に答える
1

次のように Google 検索を実行します。

site:stackoverflow.com binary trees

あなたのいくつかの質問に答えるSOの質問のリストを取得します。

于 2009-05-31T09:33:55.393 に答える
0

何らかの方法でソートされていない場合、ツリー構造を使用してもあまり意味がありません。ツリー内のノードを検索する予定で、ソートされていない場合は、ツリー全体をトラバースする必要があります (の上））。何らかの方法でソートされたツリーがある場合、ツリーの単一のブランチ (通常は O(log n)) をたどるだけで済みます。

于 2009-05-31T09:36:40.287 に答える
0

二分木では、右の葉は常に頭よりも小さく、左の葉は常に大きいため、O(log(n)) でソートされた木を検索できます。キーがより小さい場合は、右に行く必要があります。 bggerの場合は頭と左に

于 2009-05-31T09:37:02.500 に答える