algorithm - AVL ツリーが、ノード数が互いの Θ ではない子を持つことができることを証明する

Question

T を、左側のサブツリーが T _Lで、右側のサブツリーが T _Rである AVL ツリーとします。_{|T L} |としましょう。および |T _R | それぞれ、左と右のサブツリーのノード数になります。

|T R | |T _R | ≠ Θ(|T _R |) とその逆ですが、方法がわかりません。1 つのツリーが完全な AVL ツリーで、もう 1 つのツリーが最小の AVL ツリー (フィボナッチ ツリー) である場合と関係があると思いますが、そこから何をすべきかわかりません。

Answer 1

高さ h の AVL ツリーでは、ノード数は F _h+2 - 1 から 2 ^h - 1 の範囲です。この最初の量は Θ(φ ^h ) で、2 番目の量は Θ(2 ^h ) です。ここで、φ はゴールデンです。比、約 1.61。これは、左側のサブツリーのノード数が Θ(φ ^h ) で、右側のサブツリーが Θ(2 ^h ) である AVL ツリーを構築できることを意味します。つまり、左側のサブツリーは右側のサブツリーよりもノード数が漸近的に少ないことを意味します。次に、左右を逆にして、右のサブツリーが左のサブツリーの Θ になることもできないことを示すことができます。

お役に立てれば！