4

深さの各レベルのノードが左から右に番号付けされている完全な二分木を想像してください。

  • ノード 1 には子 2 と 3 があります。
  • ノード 2 には子 4 と 5 があります。
  • ノード 3 には子 6 と 7 があります。

等

深さ D には、2^D のノードがあり、番号は 2^D ... 2^(D+1)-1 です。

任意の深さの完全なツリーの深さ優先検索トラバーサルは決定論的です。

たとえば、深さ 4 のツリーは常にトラバースされます: 1,2,4,8,9,5,10,11,3,6,12,13,7,14,15。

数値のリストを、任意のツリーの DFS トラバーサルで分類される場所で並べ替える方法を探しています。

特に、2 つの数値を取り、どちらが DFS トラバーサルで最初に来るかを判断できる比較関数が必要です。

何か案は？

ある程度の最大ツリー サイズについて DFS トラバーサルを事前に計算することは、これを行う 1 つの方法ですが、その情報の計算と保存を必要としない数学的ソリューションを好みます。

4

5 に答える 5

1

@Abhishekの答えのC実装は次のとおりです。

//returns -1 if a before b; 0 if same; else 1
int treesort(unsigned int a,unsigned int b)
{
  int diff, swap=1, side=0;
  unsigned int ra, rb;
  if (a==b) return 0;  
  //ensure deeper node is always in b.
  if (b<a) { int t=a;a=b;b=t;swap=-1;}
  //treat 0 as before everything else
  if (a==0) return -1*swap;
  //clear all but the msb
  ra=base(a); rb=base(b);
  //move up to same level, tracking child side
  while (rb!=ra)  { side=b&1;rb/=2;b/=2; }
  //compare parents at same level
  diff = (b-rb)-(a-ra);
  //if same parent, answer depends on side.
  if (diff==0) diff = side;
  //restrict to [-1,1], be sure to handle swap
  return (diff>0?-1:1)*swap;
}

base最上位ビット以外をクリアする機能です。this questionからSir Slick の msb32()
int base(unsigned int x){return 1<<(msb32(x)-1);}を使用してテストしました。

于 2013-11-15T20:38:28.730 に答える
0

これが問題の数学的な解決策ですが、方程式の閉じた形式を取得できませんでした: -

合計ノード N のツリーでノード k の DFS インデックスを検索するには: -

DFS-order(k) = DFS-order((k-1)/2) + 2^(log(N+1) - log((k-1)/2) - 1)       if k is odd

DFS-order(k) = DFS-order(k/2) + 1             if k is even 

Base Case: DFS-order(1) = 0

上記の方程式の閉じた形式を見つけることができますが、これは高レベルの数学だと思います。

説明：-

奇数ノードの場合、最初に親のすべての左側のサブツリー ノードをトラバースし、新しいインデックスに 1 を加えます。左のサブツリーには、親を除くノードの親をルートとする完全なバイナリ ツリーの半分のノードがあることがわかっています。完全な BT の合計ノードは2^d - 2、ルートを除外しています。左のサブツリーにはその半分があります2^(d-1) - 1。d は親でのツリー ルートの深さです。ノード k をルートとするツリーの深さは ですTotal depth - log(k)。合計の深さはlog(N+1)です。したがって、左側のサブツリーのノード数は です2^(log(N+1) - log((k-1)/2) - 1) - 1。したがって、現在のノードに親からもう 1 つトラバーサルするために 1 を追加しますfinal sum = 2^(log(N+1) - log((k-1)/2) - 1)。これを親インデックスに追加して、現在のノード インデックスを取得しますDFS-order(k) = DFS-order((k-1)/2) + 2^(log(N+1) - log((k-1)/2) - 1)。

偶数ノードの場合、そのインデックスが親インデックス + 1 であることは自明です。

注:式は、O(log(k)) 時間でノード k のインデックスを見つけることができます。ログ関数はフロア演算子を使用して離散値を取得します。

于 2013-11-15T12:56:29.367 に答える