ツリーのデータ構造について知る必要があるすべて

木はとても美しいです。若い頃に描いた絵。

コーディングを初めて習うとき、「主なデータ構造」として配列を学ぶのが一般的です。

最終的には、ハッシュテーブルについても学習します。コンピューターサイエンスの学位を取得する場合は、データ構造に関するクラスを受講する必要があります。また、リンクリスト、キュー、およびスタックについても学習します。これらのデータ構造は、すべて論理的な開始と論理的な終了があるため、「線形」データ構造と呼ばれます。

木やグラフについて学び始めると、本当に混乱する可能性があります。データを直線的に保存するわけではありません。両方のデータ構造は、特定の方法でデータを保存します。

この投稿は、ツリーデータ構造の理解を深め、それについての混乱を明確にするためのものです。

この記事では、次のことを学びます。

  • 木とは
  • 木の例
  • その用語と仕組み
  • コードでツリー構造を実装する方法。

この学習の旅を始めましょう。 :)

定義

プログラミングを開始するとき、ツリーやグラフなどのデータ構造よりも線形データ構造をよく理解するのが一般的です。

ツリーは、非線形データ構造としてよく知られています。データを直線的に保存することはありません。データを階層的に編成します。

実生活の例に飛び込もう!

階層的に言うとはどういう意味ですか?

祖父母、親、子供、兄弟など、すべての世代の関係を持つ家系図を想像してください。私たちは一般的に家系図を階層的に整理します。

私の家系

上記の図は私の家系図です。トシコ、秋和、ひとみ、竹見は私の祖父母です。

俊明とジュリアナは私の両親です。

TK、Yuji、Bruno、Kaioは私の両親(私と私の兄弟)の子供です。

組織の構造は、階層の別の例です。

会社の構造は階層の例です

HTMLでは、ドキュメントオブジェクトモデル(DOM)はツリーとして機能します。

ドキュメントオブジェクトモデル(DOM)

HTMLタグには他のタグが含まれています。 headタグとbodyタグがあります。これらのタグには特定の要素が含まれています。 headタグには、metaタグとtitleタグがあります。 bodyタグには、h1、a、liなどのユーザーインターフェイスに表示される要素があります。

技術的な定義

ツリーは、ノードと呼ばれるエンティティのコレクションです。ノードはエッジで接続されています。各ノードには値またはデータが含まれ、子ノードがある場合とない場合があります。

ツリーの最初のノードはルートと呼ばれます。このルートノードが別のノードによって接続されている場合、ルートは親ノードになり、接続されたノードは子になります。

すべてのツリーノードは、エッジと呼ばれるリンクで接続されています。ノード間の関係を管理するため、ツリーの重要な部分です。

葉は、ツリーの最後のノードです。それらは子のないノードです。本物の木のように、根、枝、そして最後に葉があります。

理解すべきその他の重要な概念は、高さと深さです。

木の高さは、葉への最長パスの長さです。

ノードの深さは、ルートへのパスの長さです。

用語の概要

  • ルートはツリーの最上位ノードです
  • エッジは2つのノード間のリンクです
  • 子は、親ノードを持つノードです
  • 親は、子ノードへのエッジを持つノードです
  • リーフは、ツリー内に子ノードを持たないノードです
  • 高さは、葉への最長経路の長さです
  • 深さは、ルートへのパスの長さです

二分木

次に、特定のタイプのツリーについて説明します。これをバイナリツリーと呼びます。

「コンピューターサイエンスでは、バイナリツリーはツリーデータ構造であり、各ノードには最大で2つの子があり、左の子と右の子と呼ばれます。」—ウィキペディア

それでは、二分木の例を見てみましょう。

二分木をコーディングしましょう

バイナリツリーを実装するときに最初に留意する必要があるのは、それがノードのコレクションであることです。各ノードには、value、left_child、right_childの3つの属性があります。

これらの3つのプロパティで初期化する単純なバイナリツリーをどのように実装しますか?

