-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path1.search.py
More file actions
92 lines (65 loc) · 2.04 KB
/
1.search.py
File metadata and controls
92 lines (65 loc) · 2.04 KB
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.__root = None
def insert(self, value): # Big-O: O(n) / Big-Theta: Θ(log n)
if self.__root is None:
self.__root = Node(value)
else:
self.__insert(self.__root, value)
def __insert(self, node, value):
if value < node.value:
if node.left is None:
node.left = Node(value)
else:
self.__insert(node.left, value)
else:
if node.right is None:
node.right = Node(value)
else:
self.__insert(node.right, value)
def search(self, target): # Big-O: O(n) / Big-Theta: Θ(log n)
return self.__search(self.__root, target)
def __search(self, node, target):
if node is None:
return None
if node.value == target:
return node
if target < node.value:
return self.__search(node.left, target)
return self.__search(node.right, target)
def print_tree(self):
self.__print_tree(self.__root, "", True)
def __print_tree(self, node, indent, last):
if node is not None:
print(indent, end='')
if last:
print("R -> ", end='')
indent += " "
else:
print("L -> ", end='')
indent += "| "
print(node.value)
self.__print_tree(node.left, indent, False)
self.__print_tree(node.right, indent, True)
bst = BinarySearchTree()
bst.insert(50)
bst.insert(90)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(10)
bst.insert(60)
bst.insert(80)
bst.print_tree()
search = 20
print(f"Search {search}: {bst.search(search) is not None}")
search = 80
print(f"Search {search}: {bst.search(search) is not None}")
search = 200
print(f"Search {search}: {bst.search(search) is not None}")