FHQ-Treap の学習ノート
FHQ-Treap の学習ノート
Treap は Tree と Heap を組み合わせたデータ構造です。
Treap は弱いバランスの取れた二分探索木であり、カーネルツリーとして見なせます。各ノードには (Key, Value) という2つの値を持ち、Key は二分探索木の性質を満たし、Value はヒープの性質を満たします（通常は最小ヒープ）。Key は実際の情報であり、Value はランダムな値で、木の高さが ...
6月10日 16:59 投稿
ソート済み配列を平衡二分探索木に変換する方法
二分探索木の中間順走査は昇順シーケンスを生成します。問題で与えられた配列は昇順でソートされているため、この配列は二分探索木の中間順走査シーケンスであることが保証されます。
1. 二分探索木の中間順走査が与えられた場合、二分探索木を一意に決定できるか？
答えは否定的です。もし二分探索木の高さバランスを要求しない場合、任意の数字を根ノードとして選択で ...
6月8日 21:28 投稿