Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2135-8c11ca48
この記事にトラックバックする(FC2ブログユーザー)

UVa 12347 - Binary Search Tree (この記事を編集する[管理者用])

Source

ACM-ICPC Asia Phuket Regional Semilive (2011-11-06)
UVa 12347

問題概要

2分探索木をpre-orderで辿った配列が与えられる.
post-orderで辿った配列を求める問題.
2分探索木は,2分木で各ノードに値が付けられており,自分の左の子の木には自分より小さい値しかなく,自分の右の木には自分より大きい値しかない.
与えられる配列数 (ノードの数) は10000以下.

解法

最初の値を見てやって,それが値の値なので,一番最後に配列に加える.
残りの部分は,自分より小さいのが並んで,その後自分より大きいのが並ぶ.
それぞれの区間で,左の木,右の木ができているので,再帰的に同じ処理を行う.
どこで分割されるかは2分探索できて,最悪でもO(n log n)程度.
いろんなやり方があると思う.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2135-8c11ca48
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。