の生成 $n^{th}$ 完全な二分木 $N$ ラベル付きの葉

2
István Zachar 2019-02-06 09:18.

個別の完全な二分木を段階的に生成するアルゴリズムを探しています $N$ユニークな葉。つまり、生成できるアルゴリズムが必要です。$n^{th}$ すべてを生成せずに別個のツリー $n-1$前の木。すべてのツリーを事前に生成することは、特定の以上では事実上不可能Nです。

そのと完全な二分木 $N$ ラベル付けされた葉は、のバイナリグループ化と同等です。 $N$ペアにグループ化された一意の要素。がある$C_{N-1}$異なる完全な二分木またはN葉のグループ、ここで$C_n$ それは $n^{th}$カタラン数。ために$N = 4$、 がある $C_3 = 5$木。これらは、内部ノードにラベルが付けられています$5..7$ 同等のグループ化:

ために $N = 5$

(1 (2 (3 (4 5))))
(1 (2 ((3 4) 5)))
(1 ((2 3) (4 5)))
(1 ((2 (3 4)) 5))
(1 (((2 3) 4) 5))
((1 2) (3 (4 5)))
((1 2) ((3 4) 5))
((1 (2 3)) (4 5))
((1 (2 (3 4))) 5)
((1 ((2 3) 4)) 5)
(((1 2) 3) (4 5))
(((1 2) (3 4)) 5)
(((1 (2 3)) 4) 5)
((((1 2) 3) 4) 5)

この問題を解決する3つの方法があります(最終的には同等です)。

  1. 次の別個の(非同型)ツリーを段階的に直接生成できる単純なアルゴリズムがあります。
  2. ツリーからの全単射エンコーディングがあります $T_i$ シーケンスする $S_i$ そのような生成 $S_{i+1}$ (ツリーへのデコード $T_{i+1}$)簡単に実行できます。
  3. 理想的なケースでは、の単純な全単射があります $C_{N-1}$ の連続間隔に木 $C_{N-1}$ 自然数(優先的に $(1..C_{N-1})$)を生成するように $i^{th}$ ツリーは整数からデコードするのと同じくらい簡単です $i$

二分木を二分木を二分木に一意のシーケンス(プリューファー列など)にエンコードするアルゴリズムはたくさんありますが、問題は、有効なシーケンスをエンコードしない多くの失敗したシーケンスなしで、次のツリーにデコードできる次のシーケンスを生成する方法です。上記の説明のツリーであり、すでにアクセスされたツリーをエンコードしません。

1 answers

1
Mike Earnest 2019-02-06 10:01.

