12

B ツリーと 2-3-4 ツリーの違いは何ですか?

また、それぞれの最大高と最小高をどのように見つけますか?

4

2 に答える 2

24

...ウィキペディアへのリンク と引用:

「2-3-4 木は次数 4 の B 木です。」

A2-3-4 は B-treeです。
非葉、非ルート ノードの子の数が 2、3、または 4 であるため、2-3-4 ツリーと呼ばれ
ます。6 だった場合、3-4-5-6 ツリーと呼ばれていた可能性があります。 、または略して 3-6 ツリー。
子の最小数は最大数の半分であるため、通常は前者をスキップして次数mの B ツリーについて話すことができます。
B ツリーの順序は、ノードが持つことができる子の最大数として定義されます。
2-3-4 ツリーでは、これまで見てきたように、最大​​数は 4 です。

最悪の場合と最良の場合の高さは、B-trees の一般式で与えられます。

最良のケース: log m n. (すべてのノードがいっぱいです)
最悪の場合: log m/2 n. (すべてのノードは半分空です)

どこ

  • mはツリーの順序です。ノードが持つことができる子の最大数です。この場合は 4 です。
  • nはツリー内のエントリ数です

「Bツリーは任意の数の順序を持​​つことができます」 -はい、ただし、Bツリーの特定のサブクラスについては、その数を事前に修正します。蝶全般について話すのと、オオカバマダラについて話すようなものです。B ツリーは、蝶が昆虫のクラスであるように、データ構造のクラスです。オオカバマダラは、2-3-4 ツリーが B ツリーのサブクラスであるように、チョウのサブクラスです。

于 2010-04-05T21:33:44.227 に答える
-1

B ツリーが存在するようになった主な違いは、挿入時に必要なノード分割の数が 2 ～ 4 ツリー未満であることです。2-4 ツリーではカスケード分割と呼ばれる用語が時々見られますが、b ツリーではカスケード分割は存在しません。

于 2012-02-10T09:51:37.927 に答える