forked from TheAlgorithms/Python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary_search_tree.py
More file actions
221 lines (188 loc) · 6.75 KB
/
binary_search_tree.py
File metadata and controls
221 lines (188 loc) · 6.75 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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
"""
A binary search Tree
"""
class Node:
def __init__(self, value, parent):
self.value = value
self.parent = parent # Added in order to delete a node easier
self.left = None
self.right = None
def __repr__(self):
from pprint import pformat
if self.left is None and self.right is None:
return str(self.value)
return pformat({"%s" % (self.value): (self.left, self.right)}, indent=1)
class BinarySearchTree:
def __init__(self, root=None):
self.root = root
def __str__(self):
"""
Return a string of all the Nodes using in order traversal
"""
return str(self.root)
def __reassign_nodes(self, node, new_children):
if new_children is not None: # reset its kids
new_children.parent = node.parent
if node.parent is not None: # reset its parent
if self.is_right(node): # If it is the right children
node.parent.right = new_children
else:
node.parent.left = new_children
else:
self.root = new_children
def is_right(self, node):
return node == node.parent.right
def empty(self):
return self.root is None
def __insert(self, value):
"""
Insert a new node in Binary Search Tree with value label
"""
new_node = Node(value, None) # create a new Node
if self.empty(): # if Tree is empty
self.root = new_node # set its root
else: # Tree is not empty
parent_node = self.root # from root
while True: # While we don't get to a leaf
if value < parent_node.value: # We go left
if parent_node.left is None:
parent_node.left = new_node # We insert the new node in a leaf
break
else:
parent_node = parent_node.left
else:
if parent_node.right is None:
parent_node.right = new_node
break
else:
parent_node = parent_node.right
new_node.parent = parent_node
def insert(self, *values):
for value in values:
self.__insert(value)
return self
def search(self, value):
if self.empty():
raise IndexError("Warning: Tree is empty! please use another.")
else:
node = self.root
# use lazy evaluation here to avoid NoneType Attribute error
while node is not None and node.value is not value:
node = node.left if value < node.value else node.right
return node
def get_max(self, node=None):
"""
We go deep on the right branch
"""
if node is None:
node = self.root
if not self.empty():
while node.right is not None:
node = node.right
return node
def get_min(self, node=None):
"""
We go deep on the left branch
"""
if node is None:
node = self.root
if not self.empty():
node = self.root
while node.left is not None:
node = node.left
return node
def remove(self, value):
node = self.search(value) # Look for the node with that label
if node is not None:
if node.left is None and node.right is None: # If it has no children
self.__reassign_nodes(node, None)
elif node.left is None: # Has only right children
self.__reassign_nodes(node, node.right)
elif node.right is None: # Has only left children
self.__reassign_nodes(node, node.left)
else:
tmp_node = self.get_max(
node.left
) # Gets the max value of the left branch
self.remove(tmp_node.value)
node.value = (
tmp_node.value
) # Assigns the value to the node to delete and keep tree structure
def preorder_traverse(self, node):
if node is not None:
yield node # Preorder Traversal
yield from self.preorder_traverse(node.left)
yield from self.preorder_traverse(node.right)
def traversal_tree(self, traversal_function=None):
"""
This function traversal the tree.
You can pass a function to traversal the tree as needed by client code
"""
if traversal_function is None:
return self.preorder_traverse(self.root)
else:
return traversal_function(self.root)
def inorder(self, arr: list, node: Node):
"""Perform an inorder traversal and append values of the nodes to
a list named arr"""
if node:
self.inorder(arr, node.left)
arr.append(node.value)
self.inorder(arr, node.right)
def find_kth_smallest(self, k: int, node: Node) -> int:
"""Return the kth smallest element in a binary search tree """
arr = []
self.inorder(arr, node) # append all values to list using inorder traversal
return arr[k - 1]
def postorder(curr_node):
"""
postOrder (left, right, self)
"""
node_list = list()
if curr_node is not None:
node_list = postorder(curr_node.left) + postorder(curr_node.right) + [curr_node]
return node_list
def binary_search_tree():
r"""
Example
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
>>> t = BinarySearchTree().insert(8, 3, 6, 1, 10, 14, 13, 4, 7)
>>> print(" ".join(repr(i.value) for i in t.traversal_tree()))
8 3 1 6 4 7 10 14 13
>>> print(" ".join(repr(i.value) for i in t.traversal_tree(postorder)))
1 4 7 6 3 13 14 10 8
>>> BinarySearchTree().search(6)
Traceback (most recent call last):
...
IndexError: Warning: Tree is empty! please use another.
"""
testlist = (8, 3, 6, 1, 10, 14, 13, 4, 7)
t = BinarySearchTree()
for i in testlist:
t.insert(i)
# Prints all the elements of the list in order traversal
print(t)
if t.search(6) is not None:
print("The value 6 exists")
else:
print("The value 6 doesn't exist")
if t.search(-1) is not None:
print("The value -1 exists")
else:
print("The value -1 doesn't exist")
if not t.empty():
print("Max Value: ", t.get_max().value)
print("Min Value: ", t.get_min().value)
for i in testlist:
t.remove(i)
print(t)
if __name__ == "__main__":
import doctest
doctest.testmod()
# binary_search_tree()