1

二分木のプロパティを理解しようとしています。しかし、私は1つのことについて確信が持てません:

デフ。バイナリ ツリーの次のように述べています。

  1. 二分木は、ノードごとに、左側のサブツリーの内部ノードの数と右側のサブツリーの内部ノードの数の差が最大 1 である場合、バランスが取れています。

  2. 二分木は、いずれか 2 つが差分を残す場合にバランスが取れています。深さの最大値は 1 です。

この2つの定義があるかどうかを尋ねています。は同等です。つまり、Def は同等です。1 Defを満たします。2とその逆？...私にはそうだと思われます...しかし、このプロパティの(非)同等性を例で正確に説明できるのは誰ですか?

ありがとう、パトリック

4

1 に答える 1

8

いいえ、この 2 つは同等ではありません。

    3
   / \
  2   7
 /   / \
1   5   8
   / \   \
  4   6   9

はプロパティ 2 を満たしますが、プロパティ 1 を満たさないツリーです。

ただし、プロパティ 1 はプロパティ 2 を意味します。

命題:内部ノードを持つプロパティ 1 に従ってバランスが取れている二分木ではn、すべての葉は深さ

  • kもしもn = 2^k - 1
  • kまたはk+1if 2^k <= n < 2^(k+1)-1、および深さに葉がありますk+1。

証明: (内部ノード数の帰納法による)

の場合n = 1 = 2^1-1、深さ 1 に 1 つまたは 2 つのリーフがあります (ルートは深さ 0 にあります)。

の場合n = 2、1 つのサブツリーには 1 つの内部ノードがあり、そのサブツリーのすべての葉は深さ 2 にあり、もう 1 つのサブツリーは空であるか深さ 1 の葉です。

内部ノードn >= 2を持つプロパティ 1 に従ってバランスが取れているバイナリ ツリーを考えてみましょう。n+1

nが偶数の場合、n = 2*m両方のサブツリーにm内部ノードが必要であり、深さのプロパティは帰納法の仮説によって保持されます。

n = 2*m+1が奇数の場合、一方のサブツリーにはm内部ノードがあり、もう一方にはm+1.

  1. の場合2^k <= m < 2^(k+1)-1、m内部ノードを持つサブツリーには深さ の葉があり、帰納仮説によるk+1深さの葉がある可能性があります。内側のノードを持つkツリーには、さらに葉があり、場合によっては(場合) depth にも葉があります。m+1k+1m+1 < 2^(k+1)-1k

  2. の場合m = 2^k - 1、m内部ノードを持つサブツリーには深さのみに葉がkあり、内部ノードを持つサブツリーには深さおよび場合によっては深m+1さに葉があります。k+1k

于 2013-02-14T19:19:46.843 に答える