バランス二分探索木は、私は2つの質問がある

Question

サブツリー：

ほぼバランスBSTとほぼ完全なバイナリツリーの違いは何ですか

1. 。たとえ前者の定義が明確であっても、私たちは区別することができますが、関連記事を得ることはできません。

   最大（サイズ（root.left）、サイズ（root.right））< = 3 * nの/：私のクラスで私は次のようにバランスさせる条件について教えられた

2. 今日、 4 ------------（式1）。
   したがって、H（n）=上記のプロパティに続くn個のノードのツリーの高さ< = 1 + H（3 * n/4）。
   再帰的なステップを続けると、lognの境界が得られます。

   私の質問は、このタイプのBSTですか？例えば、AVLツリーの場合、左右の子の高さの差が1であること、またはより一般的な結果であり、先に述べた式1を減らして結果を証明できることですAVLツリーの場合も同様ですか？すなわち、任意の平衡BSTは、兄弟の高さの差が最大1であることになるだろうか？
   AVLと異なる場合は、この新しい種類のツリーで挿入操作と削除操作をどのように管理しますか？

EDIT：3 * n/4だけの理由も説明できますか？
私は3n/5より3n/4以下のものを取ってH（3n/4）を取ると、H（n）< = 1 + H 5）は、3n/5と2n/5の比率が2未満であるH（2n/5）よりも必然的に少なくなりません。ノード数が2の場合、高さは1増加します。 H（n）< = 1 + H（3n/5）と書くのは、H（3n/5）の代わりにH（2n/5）でもかまいません。

Answer 1

1. ほぼ完全 BSTは、最後の1を除いて、すべてのレベルが満たされているBSTです。定義はここではうんざりしています（このプロパティはといっても、と呼ばれます）。これについてはwikipediaを参照してください。
   平衡は、すべての（ほぼ）完全なBSTが平衡していますが、すべての平衡BSTが完全ではありません。ウィキペディアの記事では、その定義もあります。私の世界では、O（log n）の運用コストにつながる場合、BSTはバランスがとれています。

2. 各サブツリーは、例えばイプシロン= 3/4あるいはイプシロン= 0.999ためのイプシロン< 1（最もイプシロン* Nノードに有する場合、例えば、一方が言うことができ、BSTは、バランスが取れている - あります実際にはは全くバランスが取れていません）。そのようなBSTの高さはおおよそlog_ {1 /ε} = log_2n /（log_2ε）= O（logn）であるが、1 /（-log_2.99）= 99.5はa巨大な定数。両方のサブツリーがおおよそ同じサイズを持つ通常のイプシロン= 1/2の割合でそれを証明しようとすることができます。

この3/4を使用する一般的なBSTについてはわかりません。一般的なBSTは、たとえばRed-Black-Trees,Splay-Trees、またはハードディスクの場合はB-Treesのファミリです。たとえば、左右のサブツリーのノード数を表す2つの整数で各ノードを補うことによって、操作を実装できます。ソートを挿入または削除するときは、ルートからリーフ（またはそれ以上）まで歩き回ったときに番号を更新し、条件が検証されると回転を行います。