見てみましょう。

ここにあります。バイナリツリークラス。

オブジェクトをインスタンス化するとき、値(ノードのデータ)をパラメーターとして渡します。 left_childとright_childを見てください。両方ともNoneに設定されます。

どうして?

私たちがノードを作成するとき、それは子を持っていませんので。ノードデータがあります。

テストしてみましょう。

それでおしまい。

文字列「a」を値としてバイナリツリーノードに渡すことができます。値、left_child、およびright_childを出力すると、値を確認できます。

挿入部分に行きましょう。ここで何をする必要がありますか?

新しいノードを左右に挿入するメソッドを実装します。

ルールは次のとおりです。

  • 現在のノードに左の子がない場合、新しいノードを作成し、現在のノードのleft_childに設定します。
  • 左の子がある場合、新しいノードを作成し、現在の左の子の場所に配置します。この左の子ノードを新しいノードの左の子に割り当てます。

引き出しましょう。 :)

コードは次のとおりです。

繰り返しますが、現在のノードに左の子がない場合、新しいノードを作成し、現在のノードのleft_childに設定します。または、新しいノードを作成し、現在の左の子の場所に配置します。この左の子ノードを新しいノードの左の子に割り当てます。

そして、同じことをして正しい子ノードを挿入します。

できた:)

しかし、完全ではありません。まだテストする必要があります。

次のツリーを構築しましょう。

このツリーの図を要約するには:

  • ノードはバイナリツリーのルートになります
  • 左の子はbノード
  • 正しい子はcノードです
  • b右の子はdノード(bノードには左の子がありません)
  • c左の子はeノード
  • c右の子はfノード
  • eノードとfノードの両方に子がありません

ツリーのコードは次のとおりです。

挿入が完了しました。

次に、ツリートラバーサルについて考える必要があります。

ここには、深さ優先検索(DFS)と幅優先検索(BFS)の2つのオプションがあります。

  • DFSは、「ツリーデータ構造を走査または検索するためのアルゴリズムです。ルートから開始し、バックトラッキングする前に各ブランチに沿って可能な限り探索します。」—ウィキペディア
  • BFSは、「ツリーデータ構造を走査または検索するためのアルゴリズムです。ツリーのルートから始まり、次のレベルのネイバーに移動する前に、最初にネイバーノードを探索します。」—ウィキペディア

それでは、各ツリートラバーサルタイプについて詳しく見ていきましょう。

深さ優先検索(DFS)

DFSは、別のパスをバックトラッキングおよび探索する前に、リーフまでのパスをすべて探索します。このタイプのトラバーサルの例を見てみましょう。

このアルゴリズムの結果は1–2–3–4–5–6–7になります。

どうして?

分解しましょう。

  1. ルート(1)から開始します。印刷してください。

2.左の子に移動します(2)。印刷してください。

3.次に、左の子に移動します(3)。印刷してください。 (このノードには子がありません)

4.バックトラックして、適切な子に移動します(4)。印刷してください。 (このノードには子がありません)

5.ルートノードに戻り、右側の子に移動します(5)。印刷してください。

6.左の子に移動します(6)。印刷してください。 (このノードには子がありません)

7.バックトラックして、右の子に移動します(7)。印刷してください。 (このノードには子がありません)

8.完了。

リーフに戻ってバックトラックするとき、これはDFSアルゴリズムと呼ばれます。

このトラバーサルアルゴリズムに精通したので、DFSのタイプ(予約注文、注文注文、注文注文)について説明します。

予約注文

これはまさに上記の例で行ったことです。

  1. ノードの値を印刷します。
  2. 左の子に移動して印刷します。これは、子が残っている場合に限ります。
  3. 適切な子に移動して印刷します。これは、適切な子がある場合に限ります。

順番に

このツリーの例の順序アルゴリズムの結果は3–2–4–1–6–5–7です。

左が最初、中央が秒、右が最後です。

