データ構造の重みバイアス左翼木（WBLT）とは？重みの定義と具体例を徹底解説
重みバイアス左翼木（WBLT）とは
ここでは、左翼木（Leftist Tree）のもうひとつの変種である重みバイアス左翼木（Weight Biased Leftist Tree：WBLT）について解説します。通常の左翼木では、根から外部ノードまでの最短経路の長さを考慮しますが、WBLTでは代わりに部分木に含まれるノードの数を基準として扱う点が大きな特徴です。
重み w(x) の定義
ノード x の重み w(x) は、「x を根とする部分木内の内部ノードの総数」として定義されます。具体的には以下の通りです。
- x が外部ノード（external node）の場合：w(x) = 0
- x が内部ノード（internal node）の場合：w(x) = 左右の子の重みの合計 + 1
WBLTの具体例
それでは、実際の例を見ていきましょう。まず、次のような二分木を考えてみます。
この二分木に対して、各ノードの w(x) の値を計算すると、以下のようになります。
WBLTの定義
二分木が重みバランス左翼木（Weight Biased Leftist Tree）と呼ばれるのは、すべての内部ノードにおいて、左の子の w(x) が右の子の w(x) 以上である場合、かつその場合に限られます。
また、最大（最小）WBLTとは、WBLTの性質を満たす最大（最小）木のことを指します。この性質により、WBLTは優先度付きキューなどのデータ構造の実装において、効率的なマージ操作を実現するために活用されています。
-
BSPツリー（空間分割木）とは？データ構造の基本原理と生成アルゴリズムを徹底解説
BSPツリーの概要 コンピュータサイエンスの分野では、バイナリ空間分割（Binary Space Partitioning：BSP）と呼ばれる手法が用いられています。これは、超平面（ハイパープレーン）を分割面として使用し、空間を再帰的に2つの凸集合へと分割していく方法です。この分割処理を繰り返すことで、領域内のオブジェクトを木構造（ツリー構造）として表現できるようになります。このデータ構造がBSPツリーです。 バイナリ空間分割は、1969年に3Dコンピュータグラフィックスの文脈で考案されました。BSPツリーの構造により、シーン内のオブジェクトに関する空間情報を高速に参照することが可能になりま
-
データ構造の範囲ツリー(レンジツリー)とは?仕組み・kd-treeとの違い・構築方法を解説
範囲ツリー(range tree)は、点の集合を格納するための順序付き木構造として定義されるデータ構造です。最大の特徴は、指定された範囲内に存在するすべての点を効率的に取得できる点にあり、実務では主に2次元以上の空間で実装されます。範囲ツリーはkd-tree(kd木)とよく似た構造を持っていますが、両者には明確なトレードオフがあります。範囲ツリーはクエリ時間が O(logd n + k) とkd-treeより高速である一方、必要な記憶領域は O(n logd-1 n) と大きくなります。ここで、d は空間の次元数、n は木に格納されている点の総数、k は1回のクエリで取得される点の数を表します