「アルゴリズムとデータ構造」二分木の美しさ

[[349809]]

序文

今回レビューする内容は、データ構造トピックの「ツリー」です。ツリーなどのデータ構造を見ると頭が痛くなる、理解しにくいという方は、この記事が参考になるかもしれません。

諺にあるように、何かを把握して理解したいのであれば、まずその概念や特性などを理解しなければなりません。

紹介ツリーは以下の点を中心に開発されています👇

木の基本概念

基本用語
木の種類
バイナリツリーの概念
二分木の走査
二分木問題の概要

マインドマップ 👇

木の基本概念

ツリーは、ツリーのような構造を持つデータセットをシミュレートするために使用されます。あるいは、これを「抽象データ構造」、つまりこの抽象データ型を実装し、ツリーのような構造プロパティを持つデータセットをシミュレートするために使用されるデータ構造と考えることもできます。

Wikipedia の定義によれば、次のように理解できるようです。

これは、n (n>0) 個の有限ノードで構成される階層セットです。根が上を向き、葉が下を向いている逆さまの木のように見えることから「木」と呼ばれています。以下の機能があります:

各ノードには有限の数の子ノードが存在するか、子ノードが存在しません。
親ノードを持たないノードはルートノードと呼ばれます。
ルート以外の各ノードには親ノードが 1 つだけあります。
ルートノードを除き、各子ノードは複数の分離したサブツリーに分割できます。
ツリーにはサイクルがありません。

このとき、写真を取り出して見る必要があります👇

図から、上記の5つの特徴がよくまとめられます。

ノード A はルートノードであり、親ノードがないため、ルートノードになります。
ルートノード (A) を除く他のすべてのノードには親ノードがあり、各ノードには限られた数の子ノードのみが存在するか、子ノードが存在しません。
あるノードから始まって、多くのサブツリーに分割することができます。例えば、ノード B から始まる場合がこれに該当します。

木についての知識が少し得られたので、次は木に関する用語をいくつか理解する必要があります。

基本用語

基本的なツリー用語

より正式な要約については、Wikipedia の説明をご覧ください。

「ノード次数」: ノードに含まれるサブツリーの数はノードの次数と呼ばれます。
「ツリー次数」: ツリーでは、最大ノード次数をツリー次数と呼びます。
「リーフノード」または「ターミナルノード」: 次数が 0 のノード。
「非終端ノード」または「分岐ノード」: 次数がゼロでないノード。
「父ノード」または「親ノード」: ノードに子ノードがある場合、このノードはその子ノードの親ノードと呼ばれます。
「子ノード」または「サブノード」: ノードに含まれるサブツリーのルートノードは、ノードの子ノードと呼ばれます。
「兄弟ノード」: 同じ親ノードを持つノードは兄弟ノードと呼ばれます。
ノード「レベル」: ルートから始まり、ルートが最初のレベル、ルートの子ノードが 2 番目のレベル、というように続きます。
「深さ」: 任意のノード n の場合、n の深さはルートから n までの一意のパスの長さであり、ルートの深さは 0 です。
「高さ」: 任意のノード n の場合、n の高さは n からリーフまでの最長パスであり、すべてのリーフの高さは 0 です。
「いとこノード」: 親ノードが同じレイヤーにあるノードは互いにいとこです。
「ノードの祖先」: ルートからノードまでのブランチ上のすべてのノード。
「子孫」: ノードをルートとするサブツリー内のノードは、そのノードの子孫と呼ばれます。
「フォレスト」: 互いに素な m (m>=0) 本のツリーの集合をフォレストと呼びます。

上記の図を組み合わせることで、これらの概念を理解することができます。 2 つを組み合わせることで、ツリーをより深く理解できるようになります。

上記の基本的な概念といくつかの専門用語を使用して、木を分類し、どのような種類の木があるのかを確認する必要があります。

木の種類

木の概念と基本的な用語を理解したので、次に木の種類について詳しく説明します。

分類の基準としてWikipediaを使うことができます👇