それではコーディングしましょう。

  1. 左の子に移動して印刷します。これは、子が残っている場合に限ります。
  2. ノードの値を印刷します
  3. 適切な子に移動して印刷します。これは、適切な子がある場合に限ります。

ポストオーダー

このツリーの例のポストオーダーアルゴリズムの結果は、3–4–2–6–7–5–1です。

左が最初、右が2番目、中央が最後です。

これをコーディングしましょう。

  1. 左の子に移動して印刷します。これは、子が残っている場合に限ります。
  2. 適切な子に移動して印刷します。これは、適切な子がある場合に限ります。
  3. ノードの値を印刷します

幅優先検索(BFS)

BFSアルゴリズムは、レベルごとおよび深さごとにツリーを走査します。

このアルゴリズムをよりよく説明するのに役立つ例を次に示します。

したがって、レベルごとにトラバースします。この例では、結果は1–2–5–3–4–6–7です。

  • レベル/深さ0:値1のノードのみ
  • レベル/深さ1:値2および5のノード
  • レベル/深さ2:値3、4、6、および7のノード

それではコーディングしましょう。

BFSアルゴリズムを実装するには、キューデータ構造を使用して支援します。

どのように機能しますか?

ここに説明があります。

  1. 最初に、putメソッドを使用してルートノードをキューに追加します。
  2. キューが空でない間に繰り返します。
  3. キューの最初のノードを取得し、その値を出力します。
  4. 左と右の両方の子をキューに追加します(現在のノードに子がある場合)。
  5. できたqueuehelperを使用して、各ノードの値をレベルごとに出力します。

バイナリ検索ツリー

「バイナリ検索ツリーは、順序付きまたはソートされたバイナリツリーと呼ばれることもあり、ルックアップやその他の操作でバイナリ検索の原理を使用できるように、その値をソート順に保持します」—ウィキペディア

バイナリ検索ツリーの重要な特性は、バイナリ検索ツリーノードの値が左の子の子孫の値よりも大きいが、右の子の子孫の値よりも小さいことです。

上の図の内訳は次のとおりです。

  • Aは反転します。サブツリー7–5–8–6は右側にある必要があり、サブツリー2–1–3は左側にある必要があります。
  • Bが唯一の正しいオプションです。 Binary Search Treeプロパティを満たします。
  • Cには1つの問題があります。値4のノードです。5より小さいため、ルートの左側にある必要があります。

バイナリ検索ツリーをコーディングしましょう!

さあ、コーディングの時間です!

ここで何が見えますか?新しいノードを挿入し、値を検索し、ノードを削除し、ツリーのバランスを取ります。

始めましょう。

挿入:新しいノードをツリーに追加する

空のツリーがあり、次の値を持つ新しいノードをこの順序で追加することを想像してください:50、76、21、4、32、100、64、52。

最初に知る必要があるのは、50がツリーのルートであるかどうかです。

これで、ノードごとにノードの挿入を開始できます。

  • 76は50より大きいため、76を右側に挿入します。
  • 21は50より小さいため、21を左側に挿入します。
  • 4は50より小さい。値50のノードには左の子21があります。4は21より小さいため、このノードの左側に挿入します。
  • 32は50より小さい。値50のノードには左の子21があります。32は21より大きいので、このノードの右側に32を挿入します。
  • 100は50より大きい。値50のノードには右の子76があります。100は76より大きいため、このノードの右側に100を挿入します。
  • 64は50より大きい。値50のノードには右の子76があります。64は76より小さいため、このノードの左側に64を挿入します。
  • 値50のノードには右の子76があります。52は76より小さいため、値76のノードには左の子64があります。52は64より小さいので、このノードの左側に挿入54します。

ここにパターンがありますか?

