data-structures - LinkedListとバイナリ検索ツリーの違い

Question

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

score 84 · Accepted Answer

リンクリスト：

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)

リンクリストでは、アイテムは1つの次のポインタを介してリンクされます。二分木では、各ノードは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
------ ------ ------

score 16 · Accepted Answer

二分探索木は二分木であり、各内部ノードxは、xの左側の部分木に格納された要素がx以下であり、 xの右側の部分木に格納された要素がx以上であるような要素を格納します。 ×。

現在、Linked Listはノードのシーケンスで構成されており、各ノードには任意の値と、次および/または前のノードを指す 1 つまたは 2 つの参照が含まれています。

score 13 · Accepted Answer

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

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

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

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

score 9 · Accepted Answer

主な違いは、二分探索木がソートされていることです。バイナリ検索ツリーに挿入すると、これらの要素が最終的にメモリに格納されるのは、それらの値の関数です。リンクリストを使用すると、要素の値に関係なく、要素がやみくもにリストに追加されます。

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

score 7 · Accepted Answer

リンクされたリストは、互いにリンクされた一連の「ノード」です。つまり、次のようになります。

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) です。

score 6 · Accepted Answer

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

一方、二分探索木は、より高度な抽象化のデータ構造であり（つまり、これが内部でどのように実装されるかは指定されていません）、効率的な検索を可能にします（つまり、特定の要素を見つけるために、まったく調べる必要はありません）。要素。

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

score 6 · Accepted Answer

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

二分探索木は、双方向リンクリストと同様に、構造内の他の 2 つの要素を指します。ただし、要素をリストの最後に追加するのではなく、構造に要素を追加すると、「左」ノードにリンクされた要素が現在のノードよりも少なくなり、「右」ノードにリンクされた要素が少なくなるように、二分木が再編成されます。ノードは現在のノードより大きいです。

簡単な実装では、新しい要素が構造の最初の要素 (ツリーのルート) と比較されます。小さい場合は「左」の分岐が使用され、そうでない場合は「右」の分岐が調べられます。これは、ブランチが空であることが判明するまで、各ノードで続行されます。新しい要素がその位置を埋めます。

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

score 4 · Accepted Answer

実はとても簡単です。リンクリストは、特定の順序ではなく、一緒にチェーンされたアイテムの集まりです。あなたはそれを決して枝分かれしない本当に細い木と考えることができます：

1 -> 2 -> 5 -> 3 -> 9 -> 12 -> |i. （最後は、nullを終了するためのアスキーアートの試みです）

二分探索木は2つの点で異なります。二分部分は各ノードに1つではなく2つの子があることを意味し、検索部分はそれらの子が検索を高速化するように配置されていることを意味します-左側の小さなアイテムと大きなアイテムのみ右の方へ：

9には子が残っておらず、1、2、および12は「葉」です。これらには枝がありません。

わかる？

ほとんどの「ルックアップ」の種類の用途では、BSTの方が優れています。ただし、「後入れ先出しまたは後入れ先出し」の種類のもののリストを保持するだけの場合は、リンクリストが適切に機能する可能性があります。

score 3 · Accepted Answer

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

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

score 3 · Accepted Answer

リンクされたリストの問題は、その中を検索することです（取得または挿入のいずれか）。

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

二分木は、本質的にソートされてナビゲート可能であるため、より迅速な検索と挿入が可能になります。

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

score 2 · Accepted Answer

Linked List は、A->B->C のように、隣接するノードが互いに接続された直線的な線形データです。あなたはそれをまっすぐなフェンスと見なすことができます。

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

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

score 1 · Accepted Answer

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

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

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

ウィキペディアのリンクリスト、およびウィキペディアのバイナリ検索ツリー。

score 1 · Accepted Answer

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

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

二分探索木はまったく別のものです。ルートノードがあり、ルートノードには最大 2 つの子ノードがあり、各子ノードには最大 2 つの子ノートなどがあります。かなり巧妙なデータ構造ですが、ここで説明するのはやや面倒です。ウィキペディアの記事をチェックしてください。

data-structures - LinkedListとバイナリ検索ツリーの違い

13 に答える 13

Related

Reference