Contents


実行環境



配列を先頭からノードに割り付け(座標付け)

今回の「配列」は、Rのデータ型で言えばベクトルです。先頭の要素から順に、二分木の上下(同じ段では左右)のノードと見なし、プロットするために座標を付け、3列のデータフレーム(x、y、配列の中身)にして返す関数datTreeを作りました。
example_datTree.RSelectRawtextBitbucket
# create vector
vec = floor(runif(31) * 100)
vec = sort(unique(vec), decreasing=T)

# add coordinates of binary tree to each element
datTree = function (vec, order='') {
    len = length(vec)
    dep = ceiling(log2(len))
    dat = data.frame(x=rep(NA, len), y=rep(NA, len), val=vec)
    for (i in 1:dep) {
        j = 2 ^ (i - 1) : min(len, 2 ^ i - 1)
        dat$x[j] = (2 ^ (dep - i - 1)) * (2 * (seq(j) - 1) + 1) + 0.5
        dat$y[j] = ifelse(order == 'rev', i, 1 - i)
    }
    return(dat)
}

dat = datTree(vec)
print(dat)


プロット

上の結果のデータフレームを単純にプロットすると ↓ こんな感じ。
plot(axes=F, x=dat$x, y=dat$y, type='n')
for (i in 2:nrow(dat)) lines(dat[c(i, floor(i / 2)),])
text(dat, label=dat$val, col='red')

ここまでは簡単ですが、ノードを丸数字にする、余白を少なくする、出力サイズを変えても同様のプロット結果にする、などの整形がRでは大変。自分の未熟さもあって ↓ こんな長いコードになりました。。。
example_plotTree.RSelectRawtextBitbucket
plotTree = function (dat) {
    # settings
    width = 500    # pixel
    plt = c(5, 98) / 100
    asp = 1.25     # ratio (y / x)
    circle = 20    # ratio to par('cin')[1]
    text = 0.25    # ratio to circle
    lwd = 0.5      # line width
    bgcolor = 'whiteSmoke'

    xlm = c(1, 2 ^ floor(log2(nrow(dat))))
    xpd = diff(xlm) / 18 * c(-1, 1)
    ypd = xpd / asp
    xlm = xlm + xpd
    ylm = range(dat$y) + ypd
    height1 = width * (plt[2] - plt[1]) * diff(ylm) * asp / diff(xlm)
    height2 = width * plt[1] + height1 + width * (1 - plt[2])

    plt[3] = width * plt[1] / height2
    plt[4] = (width * plt[1] + height1) / height2

    svg('.test.svg', width=width/96, height=height2/96)
    par(bg=bgcolor, plt = plt, xpd=NA)
    cexCircle = par('cin')[1] * circle
    cexText = cexCircle * text

    plot(asp=asp, axes=F, type='n',
        x=xlm, y=ylm, xlab='', ylab='', xaxs='i', yaxs='i')
    for (i in 2:nrow(dat)) lines(dat[c(i, floor(i / 2)),], col='red')
    points(dat, cex=cexCircle, pch=21, bg='white', lwd=lwd)
    text(dat, label=dat$val, cex=cexText)

    par(cex=cexText, tck=0.03)
    xat = seq(1, xlm[2] - 1, by=2)
    yat = unique(dat$y)
    for (i in 1:2) {
        if (i == 1) { at = xat } else { at = yat }
        axis(i, at=at, col=NA, col.ticks=1, labels=NA, lwd=lwd)
    }
    
    usr = par('usr')
    xlbAt = usr[1] - diff(usr[1:2]) / diff(plt[1:2]) * (plt[1] / 4)
    ylbAt = usr[3] - diff(usr[3:4]) / diff(plt[3:4]) * (plt[3] / 2)
    text(label=xat, x=xat, y=ylbAt)
    text(adj=1, label=yat, x=xlbAt, y=yat)
    box(lwd=lwd)

    graphics.off()
}
plotTree(dat)


この結果が冒頭の画像で、元はSVGです。
» binary_tree.svg(40kB)


上下を逆にプロット(見てると不安になる)

最初に作ったdatTree関数には上下を逆にするオプション(第2引数)があり、実際の木と同様に上へ向かって枝分かれするプロットに使えます。
vec = floor(runif(31) * 100)
vec = sort(unique(vec))
dat = datTree(vec, 'rev')
print(dat)
plotTree(dat)

でも実際プロットすると、何だか不安になります。自分だけ?
» binary_tree_rev.svg(37.5kB)


igraphパッケージでも出来そう

今回は使わなかったけど、igraphパッケージでベクトルをグラフにすれば同様にプロットできるかも。



本来やりたいこと

Rとは余り関係なく、PostgreSQLの集約関数の状態遷移で、配列をヒープソートして四分位数とかパーセンタイルを出せないかな~と。PostgreSQL 9.4からパーセンタイル関数が追加されましたが、以前のバージョンもまだ少し使っているので。

パーセンタイルを出すには何らかの形で全レコードをストックする必要があり、状態遷移に配列を使い、適当な所でソートすると。その過程を可視化したいので、今日はRで書いてみました。座標付けまでは簡単だけど、ある程度きちんとプロットするのが大変。次はSVG + JavaScriptでやってみます。