BalancedTree完成
BalancedTree - 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+1] 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 len(self.parent.link)>i+1: 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 else: self.parent.link.append(gt) self.parent._optimize() else: self.page=[self.page[self.N/2]] self.link=[lt,gt] lt.parent=self gt.parent=self elif len(self.page)<(self.N/2) and self.parent: for i in range(len(self.parent.page)): if self.parent.link[i]==self: break if self.parent.link[i]==self: self.page.append(self.parent.page[i]) self.link.append(None) self.parent.page=self.parent.page[:i]+self.parent.page[i+1:] tmp=self.parent.link[i+1] self.parent.link=self.parent.link[:i+1]+self.parent.link[i+2:] self._merge(tmp) else: self.page=[self.parent.page[i]]+self.page self.link=[None]+self.link self.parent.page=self.parent.page[:-1] self.parent.link=self.parent.link[:-1] self.parent.link[i]._merge(self) if not self.parent.page: self.parent.page=self.parent.link[0].page self.parent.link=self.parent.link[0].link for l in self.parent.link: if l: l.parent=self.parent self.parent._optimize() for l in self.link: if l: l.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): if not self.page: return None for i in range(len(self.page)): d,v=self.page[i] if d==index: if not self.link[i]: self.page=self.page[:i]+self.page[i+1:] self.link=self.link[:i]+self.link[i+1:] else: self.page=self.page[:i]+self.page[i+1:] tmp=self.link[i] self.link=self.link[:i]+self.link[i+1:] self.link[i]._merge(tmp) if not self.page: if self.link[0]: self.page=self.link[0].page self.link=self.link[0].link for l in self.link: if l: l.parent=self self._optimize() return v if d>index: if self.link[i]: return self.link[i].remove(index) else: return None if self.link[len(self.page)]: return self.link[len(self.page)].remove(index) else: return None def _merge(self,sibling): if not sibling: return if not self.page: self.page=sibling.page self.link=sibling.link return else: for l in sibling.link: if l: l.parent=self a,b=sibling.page[0] c,d=self.page[0] if a<c: self.page=sibling.page+self.page self.link=sibling.link[:-1]+self.link if self.link[len(sibling.link)-1]: self.link[len(sibling.link)-1]\ ._merge(sibling.link[len(sibling.link)-1]) else: self.page=self.page+sibling.page tmp=self.link[len(self.link)-1] tmp_i=len(self.link)-1 self.link=self.link[:-1]+sibling.link if self.link[tmp_i]: self.link[tmp_i]._merge(tmp) self._optimize() def height(self): if self.link[0]: return self.link[0].height()+1 else: return 1
前に書いた二分木は相当遅かったが、これはそれなりのスピードで追加、削除、検索が行える。
次に書くのはB+-TreeかB*-Treeどちらにしよう。