順序なしツリー: ツリー内のどのノードの子ノード間にも順序関係はありません。この種類のツリーは順序なしツリー、またはフリーツリーと呼ばれます。
順序付きツリー: ツリー内の任意のノードの子ノード間には順序関係があります。この種類のツリーは順序付きツリーと呼ばれます。
完全二分木: 二分木の場合、その深さは d (d>1) であると仮定します。 d 番目の層を除いて、他の層のノードの数は最大値に達しており、d 番目の層のすべてのノードは左から右に連続して密に配置されています。このような二分木は完全二分木と呼ばれます。
バランス二分木 (AVL 木): 任意のノードの 2 つのサブツリー間の高さの差が 1 以下である場合にのみ二分木になります。
ソート済みバイナリツリー (英語: Binary Search Tree): バイナリ検索ツリー、順序付きバイナリツリーとも呼ばれます。
完全二分木: すべてのリーフノードが最下層にある完全な二分木。
二分木: 各ノードに最大 2 つのサブツリーが含まれるツリーを二分木と呼びます。
ハフマンツリー: 最短の重み付きパスを持つ二分木は、ハフマンツリーまたは最適二分木と呼ばれます。
B ツリー: 読み取りおよび書き込み操作に最適化され、データを順序どおりに維持でき、2 つ以上のサブツリーを持つ自己バランス型バイナリ検索ツリー。

ツリーの分類が非常に多いため、それらを 1 つずつ習得する必要がありますか? 個人的には、最も単純で最も広く使用されているツリーの種類でもあるバイナリツリーの構造を習得すれば十分だと思います。

次に、バイナリツリーを紹介します。

二分木の概念

バイナリツリーは典型的なツリー構造です。名前が示すように、バイナリツリーは、各ノードに最大 2 つのサブツリー (通常は「左サブツリー」と「右サブツリー」と呼ばれます) が含まれるツリー構造です。

バイナリツリー

この図の内容から判断すると、バイナリツリーの構造が明確に示されているはずです。

二分木の性質については、補足知識として下の図を参考にしてください。個人的には、ここがポイントではないと思います。

二分木の特性

重要なのは、そのトラバーサル方法を習得する必要があるということです。

二分木の走査

バイナリツリーをトラバースする一般的な方法は次の 3 つであることがわかっています。

事前順序トラバーサル
順序通りの走査
その後のトラバース

どのようなトラバーサル手法でも、非再帰バージョンだけでなく、基本的なアルゴリズムスキルをテストする再帰バージョンも習得する必要があります。次に、再帰バージョンについて見てみましょう。

事前順序トラバーサル

バイナリツリーの事前順序走査を練習するにはここをクリックしてください

バイナリツリーのルートノードが指定されると、そのノード値の「事前順序」トラバーサルが返されます。

偽のデータを模擬するとします👇

入力: [1, null ,2,3]
   1
    \
     2
    /
   3
出力: [1,3,2]

次に、事前順序探索の理解に基づいて、問題を解決するための疑似コードを書くことができます👇

 // 天天アップ
// *関数TreeNode(val, left , right ) {
 // * this.val = (val===undefined ? 0 : val)
 // * this.left = ( left === undefined ? null : left )
 // * this.right = ( right === undefined ? null : right )
 // * }
 inorderTraversal = (root, arr = []) とします => {
  if(ルート) {
    inorderTraversal(ルート.left , arr)
    arr.push(ルート.値)
    inorderTraversal(ルート.right , arr)
  }
リターン
}

非再帰バージョン 👇

非再帰の場合、ノードを格納するためのデータ構造を使用する必要があります。使用する必要があるのはスタックです。そのアイデアは参考になります👇

ルートノードはターゲットノードであり、その子ノードへのトラバーサルが開始されます。
1. ターゲットノードにアクセスする
2. 左の子をスタックにプッシュします -> 左の子が空になるまで
3. スタックからノードをポップし、右の子をターゲットノードとして取得し、1、2、3を順番に実行します。

 preorderTraversal = (root, arr = []) => {を設定します。
  定数スタック = []、res = []
  現在の値をルートとする
  while(現在|| スタックの長さ > 0) {
    while (現在) {
      res.push(現在の.val)
      stack.push(現在の)
現在=現在.左 
    }
現在の= stack.pop()
現在=現在.右 
  }
戻り値
}

順序通りの走査

バイナリツリーが与えられた場合、その順序どおりのトラバーサルを返します。

