BalancedTree
Bツリー - MasaHeroの日記に続いて書いてみた。
class BalancedTree: def __init__(self,max_n,parent=None): self.page=[] self.link=[] self.N=(max_n/2)*2 self.parent=parent def append(self,index,value): if len(self.page) == 0: self.page=[(index,value)] self.link=[None,None] else: for i in range(len(self.page)): d,v=self.page[i] if d == index: self.page[i]=(index,value) break if d > index: if self.link[i]: self.link[i].append(index,value) else: self.page=self.page[:i]+[(index,value)]\ +self.page[i:] self.link=self.link[:i]+[None]+self.link[i:] break if index > d: if self.link[i+1]: self.link[i+1].append(index,value) else: self.page.append((index,value)) self.link.append(None) self._optimize() def _optimize(self): if len(self.page)>self.N: gt=BalancedTree(self.N,self.parent) lt=BalancedTree(self.N,self.parent) gt.page=self.page[self.N/2+1:] lt.page=self.page[:self.N/2] gt.link=self.link[self.N/2+1:] lt.link=self.link[:self.N/2] for l in gt.link: if l: l.parent=gt for l in lt.link: if l: l.parent=lt if self.parent: for i in range(len(self.parent.link)): if self.parent.link[i]==self: self.parent.page=self.parent.page[:i]\ +[self.page[self.N/2]]\ +self.parent.page[i:] self.parent.link[i]=lt if self.parent.link[i+1]: self.parent.link=self.parent.link[:i+1]+[gt]\ +self.parent.link[i+1:] else: self.parent.link[i+1]=gt self.parent._optimize() else: self.page=[self.page[self.N/2]] self.link=[lt,gt] lt.parent=self gt.parent=self def get(self,index): if not self.page: return None for i in range(len(self.page)): d,v=self.page[i] if d==index: return v if d>index: if self.link[i]: return self.link[i].get(index) else: return None if self.link[len(self.page)]: return self.link[len(self.page)].get(index) else: return None def remove(self,index): pass
今回はメソッド名を標準に合わせてみた。一応追加と検索は実装したが削除はまだ。そのうち書く。