Прикреплённый файл «Tree.py»
Загрузка 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],
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2011-09-26 11:35:36, 5.7 KB) [[attachment:Tree.py]]
- [получить | показать] (2011-09-26 11:35:36, 1.2 KB) [[attachment:Treecount.py]]
- [получить | показать] (2011-09-26 11:35:36, 2.4 KB) [[attachment:Treeops.py]]
- [получить | показать] (2011-09-26 11:35:36, 1.7 KB) [[attachment:compare.py]]
Вам нельзя прикреплять файлы к этой странице.