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

今回はメソッド名を標準に合わせてみた。一応追加と検索は実装したが削除はまだ。そのうち書く。