-
Notifications
You must be signed in to change notification settings - Fork 0
/
bst.py
108 lines (94 loc) · 3.25 KB
/
bst.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
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
class BinarySearchTree():
def __init__(self, value = None):
self.value = value
self.left = None
self.right = None
self.parent = None
def insert(self, insertee):
if insertee.value <= self.value:
if self.left == None:
self.left = insertee
insertee.parent = self
return
else:
return self.left.insert(insertee)
if insertee.value > self.value:
if self.right == None:
self.right = insertee
insertee.parent = self
return
else:
return self.right.insert(insertee)
def find(self, value):
if value == self.value:
return self
elif value < self.value:
if self.left == None:
return None
else:
return self.left.find(value)
else:
if self.right == None:
return None
else:
return self.right.find(value)
def traverse_pre_order(self, values = []):
values.append(self.value)
if self.left != None:
values = self.left.traverse_pre_order(values)
if self.right != None:
values = self.right.traverse_pre_order(values)
return values
def traverse_in_order(self, values = []):
if self.left != None:
values = self.left.traverse_in_order(values)
values.append(self.value)
if self.right != None:
values = self.right.traverse_in_order(values)
return values
def traverse_post_order(self, values = []):
if self.left != None:
values = self.left.traverse_post_order(values)
if self.right != None:
values = self.right.traverse_post_order(values)
values.append(self.value)
return values
def delete(self, target_node):
if target_node.left == None and target_node.right == None:
if target_node.value < target_node.parent.value:
target_node.parent.left = None
else:
target_node.parent.right = None
elif (target_node.left != None and target_node.right == None) or (target_node.left == None and target_node.right != None):
if target_node.value <= target_node.parent.value:
if target_node.left != None and target_node.right == None:
target_node.left.parent = target_node.parent
target_node.parent.left = target_node.left
elif target_node.left == None and target_node.right != None:
target_node.right.parent = target_node.parent
target_node.parent.left = target_node.right
else:
if target_node.left != None and target_node.right == None:
target_node.left.parent = target_node.parent
target_node.parent.right = target_node.left
elif target_node.left == None and target_node.right != None:
target_node.right.parent = target_node.parent
target_node.parent.right = target_node.right
else:
replacement_node = None
replacement_node = target_node.right
while(replacement_node.left != None):
replacement_node = replacement_node.left
if replacement_node.right != None:
replacement_node.right.parent = replacement_node.parent
replacement_node.parent.left = replacement_node.right
if replacement_node != target_node.right:
replacement_node.right = target_node.right
target_node.right.parent = replacement_node
replacement_node.left = target_node.left
target_node.left.parent = replacement_node
replacement_node.parent = target_node.parent
if target_node.value <= target_node.parent.value:
target_node.parent.left = replacement_node
else:
target_node.parent.right = replacement_node