通常の AVL ツリー関数に加えて、AVL ツリーの任意の 2 つの数値間の最小ギャップを返す関数を追加する必要があるというデータ構造の宿題があります (AVL のノードは実際には数値を表します)。
AVL ツリーに (ノードとして) 1 5 12 20 23 21 という数字があるとします。この関数は、任意の 2 つの数字間の最小ギャップを返す必要があります。この状況では、|20-21| である "1" を返す必要があります。または|21-20|。
O（1）で行う必要があります。
それについてたくさん考えようとしましたが、トリックがあることは知っていますが、それを見つけることができませんでした.私はこれに何時間も費やしました.
最大ギャップを見つけるという別のタスクがありましたが、これは簡単で、最小数と最大数の差です。
データ構造を拡張する必要があります。そうしないと、ツリーを構成する数値間の最小ギャップの O(1) 検索を取得できません。
挿入/削除/検索機能の時間の複雑さを増やさないようにするための追加の制約があり、スペースの複雑さも増したくないと思います。
左部分木rLと右部分木rRを持つ汎用ノードrを考えてみましょう。以下の間の最小値として定義されたノードr追加番号rxの情報を拡張します。
(リーフノードの場合、前の条件がどれも有効でない場合は未定義)
さらに、挿入/削除を高速化するために、各内部ノードにその左端と右端のリーフ ノードへの参照を追加する必要があります。
これらの追加でそれを見ることができます：
ツリーの最小ギャップはルート ノードのx値です。より具体的には、各サブツリーのサブツリー要素のみの最小ギャップは、サブツリー ルートのx値です。
このステートメントの証明は、再帰によって行うことができます。ノードrをルートとし、左部分木rLと右部分木rRを持つ木を考えてみましょう。帰納的仮説は、rLおよびrR x値の根は、サブツリーのノード値間の最小ギャップの値であるというものです。並べ替えられた値のリストで隣接する値を持つノードのペアのみを考慮して、最小のギャップを見つけることができることは明らかです。rLのノードによって格納された値によって形成されたペアは、 rLルートx値に最小のギャップを持ちます。右のサブツリーを考慮すると、同じことが当てはまります。与えられた ( rLのノードの任意の値) < Lルート ノードの値 < ( rR内のノードの任意の値) の場合、考慮されない隣接する値のペアは 2 つだけです。
値が大きい rLノードは、AVL ツリー プロパティによる右端のリーフであり、値が小さいrRノードは左端のリーフです。4 つの値 (rL ルート x 値、rR ルート x 値、(r - rL ルート) ギャップ、(r - rR ルート) ギャップ) 間の最小値をrx値に割り当てることは、連続するノード値間のより小さいギャップを割り当てることと同じです。ツリー全体では、これはノード値の可能なペア間のギャップが小さいことに相当します。サブツリーの 1 つまたは 2 つが空である場合は、些細なことです。1 つまたは 3 つのノードのみで構成されるツリーの基本ケースでは、ツリー ルートの x 値がギャップの最小値であることは簡単にわかります。