二分木と二項探索木の違い

データ構造とは、データを有効に活用するための体系的な整理方法である。データ構造を使ってデータを整理することで、ランタイムや実行時間を短縮することができます。また、データ構造には最小限のメモリしか必要ありません。データをツリー構造で並べることもある。木は、ノードとエッジで結ばれています。一番上のノードがルートです。各ノードは最大2ノードまで持つことができます。これらは子ノードと呼ばれる。親ノードの左側にあるノードが左子ノード、親ノードの右側にあるノードが右子ノードとなります。木構造には、2分木と2分探索木がある。二分木は、各親ノードが最大2つの子ノードを持つことができるデータ構造の一種である。バイナリサーチ...

主な違い - 2分木と2分探索木

カタログ

1. 概要と主な相違点 2. 二分木とは 3. 二分探索木とは 4. 二分木と二分探索木の類似点 5. 並列比較-表形式での二分木と二分探索木 6. まとめ

二分木は何ですか？

データをツリー構造で並べる場合、ツリーの一番上にあるノードをルートノードと呼びます。ルートはツリー全体に対して1つしか存在できない。ルートノード以外のノードは、上向きのエッジを持つ。親ノードと呼ばれる。親コードの下にあるノードを子コードと呼びます。各親ノードは最大2つの子ノードを持つことができます。これらは、左子ノード、右子ノードと呼ばれる。子ノードを持たないノードをリーフノードと呼びます。バイナリーツリーのデータの並べ方は特に決まっていない。ルートノードから各ノードへのパスが存在する。

二叉树(binary tree)和二叉搜索树(binary search tree)的区别

図01：二分木の例

上記は2分木の例である。ツリーの一番上にある要素2がルートです。各ノードは最大で2つのノードを持つ。木がサイクルを含んでいたり、ノードが2つ以上のノードを含んでいたりすると、二分木として分類されない。あるノードから別のノードへの経路は必ず存在する。ルートノード2の子は7と5であり、ノードを持たないこともある。しかし、どのノードも2つ以上のノードを持つことはできない。ルートの右の要素は5であり、要素5は子ノード9の親である。ノード4とノード11には子要素がない。したがって、それらはリーフノードである。

バイナリツリーは、データを階層的に格納するために使用されます。コンピュータのファイル構造に似ている。配列のようなデータ構造は、特定の量のデータを格納することができます。しかし、2分木ではノード数に上限がない。

二項探索木は何ですか？

バイナリサーチツリーは、バイナリツリーのデータ構造である。二分木と同様に、二分探索木は2つのノードを持つことができます。ルートノード以外のノードは、上向きのエッジを持つ。親ノードと呼ばれる。そのエッジによって下方に接続されたノードを子ノードと呼ぶ。子ノードを持たないノードをリーフノードと呼ぶ。各親ノードは最大で2つのノードを持つことができます。左の子ノードと右の子ノードを参照する子ノードが存在する。最上位の要素をルートノードと呼びます。左の子ノードには、親ノード以下の値を持つノードのみが含まれる。右の子ノードには、値が親ノード以上であるノードのみが含まれる。

図02：二分探索木の例

要素8は最上位の要素です。したがって、ルートノードである。3を親ノードとすると、1と6は子ノードであり、1が左の子ノード、6が右の子ノードである。左の子ノードには、親ノードと同等かそれ以下の値が含まれる。3が親ノードの場合、左辺に3以下の要素があるはずです。この例では1です。右の子ノードには、親ノードよりも大きな値を持つノードだけが含まれます。3が親ノードの場合、右の子ノードは3より大きな値を持つはずである。この例では6である。ここでも、各データ要素を二項探索木に配置する順番が決まっているのである。データのソート、検索、探索を効率的に行うためのデータ構造である。

二分木と二項探索木の共通点

二分木と二分探索木はともに階層的なデータ構造である。
二分木と二分探索木はどちらも根を持つ。
二分木と二分探索木は、最大2つの子ノードを持つことができます。