文字列を完全に括弧で囲む方法の数 $n$ 手紙、 $C_{n-1}$、次の繰り返しに従います。 $$ C_{n-1} = \sum_{i=1}^{n-1}C_{i-1}C_{n-i-1} $$ これを確認するには、括弧内の2つの「最も浅い」グループについて考えてみます。つまり、左端(と右端を無視して、左端に)一致する括弧を見てください(。これは最初のものを囲みます$i$ 文字列内の文字。これは、 $C_{i-1}$ 方法、後者は $n-i$ 文字は括弧で囲むことができます $C_{n-i-1}$方法。たとえば、$n=5$$*$ すべてのブレークポイントを示しています。

(1 * (2 (3 (4 5)))) C(0) * C(4) strings where the break point
(1 * (2 ((3 4) 5))) is after i=1
(1 * ((2 3) (4 5)))
(1 * ((2 (3 4)) 5))
(1 * (((2 3) 4) 5))

((1 2) * (3 (4 5))) C(1) * C(2) strings where the break point
((1 2) * ((3 4) 5)) is after i=2

((1 (2 3)) * (4 5)) C(2) * C(1) strings where the break point
(((1 2) 3) * (4 5)) is after i=3

((1 (2 (3 4))) * 5) C(4) * C(0) strings where the break point
((1 ((2 3) 4)) * 5) is after i=4
(((1 2) (3 4)) * 5)
(((1 (2 3)) 4) * 5)
((((1 2) 3) 4) * 5)

この漸化式により、最初からすばやく計算可能な全単射が得られます $C_{n-1}$二分木への非負の整数。あなたは整数を与えられます$k$ そのために $0\le k\le C_{n-1}-1$。部分和を計算する $$ \sum_{i=1}^{s-1} C_{i-1}C_{n-i-1} $$ 最大数を見つけるために $s\ge 1$ その部分和はせいぜい $k$。次に、(1 2 3 ... n)次のように番号のリストに括弧を挿入します。

((1 2 ... s) (s+1 s+2 ... n))

場合 $s=1$、あなたは周りの括弧を省略することができ(1)、同様にするとき$s=n-1$周り(n)

次に、 $$e=k - \Big(\sum_{i=1}^{s-1}C_{i-1}C_{n-i-1}\Big),$$そしてせるエンド{ALIGN} \、\ \\ \ {}整列K_1&=始める電子\ PMOD {C_ {S-1}} rfloorをK_2&= \ lfloor E / C_ {S-1} 、あなたが持っているだろう$0\le k_1\le C_{s-1}-1$ そして $0\le k_2\le C_{n-s-1}-1$、および全単射を再帰的に適用できます $k_1$リストに(1 2 ... s)そしてのために$k_2$リストに(s+1 s+2 ... n)

編集:私が修正したばかりの全単射に「バグ」がありました。あなたはそれが機能することをテストすることができますhttps://repl.it/@mearnest/Catalan-Bijection?language=python3&folderId=

Edit2:別のオフバイワンエラーを修正しました。

Related questions

MORE COOL STUFF

「水曜日」シーズン1の中心には大きなミステリーがあります

「水曜日」シーズン1の中心には大きなミステリーがあります

Netflixの「水曜日」は、典型的な10代のドラマ以上のものであり、実際、シーズン1にはその中心に大きなミステリーがあります.

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ケイト・ミドルトンは、州の夕食会と州の訪問中にカミラ・パーカー・ボウルズからスポットライトを奪いたくなかった、と専門家は言う.

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンが、オリビア・ワイルドが彼女とハリー・スタイルズとの間の「難しい」が「非常に友好的」な分割を恒久的にすることを望んでいる理由を見つけてください.

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする 

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする 

エリザベス女王の死後、ケイト・ミドルトンが舞台裏で「非常に困難な時期」を過ごしていたと伝えられている理由を調べてください.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

ラーム・エマニュエルがシカゴ警察の警視を解雇し、身を守る

ラーム・エマニュエルがシカゴ警察の警視を解雇し、身を守る

シカゴ市長のラーム・エマニュエルは、シカゴの警察官による17歳のラカン・マクドナルドの銃撃の失敗した取り扱いに続いて、市の警視官、ギャリーF.マッカーシーを解雇しました。

ダグ・マローネの理想的な食事は、ボローニャのサンドイッチです。

ダグ・マローネの理想的な食事は、ボローニャのサンドイッチです。

写真:ローガンボウルズ/ゲッティイメージズジャイアンツがベンマカドゥーを解雇したので、他の誰かがジムトムスラの精神的後継者でなければなりません。季節だった。ジャガーズのダグ・マローネ監督は、孤独なボローニャサンドイッチに親しみを持っていることを考えると、すでにその役割を担う有力な候補者のようです。

人々がやめる最も一般的な時間、およびプッシュスルーする方法

人々がやめる最も一般的な時間、およびプッシュスルーする方法

時には、それが副次的なプロジェクト、仕事、人間関係、または人生の他の部分であるかどうかにかかわらず、辞めることが最良の選択肢です。しかし、何かを完了するためのリソースがないため、物事が困難になったとき、タイミングが私たちに必要なように「感じ」させたときにも、私たちは辞めます。

黒人女性、あなたの内訳へようこそ

黒人女性、あなたの内訳へようこそ

著者のベニルデ・リトルは、母親の死後のうつ病との戦いを新しい回想録「Welcome toMyBreakdown」で記録しています。チェスター・トイの作家ベニルデ・リトルは、黒人女性にそれが大丈夫だと知ってもらいたいと思っています。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

ホームオフィスのセットアップ術を極めよう!AppExert の開発者は、家族全員が一緒にいる場合でも、在宅勤務の技術を習得しています。祖父や曽祖父が共同家族で暮らしていた頃の記憶がよみがえりました。

2022 年、私たちのデジタル ライフはどこで終わり、「リアル ライフ」はどこから始まるのでしょうか?

20 年前のタイムトラベラーでさえ、日常生活におけるデジタルおよびインターネットベースのサービスの重要性に驚くことでしょう。MySpace、eBay、Napster などのプラットフォームは、高速化に焦点を合わせた世界がどのようなものになるかを示してくれました。

ニューロマーケティングの秘密科学

ニューロマーケティングの秘密科学

マーケティング担当者が人間の欲望を操作するために使用する、最先端の (気味が悪いと言う人もいます) メソッドを探ります。カートをいっぱいにして 3 桁の領収書を持って店を出る前に、ほんの数点の商品を買いに行ったことはありませんか? あなたは一人じゃない。

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

私たちが住んでいる世界を確実に理解するには、データが必要です。ただし、空間参照がない場合、このデータは地理的コンテキストがないと役に立たなくなる可能性があります。

Language