-
Notifications
You must be signed in to change notification settings - Fork 0
/
tests.py
73 lines (61 loc) · 2.23 KB
/
tests.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from trees.BST import BinarySearchTree, Node
from trees.AVL import AVLTree, AVLNode
import random
def test_tree():
def test_if_tree_correct(root: Node):
if not root:
return True
if not root.left and not root.right:
return True
if root.left and root.right:
if not (root.left.val < root.val < root.right.val):
return False
else:
return test_if_tree_correct(root.left) and test_if_tree_correct(root.right)
elif root.left:
if not (root.left.val < root.val):
return False
else:
return test_if_tree_correct(root.left)
if root.right:
if not (root.val < root.right.val):
return False
else:
return test_if_tree_correct(root.right)
test = random.sample(range(100000), 4000)
tree = BinarySearchTree()
for number in test:
tree.insert(number)
assert test_if_tree_correct(tree.root)
for number in test:
tree.delete(number)
assert test_if_tree_correct(tree.root)
def test_avl_tree():
def test_if_tree_correct(tree: AVLTree, root: AVLNode):
if not root:
return True
if not root.left and not root.right:
return True
if root.left and root.right:
if not (root.left.val < root.val < root.right.val) or not (-2 < tree.get_balance(root) < 2):
return False
else:
return test_if_tree_correct(tree, root.left) and test_if_tree_correct(tree, root.right)
elif root.left:
if not (root.left.val < root.val):
return False
else:
return test_if_tree_correct(tree, root.left)
if root.right:
if not (root.val < root.right.val):
return False
else:
return test_if_tree_correct(tree, root.right)
test = random.sample(range(100000), 4000)
tree = AVLTree()
for number in test:
tree.insert(number)
assert test_if_tree_correct(tree, tree.root)
for number in test:
tree._delete_node(tree.root, number)
assert test_if_tree_correct(tree, tree.root)