分解しましょう。

  1. 新しいノード値は現在のノードよりも大きいですか、小さいですか?
  2. 新しいノードの値が現在のノードより大きい場合、右のサブツリーに移動します。現在のノードに適切な子がない場合は、そこに挿入するか、手順1に戻ります。
  3. 新しいノードの値が現在のノードよりも小さい場合は、左のサブツリーに移動します。現在のノードに左の子がない場合は、そこに挿入するか、手順1に戻ります。
  4. ここでは特別なケースを処理しませんでした。新しいノードの値がノードの現在の値と等しい場合、ルール番号3を使用します。サブツリーの左側に等しい値を挿入することを検討してください。

それではコーディングしましょう。

とても簡単そうです。

このアルゴリズムの強力な部分は、9行目と13行目にある再帰部分です。両方のコード行がinsert_nodeメソッドを呼び出し、それぞれ左と右の子に使用します。 11行目と15行目は、各子の挿入を行う行です。

ノード値を検索しましょう…

ここで作成するアルゴリズムは、検索を実行することです。指定された値(整数値)に対して、バイナリ検索ツリーにその値があるかどうかがわかります。

注意すべき重要な項目は、ツリー挿入アルゴリズムの定義方法です。まず、ルートノードがあります。左のサブツリーノードはすべて、ルートノードよりも小さい値になります。そして、すべての適切なサブツリーノードは、ルートノードよりも大きな値を持ちます。

例を見てみましょう。

このツリーがあると想像してください。

ここで、値52に基づくノードがあるかどうかを知りたいと思います。

分解しましょう。

  1. 現在のノードとしてルートノードから始めます。指定された値は現在のノード値よりも小さいですか?はいの場合、左側のサブツリーで検索します。
  2. 指定された値は現在のノード値よりも大きいですか?はいの場合、正しいサブツリーで検索します。
  3. ルール#1と#2が両方ともfalseの場合、現在のノード値と指定された値が等しい場合、それらを比較できます。比較がtrueを返す場合、「はい!私たちのツリーには与えられた価値があります。」そうでなければ、「いや、そうではない」と言います。

それではコーディングしましょう。

コードを見てみましょう。

  • 行8と9はルール#1に該当します。
  • 行10と11はルール#2に該当します。
  • 行13はルール#3に該当します。

どうやってテストしますか?

ルートノードを値15で初期化して、バイナリ検索ツリーを作成しましょう。

そして今、多くの新しいノードを挿入します。

挿入された各ノードについて、find_nodeメソッドが実際に機能するかどうかをテストします。

ええ、それはこれらの与えられた値に対して機能します!バイナリ検索ツリーに存在しない値をテストしましょう。

そうそう。

検索が完了しました。

削除:削除および整理

さまざまなケースを処理する必要があるため、削除はより複雑なアルゴリズムです。特定の値について、この値を持つノードを削除する必要があります。このノードの次のシナリオを想像してください。子を持たない、子を1つ、または子を2つ持っています。

  • シナリオ#1:子のないノード(リーフノード)。

削除するノードに子がない場合、単純に削除します。アルゴリズムはツリーを再編成する必要はありません。

  • シナリオ#2:子が1つだけのノード(左または右の子)。

この場合、アルゴリズムでは、ノードの親が子ノードを指すようにする必要があります。ノードが左の子である場合、左の子の親が子を指すようにします。ノードがその親の右の子である場合、右の子の親が子を指すようにします。

  • シナリオ#3:2つの子を持つノード。

ノードに2つの子がある場合、ノードの正しい子から最小値を持つノードを見つける必要があります。削除するノードの場所に最小値のこのノードを配置します。

