1

Weissによるデータ構造と分析のAVL tresを読んでいます

バランス条件の 1 つは、すべてのノードが同じ高さの左右のサブツリーを持つ必要があることを主張します。空のサブツリーの高さが (通常どおり) -1 に定義されている場合、((2 の k 乗) - 1) ノードの完全にバランスの取れたツリーのみがこの基準を満たします。したがって、これにより深さの小さいツリーが保証されますが、バランス条件が硬すぎて役に立たないため、緩和する必要があります。

例を挙げて、上記のテキストを理解するための助けを求めてください。2. 「これによりツリーの深さが浅くなることは保証されますが、バランス条件が硬すぎて役に立たないため、緩和する必要があります」とはどういう意味ですか?

ありがとう！

4

1 に答える 1

1

ここで説明するように、完全にバランスの取れたツリーには、任意のノードの両側に同じ数のノードがあります。これを満たすことができるツリーの合計ノード数は次のとおりです。

1: *

3: *
  / \
 *   *

7:  *
   / \
  *   *
 / \ / \
 * * * *

等

数学的には、これはツリー内のノードの数が2 k -1であることを意味します。ここkで、は整数です。

「深さが小さい」とは、この形式のツリーが、指定された深さに対して可能な限り多くのノードを持つことを意味します。ノードを1つ追加すると、深さが増す必要があります。

于 2011-08-31T11:52:08.830 に答える