アルゴリズム導論--第14章【データ構造の拡張】14.1
4139 ワード
主に以下のいくつかの部分を紹介します.1)赤と黒の木に第iの小数点を求めるには、ノード構造の種類にドメインsizeを追加する必要があります.このノードにはいくつかの内部ノードがあります.(現在のノードを含む)
OS-SELECT(root[T], i) r = size[left[x]] + 1 // +1， // ， if r == i return x // else i < r return OS-SELECT(left[x], i) return OS-SELECT(right[x], i-r) // ，2)ノードxが与えられています.このノードの中でのシーケンシャルエルゴードの位置を求めます.OS-RANK(T,x) r = size[left[x]] + 1 // r y = x while y!=root[T] if y == right[p[y]] // y // ， // r = r + size[left[p[y]]] + 1 y = p[y] return r
練習問題14.1-3OS-SELECT(x, i) r = size[left[x]] +1 while (i !=r ) { if (i < r) x = left[x] r = size[left[x]] +1 else x = right[x] r = size[left[x]] + 1 i = i - r } return x
14.1-5OS-SELECT-SUCCEED(T, x, i) r = OS-RANK(T, x) return OS-SELECT(root[T], r+i)
14.1-6挿入時に、iノードの左サブツリーを挿入すると、size＋1、右サブツリーならそのまま削除されます.同じ14.1-7の逆順で正しい定義はwikiトランスポートで、従来の逆順で正しいやり方は正規並べ替えで並べられます.複雑度もO(nlgn)ここでは順次ツリーを統計する構造で解決できます.その結果、14のindexはjで、最初の数のindexはiであり、j＞i&a[j]＜a[i]の場合は条件を満たすと、順序統計ツリーにおいてjは挿入順であり、第二の条件はa[j]の順で上位3つの数のランキングを得ることができ、つまりOS_を介して得られる.KEYRANKという関数は得られますが、結論はreult+=j+1-OS_です.KEYRANK(T,j)
私の個人ブログ: http://www.yancey.info/?p=145