прикреплённый файл:Tree.py к странице LecturesVMSH/2011-05-11

   1 #!/usr/bin/python
   2 # coding: utf8
   3 '''АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.'''
   4 
   5 class tree:
   6     '''Simple tree class'''
   7     def recalc(self):
   8         '''Recalcelate tree volume and height'''
   9         self.H=1+max(self.GT.H, self.LT.H)
  10         self.V=1+self.GT.V+self.LT.V
  11     def __init__(self, *args):
  12         '''No args or key, value, LT, GT'''
  13         if args:    # имеется ключ, значение и два поддерева
  14             self.key,self.value, self.LT,self.GT=args
  15             self.recalc()
  16         else:
  17             self.H=self.V=0
  18             self.key=self.value=self.GT=self.LT=None
  19     def __setitem__(self, key, value):
  20         '''Add value with key'''
  21         if self.key == key:
  22             self.value=value
  23             return
  24         if self.key == None:
  25             self.key,self.value=key,value
  26             self.V,self.H=1,1
  27             self.LT,self.GT=self.__class__(),self.__class__()   # Грязный трюк
  28         else:
  29             if key>self.key:
  30                 self.GT[key]=value
  31             else:
  32                 self.LT[key]=value
  33             self.recalc()
  34         self.balance()
  35     def __iter__(self):
  36         if self:
  37             yield self.key
  38             for k in self.LT: yield k
  39             for k in self.GT: yield k
  40     def __getitem__(self, key):
  41         '''Search node with key, return its value'''
  42         if self.key == key: return self.value
  43         if key > self.key and self.GT: return self.GT[key]
  44         if key < self.key and self.LT: return self.LT[key]
  45         return None
  46     def __nonzero__(self):
  47         return self.key != None
  48     def balance(self):
  49         pass
  50     def __str__(self):
  51         container=[]
  52         stack=[self]
  53         while stack:
  54             container.append([(c.key, c.value, c.V, c.H) for c in stack])
  55             stack,todo=[],stack
  56             for c in todo:
  57                 if c.LT: stack.append(c.LT)
  58                 if c.GT: stack.append(c.GT)
  59         return "\n".join([" | ".join(["{0}: {1}/{2}/{3}/".format(*c) for c in s]) for s in container])
  60     def __delitem__(self, key):
  61         '''Delete an item -- tree needs repair'''
  62         path=[self]
  63         while path[-1].key != key:
  64             if key < path[-1].key: path.append(path[-1].LT)
  65             else: path.append(path[-1].GT)
  66         curr=path.pop()
  67         if curr.GT or curr.LT:  # узел -- поддерево
  68             if curr.LT.H>curr.GT.H:
  69                 sub=curr.LT
  70                 while sub.GT: sub=sub.GT
  71             else:
  72                 sub=curr.GT
  73                 while sub.LT: sub=sub.LT
  74             del curr[sub.key]
  75             curr.key=sub.key
  76             curr.value=sub.value
  77         else:                   # узел -- лист
  78             if path[-1].GT == curr: path[-1].GT=self.__class__()    # Грязный трюк
  79             else: path[-1].LT=self.__class__()                      # Грязный трюк
  80         while path:
  81             c=path.pop()
  82             c.recalc()
  83             c.balance()
  84     def __cmp__(self, T):
  85         '''"Compare" trees. WARNING: if volumes are equal, compare dump lists'''
  86         if not self and not T: return 0
  87         if self.V != T.V: return cmp(self.V, T.V)
  88         for i,j in zip(self,T):
  89             if i!=j: return cmp(i,j)
  90             if self[i]!=T[j]: return cmp(self[i],T[j])
  91         return 0
  92 
  93 class AVLtree(tree):
  94     '''AVL tree class'''
  95     def balance(self):
  96         '''Standard 4-way turn balancing'''
  97         if self.LT.H-self.GT.H in (-1,0,1):
  98             return
  99         if self.LT.H < self.GT.H:
 100             # Малое левое вращение
 101             if self.GT.LT.H <= self.GT.GT.H:
 102                 a=AVLtree(self.key, self.value, self.LT, self.GT.LT)
 103                 self.key, self.value, self.LT, self.GT = self.GT.key, self.GT.value, a, self.GT.GT
 104             # Большое левое вращение
 105             else:
 106                 a=AVLtree(self.key, self.value, self.LT, self.GT.LT.LT)
 107                 b=AVLtree(self.GT.key, self.GT.value, self.GT.LT.GT, self.GT.GT)
 108                 self.key, self.value, self.LT, self.GT = \
 109                         self.GT.LT.key, self.GT.LT.value, a, b
 110         else:
 111             # Малое правое вращение
 112             if self.LT.LT.H >= self.LT.GT.H:
 113                 a=AVLtree(self.key, self.value, self.LT.GT, self.GT)
 114                 self.key, self.value, self.LT, self.GT = self.LT.key, self.LT.value, self.LT.LT, a
 115             # Большое правое вращение
 116             else:
 117                 a=AVLtree(self.key, self.value, self.LT.GT.GT, self.GT)
 118                 b=AVLtree(self.LT.key, self.LT.value, self.LT.LT, self.LT.GT.LT)
 119                 self.key, self.value, self.LT, self.GT = \
 120                         self.LT.GT.key, self.LT.GT.value, b, a
 121         self.recalc()
 122 
 123 def gen(N,init=[],Tree=AVLtree):
 124     import random
 125     def word(i):
 126         letters=("aouiey","qwrtpsdfghjklzxcvbnm")
 127         r,c="",0
 128         while i:
 129             r+=letters[c][i%len(letters[c])]
 130             i/=len(letters[c])
 131             c=1-c
 132         return r
 133 
 134     T=Tree()
 135     for i in init: T[i]="-"+word(i)
 136     for i in random.sample(xrange(100,max(N+100,10000)),N):
 137         T[i]="+"+word(i)
 138     return T
 139 
 140 if __name__ == "__main__":
 141     import sys
 142     N,init,Tree=25,[],AVLtree
 143     a=sys.argv[1:]
 144     while len(a)>0:
 145         if a[0].endswith("e"):
 146             Tree=eval(a.pop(0))
 147         elif a[0].startswith("="):
 148             N=int(a.pop(0)[1:])
 149         else:
 150             init=[int(c) for c in a]
 151             a=[]
 152     T=gen(N,init,Tree)
 153     print T
 154     for c in T: print T[c],