WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

"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を使って作成できる：

Wolfram Language code: ds = CreateDataStructure["BinaryTree", 10]

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

Wolfram Language code: ds["Data"]

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

Wolfram Language code: ds["SetData", 12]

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

Wolfram Language code: ds["Data"]

左の子は空値である：

Wolfram Language code: ds["LeftNullQ"]

右の子は空値である：

Wolfram Language code: ds["RightNullQ"]

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

Wolfram Language code: ds = CreateDataStructure["BinaryTree", 1 -> {2 -> {5, Null}, 8}]

左に子を持つ：

Wolfram Language code: ds["LeftNullQ"]

左の子を返す：

Wolfram Language code: ds["Left"]

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

Wolfram Language code: Normal[ds]

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

Wolfram Language code: ds["Visualization"]

スコープ  (1)

情報  (1)

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

Wolfram Language code: ds = CreateDataStructure["BinaryTree", f[1]]

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

Wolfram Language code: Information[ds]

アプリケーション  (7)

二分探索木  (1)

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

Wolfram Language code: insert[node_, d_] := With[{curr = node["Data"]}, Which[ d < curr, If[node["LeftNullQ"], node["SetLeft", CreateDataStructure["BinaryTree", d]], insert[node["Left"], d]] , d > curr, If[node["RightNullQ"], node["SetRight", CreateDataStructure["BinaryTree", d]], insert[node["Right"], d]] ] ]

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

