1

2-3-4 ツリーの高さは、ノードの挿入順序によって異なる場合があることがわかりました。

たとえば、1,2,3,4,5,6,7,8,9,10 は高さ 2 のツリーを生成します

この順序で挿入している間：

たとえば、1, 5, 10, 2, 3, 8, 9, 4, 7, 8 は高さ 1 のツリーを生成します

これは 2-3-4 ツリーの通常の特性ですか? その場合、ノードを順番に挿入すると、非常に不均衡なツリーが生成されます。2-3-4本の木はバランスの取れた木であるべきだと思いましたか?

ありがとう。

4

3 に答える 3

0

バランスの取れたツリーとは、通常、その高さが O(logn) であることを意味します。

有効な B ツリー (2-3-4 ツリーを含む) には次の制限があります。

  1. すべての非ルート ノードには少なくとも [m/2] 要素があります。

  2. すべての葉は同じ高さです。

この 2 つの制限により、有効な B ツリーの高さは O(logn) であることが証明されます。

于 2013-05-02T04:55:01.507 に答える
0

I observed that the height of a 2-3-4 tree can be different depending of the order of insertion of nodes.

The insertion algorithm for 2-3-4 trees splits 4-nodes "on the way" to the leaf node, since they cannot take another item. This allows insertion to be done in one pass and the tree remains balanced.

于 2014-09-03T15:54:39.923 に答える