アルゴリズムクイックリファレンス 第2版

10.8

 

R

木

■

359

# D2 [

レコード削除

] n

から

E

を削除

parent.removeRNode(leaf)

# D3 [

変化伝播

]

親に対して

condenseTree

を呼び出す

if parent == self.root:

self.root.adjustRegion()

else:

Q = parent.condenseTree(path, self.m, self.M)

self.root.adjustRegion()

# CT6 [

孤立エントリを再挿入

] Q

の節点のエントリをすべて再挿入。

for n in Q:

for rect,ident in n.leafOrder():

self.add(rect, ident)

# D4 [

木を短縮

]

木を調整した後で、根に

1

つの子しかなければ、

#

その子を新しい根にする。

while self.root.count == 1 and self.root.level > 0:

self.root = self.root.children[0]

if self.root.count == 0:

self.root = None

return True

10.8.4

 分析

R

木

の構造は、長方形が挿入されたときに自分で平衡を取る機能によって、性能

を確保している。すべての長方形がR木の同じ高さにある葉に格納されているとい

うことは、内部節点は、それらを記録管理するためだけの構造を表していることに

なる。

m

と

M

というパラメ