二分木についていくつか質問があります。
ウィキペディアでは、「完全な二分木とは、最終レベルを除くすべてのレベルが完全に埋められ、すべてのノードが可能な限り左にある二分木である」場合に二分木が完成したと述べています。最後の「できるだけ左に」という節はどういう意味ですか?
整形式のバイナリ ツリーは、(1) 空である場合、または (2) 左右の子の高さがバランスが取れていて、左のツリーの高さが二分木がバランスが取れているかどうかを判断する方法から取得した正しい木 、これは正しいですか、それとも 1 値に「ジッター」がありますか? リンクした回答を読んで、右の木と左の木の高さの間に4倍の違いがある可能性があることを読みました
完全で高さのバランスが取れた定義は、バイナリ ツリーまたは他のツリーにのみ適用されますか?
完全で高さのバランスが取れた定義は、バイナリ ツリーまたは他のツリーにのみ適用されますか?
簡単な答え: はい、任意の n 分木に拡張できます。
ウィキペディアの定義の参照に従って、 このページにたどり着きました。定義はそこから取られましたが、変更されました:
定義:最も深いレベルを除くすべてのレベルが完全に埋められているバイナリ ツリー。深さ n (ツリーの高さ) では、すべてのノードをできるだけ左に配置する必要があります。
以下のメモに続きますが、
完全な二分木には、深さ k < n ごとに 2k ノードがあり、全体で 2n と 2^(n+1) - 1 ノードの間にあります。
場合によっては、便宜上 (何かに役立つ) 定義が異なることがあります。そのパッセージは、私が理解しているように、リーフノードが最初に最も深いレベルの左側を埋める (つまり、左から右に埋める) 必要があるバリエーションである可能性があります。私が通常見つけた定義は、まさに上記のとおりですが、その一節はありません。
通常、高さのバランスの取れたツリーの定義は、あなたが説明したものです。言い換えると：
すべてのノードについて、その 2 つのサブツリーの高さの差が最大で 1 である場合にのみ、ツリーはバランスが取れています。
その定義はhereから取得されました。繰り返しになりますが、特定の目的に役立つように定義がより柔軟になることがあります。たとえば、AVL ツリーの定義は次のように述べています。
AVL ツリーでは、任意のノードの 2 つの子サブツリーの高さの差は最大で 1 です。
それでも、任意のノードの 2 つの子サブツリーの差が最大で 2 の場合にツリーの高さのバランスが取れていると見なされるように、アルゴリズムを書き直さなければならなかったことを覚えています。指定した定義は再帰的であることに注意してください。これはバイナリでは非常に一般的です。木。
n子を持つ) に適用できます。