kd-tree Visualization(2)

先日のエントリにて、kd木を紹介しました。前回はアルゴリズム Cに倣って、要素の追加のみでkd木を構築してみました。

繰り返しになりますが、一般的に要素の追加のみでkd木を構築するとバランスの悪い木となることが知られています。先日のエントリで作成したkd木を可視化したものは以下のようなものでした。

同じく、木構造として可視化したものは以下のようなものでした。

さて、では何故均衡の取れない木が構築されてしまうのでしょう? 座標群の初めの点、1番の点を挿入した直後の状態を可視してみましょう。

この可視と先ほどの木構造としての可視を比較すると不均衡な木が構築される理由がより明らかとなります。木構造の可視にて1番の左側にぶら下がっている2番以下の座標群は、この可視では1番によって空間分割された領域の下側、つまり、y座標値がより小さい側に分布しています。

同様に、木構造にて1番の右側にぶら下がっている9番以下の座標群は、この可視では1番によって空間分割された領域の上側、つまり、y座標値がより大きい側に分布していることが分かります。

空間分割された双方の座標の数に偏りがあるのは明白です。つまり、1番の座標は、空間の上下を木構造的に均等に分割する座標ではなかったのです。そのため、この時点ですでに木構造の不均衡が生じ始めているのです。

さて、ではバランスの取れた木構造を構築するにはどうしたらよいでしょう? 空間分割した結果、木構造的に均等に座標群が分割出来る座標を選べばよいのです。この座標群では、まず初めに以下に示す座標を選べば、均等に座標群を分割することが期待出来ます。

1番の座標によって分割された空間には、それぞれ同等量の座標群が含まれていますね。

次の空間分割も同様に、均等に座標群を分割する座標を選択します。

これを再帰的に繰り返します。

このように座標群を均等に分割するには、メディアンの座標を選択するのが良さそうです。では、メディアンを加味した2d木を構築してみましょう。今回もPythonで記述しています。また、sort()を用いたメディアンの選択はコストが高いことで知られていますが、今回はコードの見通しを良くするために敢えて使用しています。

#!/usr/bin/python -t

from operator import itemgetter
from random import seed, randint

def build(points, d=1):
    pts = list(points)

    if not pts:
        return None
    
    h = len(pts) // 2

    pts.sort(key=itemgetter(d))

    d = (d + 1) % 2

    return [build(pts[0:h],  d),
            build(pts[h+1:], d),
            pts[h]]

if __name__ == '__main__':
    seed(0)
    pts = [(randint(1, 100), randint(1, 100))
           for i in range(32)]

    tree = [None, build(pts), (0, 0)]

結果をPostScriptで可視化してみます。座標に振られている番号は、先日のエントリと同様に、kd木に挿入された順番を示しています。今回は空間分割を行う座標をメディアンを元に動的に決定しているため、元々与えられた座標群の順番とは異なった番号が振られています。

これはバランスが良さそうですね。木表現として可視化しましょう。

なかなか均衡の取れたkd木が構築出来たことが分かります。均衡の取れたkd木における検索の計算量はO(log N)と言われていますので、接点数が32個のこの木では5回になるはずです。6番の頂点を検索するためには6回計算をしなければならないようですが、その他の頂点群の検索の回数は5回以内の計算数で収まりました。

では、これらのエントリを記載する動機となった、極端に整列している座標群を与えて2d木を構築してます。座標群は先日のエントリと同様に、10刻みの座標群を用いました。