"BinaryTree" (データ構造)

"BinaryTree"

各ノードに保存される値が一般式である可変二分木を表す．

詳細

  • 二分木は，各ノードに関連付けられたデータに基づくノードを評価するためだけでなく，2つまでの枝との階層関係を表すためにも役立つ．
  • CreateDataStructure["BinaryTree",v]指定された初期値 v を持ち，左と右に子を持たない新しい"BinaryTree"を作成する
    CreateDataStructure["BinaryTree",v{l,r}]指定された初期値 v と指定された左と右の子を持つ新しい"BinaryTree"を作成する
    Typed[x,"BinaryTree"]x に"BinaryTree"型を与える
  • "BinaryTree"型のデータ構造については，以下の演算が使える．
  • ds["BreadthFirstScan",f]ds の幅優先探索を行い，各ノードのデータを f に渡すtime: O(n)
    ds["Copy"]ds のコピーを返すtime: O(n)
    ds["Data"]木のノード ds に保存されたデータを返すtime: O(1)
    ds["InOrderScan",f]ds の間順探索を行い，各ノードのデータを f に渡すtime: O(n)
    ds["Left"]ds の左の子のデータ構造を返すtime: O(1)
    ds["LeftNullQ"]ds の左の子が空値である場合にTrueを返すtime: O(1)
    ds["NullQ"]ds が空値である場合にTrueを返すtime: O(1)
    ds["PostOrderScan",f]ds の後順探索を行い，各ノードのデータを f に渡すtime: O(n)
    ds["PreOrderScan",f]ds の前順探索を行い，各ノードのデータを f に渡すtime: O(n)
    ds["Right"]ds の右の子のデータ構造を返すtime: O(1)
    ds["RightNullQ"]ds の右の子が空値である場合にTrueを返すtime: O(1)
    ds["SetData",v]木のノード ds に保存されたデータを v に設定するtime: O(1)
    ds["SetLeft",l]木のノード ds の左の子を l に設定するtime: O(1)
    ds["SetRight",r]木のノード ds の右の子を r に設定するtime: O(1)
    ds["ValidQ"]ds が有効な木である場合にTrueを返すtime: O(n)
    ds["Visualization"]ds の可視化を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Normal[ds]ds を通常の式に変換する

例題

すべて開くすべて閉じる

例  (2)

新しい"BinaryTree"は，CreateDataStructureを使って作成できる：

保存された値を抽出する：

保存する新しい値を挿入する：

値が更新されたことを確かめる：

左の子は空値である：

右の子は空値である：

指定された子を持つ新しい"BinaryTree"を作成する：

左に子を持つ：

左の子を返す：

式バージョンの ds を返す：

データ構造の可視化を生成することができる：

スコープ  (1)

情報  (1)

新しい"BinaryTree"は，CreateDataStructureを使って作成することができる：

データ構造 ds についての情報：

アプリケーション  (7)

二分探索木  (1)

二分木は，順序付けられたものをソートするのに使われる．通常これらは二分探索木と呼ばれる．以下は，簡単な挿入プログラムである：

二分木を作成し，乱数を30個挿入する：

二分木に対して間順探索を行う．ソートされているので，この例で示されるように，要素はソートされた順に訪れられる：

このような基本の二分探索木の問題は，挿入鎖が非平衡になり，木の最大深さが大きくなる可能性がある点である．この問題は，さまざまな形式の平衡二分木によって修正される．

木の回転  (1)

ソートされた二分木の回転演算には，要素の順序を維持しながら木構造を変更させることが必要である．回転演算は，平衡二分木を作成する数多くの方法によって使用される．

右回転と左回転を行う基本の木の回転演算を以下に示す：

ここでは二分木が作成される．左に2つのレベルのノードがあり，右には何もない．これは非効率的なストレージである：

右回転は，ソートされた特性を維持しつつ，ノードを右に移動させ，より平衡の取れた木にする：

左回転は，ソートされた特性を維持しつつ，ノードを左に戻す：

ランダムな木  (1)

指定の深さで二分木にランダムなノードを挿入するプログラム：

二分木の最大の深さを計算する  (1)

二分木の最大の深さは，根のノードから葉のノードまでの最長経路に沿ったノードの数である．

二分木の最大の深さを計算するプログラム：

サンプルの木：

最大の深さ：

最下位共通先祖を求める  (1)

木における2つのノードの最下位共通先祖は，両方のノードを子孫として持つ最下位（最も深い）ノードである．これは，簡単なコードで計算できる．

木にランダムなノードを挿入するプログラム．これは，すべてのノードが他と区別できるものであることを確かめるためにカウンタを使う：

乱数種を設定して，再生可能な例を得る：

ランダムな木を作成し，それを可視化する：

最下位共通先祖を求めるプログラム：

最下位共通項を求める：

可視化を使うと，解が正しいことを確かめることができる：

二分木が対称であるかどうかを検証する  (1)

二分木は，その真ん中に対称面がある場合には対称である．

二分木が対称であるかどうかを検証するプログラム．これは，データが等しく，左と右のノードが対称であることをチェックする：

対称ではない木：

非対称であることが確かめられた：

対称である木：

対称であることが確かめられた：

二分木の直径を求める  (1)

二分木の直径は，任意の2つのノード間の最長経路（根を通る場合も通らない場合もある）の長さである．

二分木の直径を計算するプログラム：

サンプルの木：

直径を計算する：

別のサンプルの木：

直径を計算する：

考えられる問題  (2)

空ノード  (1)

いくつかのデータで二分木を作成する：

右の子を抽出する：

これは空ノードである：

空ノードの内容に対して作用する演算を行うとエラーが発生する：

空ノードのシリアライゼーションはNullである：

CreateDataStructureで空ノードを作成する：

Wolfram言語における空ノードの表現は，ノードが空であるかどうかをチェックしなくても，二分木のノードを操作するアルゴリズムを書くことが可能となるので，大変便利である．

有効な木  (1)

Wolfram言語の二分木のインターフェースは，柔軟かつ効率的であるように設計されている．このことによって，作成した構造に何らかの影響があることもある．

いくつかのデータで二分木を作成する：

別の木を作成し，右の子を持つようにする：

演算に右の子を親に等しくすることを妨げるものは何もない：

結果としてできたものは木ではない．このことは，"ValidQ"演算を使って確かめることができる：

演算によっては，木が有効でない場合にエラーを発することもある：

無効な構造が作成された場合に挿入関数がエラーを発しないということは，それらの関数があまり効率的ではないということである．データ構造をシリアライズするこのような演算には，組込みのチェックが含まれている．