2

O(n)時間で配列をデカルトツリーに変換する方法を知っています

  1. http://en.wikipedia.org/wiki/Cartesian_tree#Efficient_constructionおよび
  2. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#RMQから LCA へ

ただし、少なくともデカルト ツリーのすべてのノードに左右のポインターを関連付ける必要があるため、必要なメモリ量が多すぎます (定数)。

これらの定数を（うまくいけば1に）減らすために行われた作業に私をリンクできますか？

4

3 に答える 3

2

デカルト ツリー ノードに関連付けられた左右のポインターを保持する必要はありません。各ノードの親を保持するだけでよく、デカルト ツリーの定義によって (配列 A[0, N - 1] のデカルト ツリーは、ルートが A の最小要素であるバイナリ ツリー C(A) であり、ラベルが付けられていますこの最小値の位置 i を持つ. 根の左の子は A[0, i - 1] のデカルトツリーである i > 0 の場合, さもなければ子は存在しない. 右の子は A[i + 1, について同様に定義される. N - 1].)、この配列をトラバースするだけで、ノードの親がノード自体よりも低いインデックスを持っている場合、ノードはその親の正しい息子になり、ノードの親がより高いインデックスを持っている場合も同様ですノードはその親の息子のままになります。

お役に立てれば。

于 2014-06-13T08:50:14.487 に答える