学習アルゴリズム

第6章 バイナリーツリー手のひらの中の無限大

この作品はAIを使って翻訳されている。ご意見、ご感想をお待ちしている：[e-mail]

この章では、次のことを学ぶ：

• 値の挿入、削除、検索によるバイナリツリーの作成と操作方法。

• というグローバルなプロパティを強制するバイナリ検索ツリーを管理する方法：

  • ノードの左サブツリーの値は、すべてそのノードの値より小さいか等しい。

  • あるノードの右サブツリーの値は、すべてそのノードの値より大きいか等しい。

• 検索、挿入、削除の演算子は、バランスの取れた2分木ではO(log N)ですむが、気をつけないと許容できないO(N)にまで劣化する可能性がある。

• 検索、挿入、削除においてO(log N)の性能を保証するために、挿入と削除の演算子の後にバイナリ探索木のバランスを調整する方法。

• O(N)のパフォーマンスで各値を昇順に処理するためにバイナリ検索ツリーをトラバースする方法。

• バイナリツリー構造を使ってシンボルテーブル・データ型を実装し、そのキーをソート・オーダーで取得できるという利点を追加する方法。

• バイナリツリー構造を使ってプライオリティ・キューを実装する方法。プライオリティ・キューを混乱させることなく、(主, 値)エントリを優先順位順に生成できるという利点がある。

はじめに

リンクされたリストと配列は、直線的な配置で情報を格納する。この章では、コンピューターサイエンスの分野で最も重要な概念の一つであるバイナリーツリー再帰的データ構造を紹介する。第5章では、関数が自分自身を呼び出す再帰の概念について学んだ。この章では、バイナリーツリーが再帰的データ構造であること、つまり他のバイナリーツリー構造を参照することを学ぶ。再帰的データ構造の概念を紹介するために、すでに見たリンクリストのデータ構造をもう一度見てみよう。

リンクリストは再帰的データ構造の一例であり、各ノードはサブリストの最初のノードへの参照（next ）を持つ。リンクリストは、N個の値の集合の動的な成長と縮小をサポートすることで、固定長配列を改良している。リスト6-1に示すsum_list() 再帰関数は、リンクリストを処理してその和を返す。この実装を、従来の反復処理と比較してみよう。

リスト6-1. リンクリストの値を合計する再帰的関数と反復関数

class Node:
  def __init__(self, val, rest=None):
    self.value = val
    self.next = rest

def sum_iterative(n):
  total = 0                         
  while n:
    total += n.value                
    n = n.next                      
  return ...