連結機/統合/当社では豊富な種類の木AVL

Question

そしてAVL木は、それぞれの要素から最初のツリーはその任意の要素からです。その中で最も効率的な方法を連結し一つのAVLすんで検索もなたものです。

Answer 1

ときを破棄し、入力：

1. 削除の右側の要素を左側のツリーで新しいルートノードで、左の子は左側のツリー、その右の子は、木:O(log n)
2. を判定および設定するためのそのノードのバランス係数O(log n)（仮）に違反した不変量のバランス係数が範囲外の{-1,0,1}
3. 回転させ、バランス因子に戻範囲：O(log n)の回転数:O(log n)

このように、全体の動作を行うことができO(log n).

編集：第二思いが容易である理由に回転以下のアルゴリズムです。でもその高速化:

1. 決定の高さの木:O(log n)
   この木は高(その他の場合は対称):
2. 削除の一番右に出現した位置の要素から left ツリー（回転、調整、計算が必要です。ましょう n する要素になります。O(log n)
3. 右側のツリー、ナビゲートできるノードがサブツリーは最大1の丈を超 left.ましょう r されるノードです。O(log n)

4. 交換するノードを新しいノード値はnというツ left や r.O(1)
   工事により、新しいノードは、AVL-バランスの取れたものであれば、そのサブツリーの丈を超1 r.

5. は増加その親会社のバランスします。O(1)

6. バランスを回復させる効果と同じように、後に挿入す.O(log n)

Answer 2

一の超簡単なソリューション(動作するな仮定の関係の樹）は、この:

1. い合うの木々を一つに統合配列（兼任の両方に対して繰り返し処理を実行しています。
2. の構築AVLツリーから配列の中の要素はルート申請、再帰的に左右半分.

両手順はO(n)の大きな課題であるとO(n)超空間です。

Answer 3

を読んだこの問題につき こちらの.あ meriton回答の場合正しいこの問題:

第三段階のアルゴリズム ナビゲーシ左に達するまでのノードがサブツリーと同じ高さにして左側のツリー.ことができない場合があり、反例画像）となっています。グ方法、上達するためのコツなどいこのステップで見るサブツリーとの高さ h または h+1 場所 h するのは左側のツリー

Answer 4

私はあなただけで一本の木（うまくいけば小さい）を歩くと、個別に他の木にそれの各要素を追加する必要がありますことを疑います。 AVLの挿入/削除の操作を一度にサブツリー全体を加える処理するように設計されていません。