WOLFRAM

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

"AVLTree" (データ構造)

"AVLTree"

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

詳細

  • 二分探索木は，素早く挿入演算が行えるようにソートされた形式でデータを保存する．平衡二分探索木は，すべての枝の高さが平衡であるので，任意の挿入や削除の演算を効率的にする．
  • CreateDataStructure[ "AVLTree"]新しい空の"AVLTree"を作成する
    CreateDataStructure["AVLTree",v{l,r}]指定の初期値 v と指定の左と右の子を持つ新しい"AVLTree"を作成する
    CreateDataStructure["AVLTree",tree,p]指定の木と順序関数 p を持つ新しい"AVLTree"を作成する
    Typed[x,"AVLTree"]x に"AVLTree"型を与える
  • "AVLTree"型のデータ構造には，以下の演算が使える．
  • ds["BreadthFirstScan",f]ds の幅優先探索を行い，各ノードのデータを f に渡すtime: O(n)
    ds["Copy"]ds のコピーを返すtime: O(n)
    ds["Delete",x]delete x を ds から削除するtime: O(log n)
    ds["DeleteAll"]ds からすべての要素を削除するtime: O(n)
    ds["DropMax"]ds の最大要素を取り除き，それを返すtime: O(log n)
    ds["DropMin"]ds の最小要素を取り除き，それを返すtime: O(log n)
    ds["Elements"]ds の要素のリストを返すtime: O(n)
    ds["EmptyQ"]ds がノードを持たない場合はTruetime: O(1)
    ds["FreeQ",x]ds が x を含まない場合はTruetime: O(log n)
    ds["InOrderScan",f]ds の間順探索を行い，各ノードのデータを f に渡すtime: O(n)
    ds["Insert",x]x を ds に挿入するtime: O(log n)
    ds["Length"]ds のノードの数time: O(1)
    ds["Max"]ds の最大要素を返すtime: O(log n)
    ds["MemberQ",x]ds が x を含む場合はTruetime: O(log n)
    ds["Min"]ds の最小要素を返すtime: O(log n)
    ds["PostOrderScan",f]ds の後順探索を行い，各ノードのデータを f に渡すtime: O(n)
    ds["PreOrderScan",f]ds の前順探索を行い，各ノードのデータを f に渡す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つの要素の順序は，Sortの順序関数によって与えられる解釈に従い，順序関数 p によって決定される．デフォルトの順序関数は，Orderである．
  • "AVLTree"は，各部分木の高さが決して2以上異なることがないように，平衡特性を維持する．
  • 最初の木の指定がNullである場合には，空の"AVLTree"が作成される．

例題

すべて開く すべて閉じる

例  (1)

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

Wolfram Language code: ds = CreateDataStructure["AVLTree"]

複数の値を挿入する：

Wolfram Language code: ds["Insert", 10]; ds["Insert", 15]; ds["Insert", 5];

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

Wolfram Language code: ds["Visualization"]

スコープ  (4)

情報  (1)

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

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

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

Wolfram Language code: Information[ds]

平衡  (1)

"AVLTree"は，各部分木の高さの差が1より大きくならないように平衡を保つ：

Wolfram Language code: ds = CreateDataStructure["AVLTree"]; ds["Insert", 0]; ds["Insert", 10]; ds["Visualization"]

平衡特性を崩す変更を行うと，再度平衡になるように調整される：

Wolfram Language code: ds["Insert", 15]; ds["Visualization"]

これで右に挿入しても再度平衡を取る必要はない：

Wolfram Language code: ds["Insert", 20]; ds["Visualization"]

左から削除すると，再度平衡にする必要がある：

Wolfram Language code: ds["Remove", 0]; ds["Visualization"]

順序  (1)

新しい木を作成し，30個の乱数を挿入する：

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

木に対して間順探索が行われる．ソートされるので，この例が示すように，ソートされた順に要素を訪れる：

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

順序関数  (1)

カスタム順序関数で空の木を作成する：

Wolfram Language code: ds = CreateDataStructure["AVLTree", Null, Order[First[#1], First[#2]]&];

データを挿入する：

Wolfram Language code: data = Table[{RandomInteger[1000], f[i]}, {i, 10}]; Scan[ds["Insert", #]&, data];

木の要素：

Wolfram Language code: ds["Elements"]

最大要素を削除して返す：

Wolfram Language code: ds["DropMax"]

最大要素は削除された：

Wolfram Language code: ds["Elements"]