Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit25519dc

Browse files
committed
Added AVLTree
1 parente0f1f47 commit25519dc

File tree

2 files changed

+135
-36
lines changed

2 files changed

+135
-36
lines changed

‎trees/avl_tree.py‎

Lines changed: 101 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -42,34 +42,107 @@ def add(self, element):
4242
self.right).balance()
4343

4444
defbalance(self):
45-
returnself
45+
ifself.right_is_heavier():
46+
ifself.right.left_is_heavier():
47+
returnself.rotate_double_left()
4648

47-
defrotate_right(self):
48-
pass
49+
else:
50+
returnself.rotate_left()
51+
52+
elifself.left_is_heavier():
53+
ifself.left.right_is_heavier():
54+
returnself.rotate_double_right()
55+
56+
else:
57+
returnself.rotate_right()
58+
59+
else:
60+
returnself
4961

5062
defrotate_left(self):
51-
pass
63+
ifself.rightisNone:
64+
returnself
65+
66+
returnAVLTree(self.right.value,
67+
AVLTree(self.value,
68+
self.left,
69+
self.right.left),
70+
self.right.right)
71+
72+
defrotate_right(self):
73+
ifself.leftisNone:
74+
returnself
75+
76+
returnAVLTree(self.left.value,
77+
self.left.left,
78+
AVLTree(self.value,
79+
self.left.right,
80+
self.right))
5281

5382
defrotate_double_right(self):
54-
pass
83+
ifself.leftisNone:
84+
returnself
85+
86+
returnAVLTree(self.value,
87+
self.left.rotate_left(),
88+
self.right).rotate_right()
5589

5690
defrotate_double_left(self):
57-
pass
91+
ifself.rightisNone:
92+
returnself
93+
94+
returnAVLTree(self.value,
95+
self.left,
96+
self.right.rotate_right()).rotate_left()
5897

5998
defright_is_heavier(self):
60-
pass
99+
balance=len(self.right)ifself.rightelse0-len(
100+
self.left)ifself.leftelse0
101+
returnbalance>=2
61102

62103
defleft_is_heavier(self):
63-
pass
104+
balance=len(self.right)ifself.rightelse0-len(
105+
self.left)ifself.leftelse0
106+
returnbalance<=-2
64107

65108
defpop(self,element):
66-
pass
109+
ifself.value==element:
110+
# This is the element to be removed.
111+
ifnotself.rightandnotself.left:
112+
returnNone
113+
114+
elifself.rightandnotself.left:
115+
returnself.right
67116

68-
defdelete(self,node):
69-
pass
117+
elifself.leftandnotself.right:
118+
returnself.left
119+
120+
else:
121+
# We have two children
122+
sucessor=self.right
123+
whilesucessor.left:
124+
sucessor=sucessor.left
125+
126+
returnAVLTree(sucessor.value,self.left,self.right.pop(
127+
sucessor.value)).balance()
128+
129+
elifself.value>element:
130+
returnAVLTree(self.value,self.left.pop(element),
131+
self.right).balance()
132+
133+
else:
134+
returnAVLTree(self.value,self.left,
135+
self.right.pop(element)).balance()
70136

71137
defsearch(self,element):
72-
pass
138+
ifelement==self.value:
139+
returnself
140+
141+
elifelement>self.valueandself.rightisnotNone:
142+
returnself.right.search(element)
143+
144+
elifelement<=self.valueandself.leftisnotNone:
145+
returnself.left.search(element)
73146

74147
def__contains__(self,item):
75148
ifitem==self.value:
@@ -103,4 +176,19 @@ def __cmp__(self, other):
103176

104177
def__repr__(self):
105178
return"%s(%s, %r, %r)"% (self.__class__.__name__,
106-
self.value,self.left,self.right)
179+
self.value,self.left,self.right)
180+
181+
defis_balanced(self):
182+
left_height=len(self.left)ifself.leftelse0
183+
right_height=len(self.right)ifself.rightelse0
184+
185+
ifnotabs(left_height-right_height)<=1:
186+
returnFalse
187+
188+
ifself.leftandnotself.left.is_balanced():
189+
returnFalse
190+
191+
ifself.rightandnotself.right.is_balanced():
192+
returnFalse
193+
194+
returnTrue

‎trees/trees_unittests.py‎

Lines changed: 34 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -219,9 +219,6 @@ def test_init(self):
219219
AVLTree(None,None,None))
220220
self.assertEqual(avl.height,3)
221221

222-
deftest_init_empty(self):
223-
pass
224-
225222
deftest_add(self):
226223
avl=AVLTree(50,AVLTree(17,None,AVLTree(23,
227224
None,
@@ -235,12 +232,20 @@ def test_add(self):
235232
39],reverse=True)
236233
actual_itered=list(avl)
237234

238-
printavl
239-
240235
self.assertEqual(actual_itered,expected_itered)
241236

242-
deftest_remove(self):
243-
pass
237+
deftest_pop(self):
238+
avl=AVLTree(50,AVLTree(17,AVLTree(12,None,None),AVLTree(23,
239+
None,
240+
None)),
241+
AVLTree(72,AVLTree(54,None,None),
242+
AVLTree(76,None,None)))
243+
244+
avl=avl.pop(50)
245+
246+
actual_list=list(avl)
247+
expected_list=sorted([17,12,23,72,54,76],reverse=True)
248+
self.assertEqual(actual_list,expected_list)
244249

245250
deftest_in(self):
246251
avl=AVLTree(50,AVLTree(17,AVLTree(12,None,None),AVLTree(23,
@@ -299,26 +304,32 @@ def test_cmp(self):
299304
self.assertTrue(notavl2<avl3)
300305
self.assertTrue(avl2==avl3)
301306

302-
deftest_balance(self):
303-
pass
307+
deftest_is_balanced(self):
308+
tree=AVLTree(4,None,None)
309+
self.assertTrue(tree.is_balanced())
304310

305-
deftest_rotate_left(self):
306-
pass
311+
tree=AVLTree(None,AVLTree(None,
312+
AVLTree(None,None,None),None),None)
313+
self.assertFalse(tree.is_balanced())
314+
315+
tree=AVLTree(50,AVLTree(17,AVLTree(12,None,None),AVLTree(23,
316+
None,
317+
None)),
318+
AVLTree(72,AVLTree(54,None,None),
319+
AVLTree(76,None,None)))
307320

308-
deftest_rotate_right(self):
309-
pass
321+
self.assertTrue(tree.is_balanced())
310322

311-
deftest_rotate_double_left(self):
312-
pass
323+
deftest_remove_add_balanced(self):
324+
tree=AVLTree(4,None,None)
325+
tree.add(1).add(2).add(3).add(4).add(7).add(9).pop(4).pop(9).add(
326+
20).add(-2).add(21).add(-3).pop(-3)
313327

314-
deftest_rotate_double_right(self):
315-
pass
328+
self.assertTrue(tree.is_balanced())
316329

317330
deftest_search(self):
318-
pass
319-
320-
deftest_right_is_heavier(self):
321-
pass
331+
avl=AVLTree(1,None,None).add(2).add(3).add(4).add(5).add(-2).add(10)
332+
searched_node=avl.search(-2)
333+
expected_node=AVLTree(-2,None,None)
322334

323-
deftest_left_is_heavier(self):
324-
pass
335+
self.assertEqual(searched_node,expected_node)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp