LinkedList と二分探索ツリーの違い

StackOverflow https://stackoverflow.com/questions/270080

質問

リンク リストと BinarySearchTree の主な違いは何ですか?BST は LinkedList を維持するための単なる手段ですか?私のインストラクターは LinkedList と BST について話しましたが、それらを比較したり、いつどちらを優先するかについては述べませんでした。おそらく愚かな質問かもしれませんが、私は本当に混乱しています。誰かがこれを簡単な方法で明確にしてくれれば幸いです。

役に立ちましたか？

解決

リンクリスト：

Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7)

バイナリツリー：

                 Node(1)
                /
            Node(2)
           /    \
          /      Node(3)
  RootNode(4)
          \      Node(5)
           \    /
            Node(6)
                \
                 Node(7)

リンクリストでは、アイテムは単一の次のポインターを介してリンクされます。 バイナリツリーでは、各ノードに0、1、または2つのサブノードを設定できます。バイナリ検索ツリーの場合、左ノードのキーはノードのキーよりも小さく、右ノードのキーはノード。ツリーのバランスが取れている限り、各アイテムへの検索パスはリンクリストの検索パスよりもはるかに短くなります。

検索パス：

------ ------ ------
key    List   Tree
------ ------ ------
1      1      3
2      2      2
3      3      3
4      4      1
5      5      3
6      6      2
7      7      3
------ ------ ------
avg    4      2.43
------ ------ ------

構造が大きくなると、平均検索パスは著しく小さくなります：

------ ------ ------
items  List   Tree
------ ------ ------
     1      1   1
     3      2   1.67
     7      4   2.43
    15      8   3.29
    31     16   4.16
    63     32   5.09
------ ------ ------

他のヒント

A Binary Search Tree は、各内部ノード x が要素を格納するバイナリツリーで、 x は x 以下であり、 x の右サブツリーに格納されている要素は x 以上です。

alt text

リンクリストは一連のノードで構成され、各ノードには任意の値と、次または前のノードを指す1つまたは2つの参照が含まれます。

コンピューターサイエンスでは、バイナリ検索ツリー（BST）はバイナリツリーデータ構造です。次のプロパティがあります。

  • 各ノード（ツリー内のアイテム）には異なる値があります;
  • 左右のサブツリーは両方とも二分探索木でなければなりません;
  • ノードの左のサブツリーには、ノードの値より小さい値のみが含まれます。
  • ノードの右側のサブツリーには、ノードの値以上の値のみが含まれます。

コンピューターサイエンスでは、リンクリストは基本的なデータ構造の1つであり、他のデータ構造を実装するために使用されます。

したがって、バイナリ検索ツリーは、リンクリストまたは配列を使用して実装できる抽象概念です。リンクリストは基本的なデータ構造です。

主な違いは、バイナリ検索ツリーがソートされることです。バイナリ検索ツリーに挿入すると、それらの要素がメモリに格納される場所は、その値の関数です。リンクリストを使用すると、要素は値に関係なくリストに盲目的に追加されます。

すぐにいくつかのトレードオフができます： リンクリストは挿入順序を保持し、挿入は安価です 一般に、バイナリ検索ツリーは検索が高速です

リンクリストは、「ノード」の連番です。互いにリンクされている、すなわち：

public class LinkedListNode
{
     Object Data;
     LinkedListNode NextNode;
}

バイナリ検索ツリーは同様のノード構造を使用しますが、次のノードにリンクする代わりに、2つの子ノードにリンクします。

public class BSTNode
{
    Object Data
    BSTNode LeftNode;
    BSTNode RightNode;
}

新しいノードをBSTに追加する際に特定のルールに従うことにより、非常に高速に移動できるデータ構造を作成できます。ここでの他の回答はこれらのルールを詳しく説明しました。ノードクラス間の違いをコードレベルで表示したかっただけです。

ソートされたデータをBSTに挿入すると、リンクされたリストになり、ツリーを使用する利点が失われることに注意することが重要です。

このため、linkedListはO（N）トラバーサルデータ構造であり、BSTは最悪の場合はO（N）トラバーサルデータ構造であり、最良の場合はO（log N）です。

リンクリストとBSTには、コンテナとして機能する両方のデータ構造であることを除いて、実際にはあまり共通点はありません。 リンクリスト では、基本的にどの場所でも要素を効率的に挿入および削除できますリスト内で、リストの順序を維持しながら。このリストは、1つの要素から次の要素（および多くの場合、前の要素）へのポインターを使用して実装されます。

バイナリ検索ツリー はデータです効率的な検索を可能にする（つまり、特定の要素を見つけるために、すべての要素を見る必要がない） これは内部的に実装されていない）より高い抽象化の構造/ p>

リンクリストは、縮退したバイナリツリー、つまりすべてのノードに子が1つしかないツリーと考えることができることに注意してください。

実際には非常に簡単です。リンクリストは、特定の順序で並べられていない一連のアイテムです。あなたは、それは決して分岐しない本当に細い木と考えることができます：

1-＆gt; 2-＆gt; 5-＆gt; 3-＆gt; 9-＆gt; 12-＆gt; | i。（最後は終端ヌルへのascii-artの試みです）

バイナリ検索ツリーは2つの点で異なります。バイナリ部分は各ノードに1つではなく 2 の子があることを意味し、検索部分はそれらの子が検索を高速化するために配置されることを意味します-のみ左に小さなアイテム、右に大きなアイテムのみ：

    5
   / \
  3   9
 / \   \
1   2   12

9には左の子がなく、1、2、および12は「葉」です。 -ブランチはありません。

理にかなっていますか

ほとんどの＆quot; lookup＆quot;用途の種類は、BSTの方が優れています。ただし、後の先入れ先出しまたは後入れ先出しに対処するために物事のリストを「保持」するだけです。種類、リンクリストはうまくいくかもしれません。

リンクリストの問題は、リスト内での検索です（取得または挿入のいずれか）。

単一リンクリストの場合、先頭から始めて、目的の要素を見つけるために順番に検索する必要があります。リスト全体をスキャンする必要を回避するには、リスト内のノードへの追加の参照が必要です。この場合、単純なリンクリストではなくなります。

バイナリツリーは、本質的にソートされナビゲート可能であるため、より迅速な検索と挿入が可能です。

私が過去に成功して使用した代替手段は、SkipListです。これは、リンクリストに似たものを提供しますが、バイナリツリーに匹敵する検索パフォーマンスを可能にする追加の参照を提供します。

リンクされたリストは、まさに...リストです。それは線形です。各ノードには、次のノードへの参照があります（二重リンクリストの場合は、前のノードにも）。ツリーブランチ---各ノードには、さまざまな子ノードへの参照があります。二分木は、各ノードに2つの子しかない特殊なケースです。したがって、リンクリストでは各ノードに前のノードと次のノードがあり、バイナリツリーではノードに左の子、右の子、親があります。

これらの関係は、構造をトラバースする方法に応じて、双方向または単方向になります。

類似点はありますが、主な違いは、バイナリ検索ツリーが要素または「キー」の効率的な検索をサポートするように設計されていることです。

二重リンクリストのようなバイナリ検索ツリーは、構造内の他の2つの要素を指します。ただし、要素をリストの最後に追加するのではなく、構造に要素を追加する場合、「左」にリンクされている要素がノードは現在のノードよりも小さく、「右」にリンクされている要素ノードは現在のノードより大きい。

単純な実装では、新しい要素は構造の最初の要素（ツリーのルート）と比較されます。少ない場合は、「左」分岐が行われます。それ以外の場合は「右」ブランチが検査されます。これは、ブランチが空であることがわかるまで、各ノードで継続します。新しい要素がその位置を埋めます。

この単純なアプローチでは、要素を順番に追加すると、リンクリストが作成されます（同じパフォーマンス）。ノードを再配置することにより、ツリーのバランスの尺度を維持するためのさまざまなアルゴリズムが存在します。たとえば、AVLツリーは、最適な検索時間を提供して、ツリーのバランスをできるだけ保つために最も多くの作業を行います。赤黒の木は、バランスのとれた木を維持しないため、検索が若干遅くなりますが、キーが挿入または削除されるため、平均して作業が少なくなります。

リンクリストは、隣接ノードが互いに接続された直線の線形データです。 A-＆gt; B-＆gt; C。まっすぐなフェンスと考えることができます。

BSTは、メイントランクがブランチに接続され、それらのブランチが順番に他のブランチなどに接続されているツリーのような階層構造です。 「バイナリ」ここで言う単語は、各ブランチが最大2つのブランチに接続されることを意味します。

リンクリストを使用して、各アイテムが最大1つのアイテムに接続されているストレートデータのみを表します。一方、BSTを使用してアイテムを2つのアイテムに接続できます。 BSTを使用して家系図などのデータを表すことができますが、それは各人に3人以上の子供がいる可能性があるため、n項検索ツリーになります。

二分探索ツリーはどのような方法でも実装でき、リンク リストを使用する必要はありません。

リンク リストは、ノードと、ノード内の他のノードへのポインタ/参照を含む単純な構造です。リストのヘッド ノードを指定すると、リンクされたリスト内の他のノードを参照できます。二重リンクリストには 2 つのポインター/参照があります。通常は次のノードへの参照ですが、前のノードへの参照もあります。二重リンクリストの最後のノードがリストの最初のノードを次のノードとして参照し、最初のノードが最後のノードを前のノードとして参照する場合、それは循環リストであると言われます。

二分探索ツリーは、二分探索比較アルゴリズムに基づいて、入力をほぼ等しい 2 つの半分に分割するツリーです。したがって、要素を見つけるために必要な検索はほんの数回だけです。たとえば、1 ～ 10 のツリーがあり、3 つを検索する必要がある場合、最初に一番上の要素 (おそらく 5 または 6) がチェックされます。3 はそれより少ないため、ツリーの前半のみがチェックされます。次の値が 3 の場合は、その値が存在します。それ以外の場合は、値が見つからないかデータが返されるまで、比較が行われます。したがって、ツリーの検索は高速ですが、挿入や削除は必ずしも高速ではありません。これらは非常に大まかな説明です。

リンクされたリスト ウィキペディアより、そして 二分探索木, 、これもwikipediaより。

これらはまったく異なるデータ構造です。

リンクリストは、各要素が次の要素にリンクされている要素のシーケンスであり、二重リンクリストの場合は前の要素にリンクされています。

バイナリ検索ツリーはまったく異なるものです。これにはルートノードがあり、ルートノードには最大2つの子ノードがあり、各子ノードには最大2つの子ノートなどがあります。これは非常に巧妙なデータ構造ですが、ここで説明するのは少し面倒です。 ウィキペディアの記事をご覧ください。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top