Wolfram Language code: ds = CreateDataStructure["BinaryTree", 50]; Scan[insert[ds, #]&, RandomInteger[{0, 500}, 30]];
Wolfram Language code: ds["Visualization"]

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

Wolfram Language code: arr = CreateDataStructure["DynamicArray"];ds["InOrderScan", arr["Append", #]&]; arr//Normal

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

木の回転  (1)

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

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

Wolfram Language code: RightRotate[y_] := Module[{x, tmp}, x = y["Left"]; tmp = x["Right"]; x["SetRight", y]; y["SetLeft", tmp]; x]
Wolfram Language code: LeftRotate[x_] := Module[{y, tmp}, y = x["Right"]; tmp = y["Left"]; y["SetLeft", x]; x["SetRight", tmp]; y]

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

Wolfram Language code: ds = CreateDataStructure["BinaryTree", 3 -> {1 -> {0, Null}, Null}]; ds["Visualization"]

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

Wolfram Language code: ds = RightRotate[ds]; ds["Visualization"]

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

Wolfram Language code: ds = LeftRotate[ds]; ds["Visualization"]

ランダムな木  (1)

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

Wolfram Language code: InsertRandom[node_, lim_] := Module[ {test, newNode}, test = RandomChoice[ {Left, Right, All}]; If[ (test === Left || test === All) && lim ≥ 0, newNode = CreateDataStructure["BinaryTree", 1]; node["SetLeft", newNode]; InsertRandom[newNode, lim - 1]]; If[(test === Right || test === All) && lim ≥ 0, newNode = CreateDataStructure["BinaryTree", 1]; node["SetRight", newNode]; InsertRandom[newNode, lim - 1]]; node ]
Wolfram Language code: ds = InsertRandom[CreateDataStructure["BinaryTree", 1], 4]
Wolfram Language code: ds["Visualization"]

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

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

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

Wolfram Language code: MaximumDepth[tree_] := If[tree["NullQ"], 0, Max[MaximumDepth[tree["Left"]], MaximumDepth[tree["Right"]]] + 1 ]

サンプルの木：

Wolfram Language code: tree = CreateDataStructure["BinaryTree", 1 -> {2 -> {5 -> {7 -> {8, Null}, Null}, Null}, 2 -> {Null, 5}}]; tree["Visualization"]

最大の深さ：

Wolfram Language code: MaximumDepth[tree]

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

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

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

Wolfram Language code: InsertRandom[node_, cnt_, lim_] := Module[ {test, newNode}, test = RandomChoice[ {Left, Right, All}]; If[ (test === Left || test === All) && lim ≥ 0, newNode = CreateDataStructure["BinaryTree", cnt["Increment"]]; node["SetLeft", newNode]; InsertRandom[newNode, cnt, lim - 1]]; If[(test === Right || test === All) && lim ≥ 0, newNode = CreateDataStructure["BinaryTree", cnt["Increment"]]; node["SetRight", newNode]; InsertRandom[newNode, cnt, lim - 1]]; node ]

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

Wolfram Language code: SeedRandom[ 14]

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

Wolfram Language code: tree = InsertRandom[CreateDataStructure["BinaryTree", 0], CreateDataStructure["Counter", 1], 7]; tree["Visualization"]

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

Wolfram Language code: LowestCommonAncestor[tree_, left_Integer, right_Integer] := Which[ tree["NullQ"], tree, tree["Data"] === left, tree, tree["Data"] === right, tree, True, Module[{sleft, sright}, sleft = LowestCommonAncestor[tree["Left"], left, right]; sright = LowestCommonAncestor[tree["Right"], left, right]; Which[ sleft["NullQ"], sright, sright["NullQ"], sleft, True, tree ] ] ]

最下位共通項を求める：

Wolfram Language code: LowestCommonAncestor[tree, 15, 20]["Data"]

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

Wolfram Language code: LowestCommonAncestor[tree, 15, 20]["Visualization"]

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

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

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

Wolfram Language code: SymmetricTreeQ[tree_] := SymmetricTreeQ[tree["Left"], tree["Right"]] SymmetricTreeQ[x_, y_] := Which[ x["NullQ"] && y["NullQ"], True, x["NullQ"] || y["NullQ"], False, True, x["Data"] == y["Data"] && SymmetricTreeQ[x["Left"], y["Right"]] && SymmetricTreeQ[x["Right"], y["Left"]] ]

対称ではない木：

Wolfram Language code: tree = CreateDataStructure["BinaryTree", 1 -> {2 -> {5, Null}, 8}];tree["Visualization"]

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

Wolfram Language code: SymmetricTreeQ[tree]

対称である木：

Wolfram Language code: tree = CreateDataStructure["BinaryTree", 1 -> {2 -> {5, Null}, 2 -> {Null, 5}}]; tree["Visualization"]

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

Wolfram Language code: SymmetricTreeQ[tree]

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

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

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

Wolfram Language code: BinaryTreeDiameter[tree_] := Module[{diameter}, diameter = CreateDataStructure["Value", 1]; BinaryTreeDepth[diameter, tree]; diameter["Get"] - 1 ] BinaryTreeDepth[diameter_, tree_] := Module[{left, right}, If[tree["NullQ"], Return[0]]; left = BinaryTreeDepth[diameter, tree["Left"]]; right = BinaryTreeDepth[diameter, tree["Right"]]; diameter["Set", Max[diameter["Get"], left + right + 1]]; Max[left, right] + 1 ]

サンプルの木：

Wolfram Language code: tree = CreateDataStructure["BinaryTree", 1 -> {2 -> {5, Null}, 2 -> {Null, 5}}]; tree["Visualization"]

直径を計算する：

Wolfram Language code: BinaryTreeDiameter[tree]

別のサンプルの木：

Wolfram Language code: tree = CreateDataStructure["BinaryTree", 1 -> {2 -> {5 -> {7 -> {8, Null}, Null}, Null}, 2 -> {Null, 5}}]; tree["Visualization"]

直径を計算する：

Wolfram Language code: BinaryTreeDiameter[tree]

考えられる問題  (2)

空ノード  (1)

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

Wolfram Language code: ds = CreateDataStructure["BinaryTree", 10]

右の子を抽出する：

Wolfram Language code: rChild = ds["Right"]

これは空ノードである：

Wolfram Language code: rChild["NullQ"]

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

Wolfram Language code: rChild["Data"]

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

Wolfram Language code: InputForm[ rChild]
Wolfram Language code: DataStructure["BinaryTree", {"Data" -> Null}]

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

Wolfram Language code: CreateDataStructure["BinaryTree", Null]["NullQ"]
Wolfram Language code: CreateDataStructure["BinaryTree"]["NullQ"]

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

有効な木  (1)

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

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

Wolfram Language code: ds = CreateDataStructure["BinaryTree", 10]

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

Wolfram Language code: ds1 = CreateDataStructure["BinaryTree", 20]; ds["SetRight", ds1]; ds["Visualization"]

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

Wolfram Language code: ds1["SetRight", ds];

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

Wolfram Language code: ds["ValidQ"]

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

Wolfram Language code: ds//Normal

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