2つのAVLツリー間でk番目に大きい要素を検索するアルゴリズムを設計する

Question

これは先週の講義で挑戦された質問で、以来私はそれを検討してきました。 k番目に大きい要素の2つのAVLツリーを検索するアルゴリズムを作成するように求められました。 2つのツリーの各ノードには、その整数値とそれ自身を含むサブツリー内にある子の数の2つの情報が含まれています（リーフには1つの子があります）。アルゴリズムの複雑さはO（（logn）^ 2）よりも悪くはありません。

私はあるツリーの各ノードを他のツリーのすべてのノードと比較することを考えましたが、それはあまりにも遅いO（n）の複雑さです。

最初のステップとして

Answer 1

、BはAVL木の多くの要素があるかを決定する特定の上限という機能を設計してみましょう少ないときB：

count(node, b) 
    if node.key < b: 
     return node.left.size + 1 + count(node.right, b) 
    else 
     return count(node.left, b) 

ありますが、一つだけ再帰呼び出し各分岐においてノードの深さが増加する。したがって、この関数の複雑さはO（log（n））です。この機能も、各再帰呼び出しで増加node1については

kth(k, node1, tree2) 
    left = node1.left.size + count(tree2, node1.key) 
    if k < left: 
     return kth(k, node.left, node2.right 
    else if k == left: 
     return max(upperBound(tree2, node1.key), upperBound(node1.left, node1.key)) 
    else if k == left + 1: 
     return node1.key 
    else 
     return kth(k - node1.left.size - 1, tree2) 

ので、私たちは、それぞれが必要なO（ログをO（n個のログ）電話を持っている：

は、今、私たちはcountを使用して必要な機能を構築することができますn）count関数の呼び出しによる時間。稼働時間は、必要に応じてO（log²n）です。

この解決策を完了するには、サブツリー内の最大キーを返す関数upperBoundを設計する必要があります。これは、o（log n）時間で簡単に行うことができます。

Answer 2

k-th要素が最初のツリーにあるとします。ツリー内の位置をバイナリ検索することができます。固定位置pの場合、O(log n)の時間内にツリー内のp-th要素を見つけることができます（ルートから開始し、左のサブツリーのサイズに応じて左に行くことによって）。

ここでは、2番目のツリーでこの要素よりも小さい要素の数を見つける必要があります。 O(log n)時間に行うことができます。現在のノードの値に応じて、ルートから開始して左または右に移動します（また、右に行くときには、左のサブツリーのサイズを回答に追加します）。

2番目のツリーの指定された要素の数（この番号はsとしましょう）がわかっている場合、ツリーの結合の位置は正確にs + pです。

このアルゴリズムはO(log^2 n)時間で実行されます。

k番目の要素が最初のツリーにない場合は、2番目のツリーにある必要があります。したがって、一般的なケースでは、他のツリーでこの手順を繰り返して答えを得ます。