コーディングの時間です。

  1. 最初:パラメーター値と親に注意してください。この値を持つノードを見つけたいのですが、ノードの削除にはノードの親が重要です。
  2. 2番目:戻り値に注意してください。アルゴリズムはブール値を返します。ノードを見つけて削除するとTrueを返します。それ以外の場合は、Falseを返します。
  3. 2行目から9行目:探している値を持つノードの検索を開始します。値が現在のnodevalueよりも小さい場合、再帰的に左のサブツリーに移動します(現在のノードに左の子がある場合のみ)。値が大きい場合、再帰的に右のサブツリーに移動します。
  4. 10行目:削除アルゴリズムについて考え始めます。
  5. 11行目から13行目:子のないノードをカバーします。これは、その親からの左の子です。親の左の子を[なし]に設定して、ノードを削除します。
  6. 14行目と15行目:子のないノードをカバーします。これは、親からの正しい子です。親の右の子を[なし]に設定して、ノードを削除します。
  7. クリアノードメソッド:clear_nodeコードを以下に示します。ノードleft child、right child、およびその値をNoneに設定します。
  8. 16行目から18行目:ノードを1つの子(左の子)だけでカバーし、その親からの左の子です。親の左の子をノードの左の子(子を持つ唯一の子)に設定します。
  9. 19行目から21行目:ノードを1つの子(左の子)だけでカバーし、その親から右の子です。親の右の子をノードの左の子(ノードの唯一の子)に設定します。
  10. 22行目から24行目:ノードを1つの子(右の子)だけでカバーし、その親から左の子です。親の左の子をノードの右の子(唯一の子)に設定します。
  11. 25行目から27行目:ノードを1つの子(右の子)だけでカバーします。これは、その親から右の子です。親の右の子をノードの右の子(唯一の子)に設定します。
  12. 28行目から30行目:ノードを左と右の両方の子でカバーします。最小値を持つノードを取得し(コードを以下に示します)、現在のノードの値に設定します。最小のノードを削除して終了します。
  13. 行32:探しているノードが見つかった場合、Trueを返す必要があります。 11行目から31行目まで、このケースを処理します。 Trueを返すだけです。
  • clear_nodeメソッドを使用するには:None値を3つの属性すべて(value、left_child、right_child)に設定します
  • find_minimum_valueメソッドを使用するには、左に進みます。もうノードが見つからない場合は、最小のノードを見つけました。

それではテストしてみましょう。

このツリーを使用して、remove_nodeアルゴリズムをテストします。

値8のノードを削除しましょう。これは、子のないノードです。

次に、値17のノードを削除します。これは、子が1つだけのノードです。

最後に、2つの子を持つノードを削除します。これがツリーのルートです。

これでテストが完了しました。 :)

それは今のところすべてです!

ここで多くのことを学びました。

この密なコンテンツを完成させていただきありがとうございます。私たちが知らない概念を理解するのは本当に難しいです。しかし、あなたはそれをやった。 :)

これは、アルゴリズムとデータ構造の学習と習得への道のりのもう1つのステップです。私の完全な旅のドキュメントは、Renaissance Developerの出版物でご覧いただけます。

楽しんで、学習とコーディングを続けてください。

このコンテンツが気に入っていただければ幸いです。 Ko-Fiでの私の仕事をサポートする

私のTwitterとGithub。 ☺

追加のリソース

  • mycodeschoolによるツリーデータ構造の概要
  • ウィキペディアによるツリー
  • 才能のあるヴァイデイ女子によって木に困惑しないようにする方法
  • 木の紹介、ジョナサン・コーエン教授による講演
  • 木の紹介、デイビッド・シュミット教授による講演
  • 木の紹介、ビクター・アダムチク教授による講演
  • ゲイル・ラークマン・マクダウェルの木
  • TKによるバイナリツリーの実装とテスト
  • Courseraコース:カリフォルニア大学サンディエゴ校のデータ構造
  • Courseraコース:カリフォルニア大学サンディエゴ校によるデータ構造とパフォーマンス
  • ポールプログラミングによるバイナリ検索ツリーの概念と実装
  • TKによるバイナリ検索ツリーの実装とテスト
  • ウィキペディアによるツリートラバーサル
  • GeeksforGeeksによるバイナリ検索ツリー削除ノードアルゴリズム
  • アルゴリズムによる二分探索木削除ノードアルゴリズム
  • Pythonをゼロからヒーローに学ぶ