Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                

2-3-4 treeとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 2-3-4 treeの意味・解説 

2-3-4木

(2-3-4 tree から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/10/07 06:46 UTC 版)

Jump to navigation Jump to search

2-3-4木(2-3-4き、: 2-3-4 tree)または2-4木は計算機科学の用語であり、4次のB木: B-tree)と同じである。

一般に2-3-4木はB木のように辞書として使うことができる平衡木の一種である。探索、挿入、削除をO(log n)で行うことができる。ここでnは木の要素数である。

2-3-4木は木の操作において多くの特別なケースが存在するので大半のプログラミング言語において比較的実装が難しい。赤黒木(red-black tree)の方が実装が簡単で代わりに用いられる傾向がある。

背景

2-3-4木は要素と呼ばれる単一の項目としてデータを格納する。 それら要素はノードにまとめられる。ノードは以下のうちどれかである。

  • 2-nodeの場合は、1つの要素と2つの子をもつ。
  • 3-nodeの場合は、2つの要素と3つの子をもつ。
  • 4-nodeの場合は、3つの要素と4つの子をもつ。
2-node
3-node
4-node

それぞれのは部分2-3-4木である (空もありうる)。ノードは親を持たないノードであり、全ての他のノードはそこから到達できるので、探索の開始点になる。は子を持たないノードである。

B木同様、2-3-4木も順序つきである。そのためそれぞれの要素は、左の要素および左の部分木と比較して等しいかより大きくなければならない。従って、それぞれの子は左と右の要素で示される閉区間となる。

2-3-4木を解析するときは、内部ノードと外部ノードを明確に区別しなければならない。内部ノードとは上記の例において木の中にあり、ab、そしてcを含んでいるノードである。外部ノードとは木の中にないノードであり、次のノードの位置として示されているものである。それらは上記の例では、pqr、そしてsを含む。2-3-4木は次の二つの性質を維持しなければならず、他の平衡木と明確に区別される。

  • 各内部ノードは4つより多い子ノードを持たない
  • すべての外部ノードは同じ深さを持たなければならない (これは、その木の中の任意の外部ノードへ到達するために、根ノードから同じ個数のノードを探索すればよい事を意味する)

2-3-4木は赤黒木のisometry、すなわち等価なデータ構造である。言い換えると、任意の2-3-4木に対して,それと同じ順序でデータ要素を持つ赤黒木が少なくとも一つ存在する。2-3-4木に対する挿入および削除は、赤黒木における色替え(color-flipping)および回転(rotation)と等価である。このことは、赤黒木が平衡する原理が複雑であるため、赤黒木の背後にあるロジックを理解する上で重要である。

挿入

削除

赤黒木への視覚的な変換

2-3-4木と等価の赤黒木

2-3-4木は、少なくとも一種類以上の赤黒木に変換可能である。具体的には3つの要素を持つノードの場合は真ん中の値を要素にもつ黒ノードを作成し、それ以外の要素を作成したノードの子ノードとして生成し色を赤とする。2つの要素を持つノードの場合は、どちらかの要素を持つノードを作成し色を黒とし、もう片方の要素はそのノードの子ノードとし色を赤とする。最後に葉以外の全てのノードが子どもを2つ持つように黒の葉を付与することで赤黒木を作成できる。このとき赤黒木の定義は自動的に満たされていることとなる。

また2-3-4木における挿入および削除の各操作は、赤黒木におけるカラー・フリッピングおよび回転の各操作にあたる。

2-3-4木の問題

参考

外部リンク


「2-3-4 tree」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「2-3-4 tree」の関連用語

2-3-4 treeのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



2-3-4 treeのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの2-3-4木 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2024 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2024 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2024 GRAS Group, Inc.RSS