例：

入力: [1,null,2,3] 1
23
出力: [1,3,2]

上級: 再帰アルゴリズムは単純ですが、反復アルゴリズムで実行できますか?

再帰バージョン 👇

 const inorderTraversal = (ルート、arr = []) => {
  if(ルート) {
    inorderTraversal(ルート.left , arr)
    arr.push(ルート.val)
    inorderTraversal(ルート.right 、 arr)
  }
リターン
}

非再帰バージョンについてはここでは説明しません。これは、事前順序トラバーサルと同じ考え方で、スタックを使用してノード情報を維持します。

 const inorderTraversal = (ルート、arr = []) => {
  定数スタック = []、res = []
  現在の値をルートとする
  while(現在|| スタックの長さ > 0) {
    while (現在) {
      stack.push(現在の)
現在=現在.左 
    }
現在の= stack.pop()
    res.push(現在の.val)
現在=現在.右 
  }
戻り値
}

その後のトラバース

バイナリツリーが与えられた場合、その後順トラバーサルを返します。

例：

入力: [1,null,2,3]
1
23
出力: [3,2,1]

上級: 再帰アルゴリズムは単純ですが、反復アルゴリズムで実行できますか?

出典: LeetCode リンク: https://leetcode-cn.com/problems/binary-tree-postorder-traversal 著作権は LeetCode Network に帰属します。商用目的での複製については、正式な許可を得るためにお問い合わせください。非商用目的での複製については、出典を明記してください。

再帰バージョン 👇

 const postorderTraversal = (ルート、arr = []) => {
  if(ルート) {
    postorderTraversal(ルート.left , arr)
    postorderTraversal(ルート.right 、 arr)
    arr.push(ルート.val)
  }
リターン
}

非再帰バージョン 👇

実は、最初の2つをやると、ルーチンがあることがわかりますよ〜

 const postorderTraversal = (ルート、arr = []) => {
  定数スタック = []、res = []
  let current = root, last = null //最後のポインタは前のノードを記録します
  while(現在|| スタックの長さ > 0) {
    while (現在) {
      stack.push(現在の)
現在=現在.左 
    }
現在のスタック = [スタックの長さ - 1]
    if (! current . right || current . right == last ) {
現在の= stack.pop()
      res.push(現在の.val)
最後=現在 
 current = null // スタックのポップを続行
    }それ以外{
現在=現在.右 
    }
  }
戻り値
}

バイナリツリーのレベルトラバーサル ⭐⭐

リンク: 二分木のレベル順走査

バイナリツリーが与えられた場合、「レベル順トラバーサル」によって取得されたノード値を返します。 (つまり、すべてのノードを左から右へ、レイヤーごとに訪問します)。

例: バイナリツリー: [3,9,20,null,null,15,7],

3
/
9 20 /
15 7

レベルトラバーサルの結果を返します:

[ [3]、[9,20]、[15,7] ]

出典: LeetCode リンク: https://leetcode-cn.com/problems/binary-tree-level-order-traversal 著作権は LeetCode Network に帰属します。商用目的での複製については、正式な許可を得るためにお問い合わせください。非商用目的での複製については、出典を明記してください。

再帰バージョン 👇

 const levelOrder =関数(ルート) {
  if(!root) return []
  res = [] とします
  dfs(ルート, 0, res)
戻り値
} 
 
関数dfs(ルート、ステップ、res){
  if(ルート){
      if (!res[ステップ]) res[ステップ] = []
      res[ステップ].push(ルート.val)
      dfs(ルート.左, ステップ+1, res)
      dfs(ルート.right , ステップ+1, res)
    }
 }

非再帰バージョン 👇

ここで使用されるのは、キューデータ構造と先入れ先出しメカニズムです。

 const レベルオーダー = (ルート) => {
  キュー = []、res = [] とします。
  if (root) queue.push(root);
  while (キューの長さ) {
      next_queue = [] とします。
          今_res = []
      while (キューの長さ) {
          ルート = キュー.shift()
          now_res.push(ルート.val)
          root.left && next_queue.push( root.left )
          root.right && next_queue.push( root.right )
      }
      キュー = 次のキュー
      res.push(now_res)
  }
戻り値
}