トップページ > ダウンロード > ヒープ探索木

ヒープ探索木(Priority Search Trees, PST)

1.概要

◆デモサンプル画面 <sample image of demo-program>


 
◆機能概要
  XY平面上に分布するN個の点(X,Y)に対して、Y≧y0かつx0≦X≦x1である点(X,Y)をO(k+logN)の
 手間で得られる。
 ここで、kは条件を満たす点の数で、最大値はNである。
 点の追加、削除に対してもO(logN)の手間でPSTを再構成できる。必要なメモリ量はO(N)である。
 
◆アルゴリズム概要
  XY平面上の点の集合に対して、Y座標値でヒープを構成し、X座標値で平衡探索木を構成する。
 
◆方式
  方式としては(1)McCreight方式と(2)place holder方式がある。
(1)McCreight方式では木のノード数がNで済む。
  1つのノードに2つ点を格納することがあるので描画には向かない。
  ノード数が少ないのでメモリ効率が良い。
 
(2)place holder方式は木のノード数が2N−1であり、N−1個の葉ノードを除いて、
  1つのノードに1個の点を格納するので、木を直感的に描画できる。
  place holderノードに点を格納した部分はバランスが崩れて見える場合があるが、空のplace holderノードまで考慮するとバランスしている。
 
◆用途
(1)線分重なり判定 (区間の交差問題)
 直線上のN個の線分[X,Y]が与えられた時に、質問線分[a,b]と交叉する全ての線分をO(k+logN)で得られる。
 すなわち、線分[X,Y]に対して点(X,Y)を対応させて、Y≧a かつX≦bを満たす点が線分[a,b]と交叉する線分
 である。
 
(2)長方形の重なり判定 (長方形交差問題)
 水平線と垂直線を辺とするN個の長方形が与えられた時に、交差する長方形のペアを抽出する問題に
 対して、走査線をずらしながら、線分の重なり判定と線分の追加削除を繰り返すことで、ペアを効率よく抽出できる。

2.制限

本プログラムは評価版の為、以下の制限を設けている。
 
  使用期限 2016/12/31

3.使用方法

◆ダウンロード(ダウンロードのページからもダウンロードできます)
  
   sample07.zip  26.0 KB (26,718 バイト)
   sample07.lzh  25.8 KB (26,499 バイト)
 
       展開後  PStree.exe       20,480 バイトト
                 pstreeDll.dll    140,288 バイト

3.1 インストール 
 
 (1)ダウンロードしたファイルを、任意のディレクトリに解凍します。
 
  (a)使用許諾契約書.txt
  (b) pstreeDll.dll
  (c) PStree.exe

3.2 アンインストール
 
 (1)インストール時に作成したディレクトリごとファイルを削除します。

3.3 使用方法
 
  PStree.exeをダブルクリック
    ※実行時には、.NetFramework3.5 が必要です。
 

4.開発環境

プログラムコードは、下記言語で作られています。

 pstreeDll.dll は、 Visual Studio 2008 C++
 PStree.exe   は、 Visual Studio 2008 C#
Copyright 2011 Sogen System Co.,Ltd. All Rights Reserved.