@@ -66,11 +66,29 @@ def insert(self, label):
6666 parent_node .setRight (new_node )
6767 #Set parent to the new node
6868 new_node .setParent (parent_node )
69- '''
70- def delete(self):
69+
70+ def delete (self , label ):
7171 if (not self .empty ()):
72- if()
73- '''
72+ #Look for the node with that label
73+ node = self .getNode (label )
74+ #If the node exists
75+ if (node is not None ):
76+ #If it has no children
77+ if (node .getLeft () is None and node .getRight () is None ):
78+ self .__reassignNodes (node , None )
79+ node = None
80+ #Has only right children
81+ elif (node .getLeft () is None and node .getRight () is not None ):
82+ self .__reassignNodes (node , node .getRight ())
83+ #Has only left children
84+ elif (node .getLeft () is not None and node .getRight () is None ):
85+ self .__reassignNodes (node , node .getLeft ())
86+ #Has two children
87+ else :
88+ tmpNode = self .getMax (node .getLeft ())
89+ self .delete (tmpNode .getLabel ())
90+ self .__reassignNodes (node , tmpNode )
91+
7492 def getNode (self , label ):
7593 curr_node = None
7694 #If the tree is not empty
@@ -89,18 +107,23 @@ def getNode(self, label):
89107 curr_node = curr_node .getRight ()
90108 return curr_node
91109
92- def getMax (self ):
93- #We go deep on the right branch
94- curr_node = None
95- if (not self .empty ()):
110+ def getMax (self , root = None ):
111+ if (root is not None ):
112+ curr_node = root
113+ else :
114+ #We go deep on the right branch
96115 curr_node = self .getRoot ()
116+ if (not self .empty ()):
97117 while (curr_node .getRight () is not None ):
98118 curr_node = curr_node .getRight ()
99119 return curr_node
100120
101- def getMin (self ):
102- #We go deep on the left branch
103- curr_node = None
121+ def getMin (self , root = None ):
122+ if (root is not None ):
123+ curr_node = root
124+ else :
125+ #We go deep on the left branch
126+ curr_node = self .getRoot ()
104127 if (not self .empty ()):
105128 curr_node = self .getRoot ()
106129 while (curr_node .getLeft () is not None ):
@@ -121,29 +144,58 @@ def preShow(self, curr_node):
121144 def getRoot (self ):
122145 return self .root
123146
147+ def __isRightChildren (self , node ):
148+ if (node == node .getParent ().getRight ()):
149+ return True
150+ return False
151+
152+ def __reassignNodes (self ,node , newChildren ):
153+ if (newChildren is not None ):
154+ newChildren .setParent (node .getParent ())
155+ if (node .getParent () is not None ):
156+ #If it is the Right Children
157+ if (self .__isRightChildren (node )):a
158+ node .getParent ().setRight (newChildren )
159+ else :
160+ #Else it is the left children
161+ node .getParent ().setLeft (newChildren )
162+ else :
163+ #It is the root of the tree
164+ node .setLabel (newChildren .getLabel ())
124165
125166def testBinarySearchTree ():
126167 '''
127168 Example
128- 8
129- / \
130-
131- / \ \
132-
133- / \ /
134- 4 7 13
169+ 8
170+ / \
171+ 3 10
172+ / \ \
173+ 1 6 14
174+ / \ /
175+ 4 7 13
135176 '''
136177
178+ '''
179+ Example After Deletion
180+ 7
181+ / \
182+
183+ / \
184+ 1 6
185+ /
186+ 4
187+ '''
137188 t = BinarySearchTree ()
138189 t .insert (8 )
139190 t .insert (3 )
140- t .insert (1 )
191+ t .insert (10 )
141192 t .insert (6 )
142- t .insert (4 )
143- t .insert (7 )
193+ t .insert (1 )
144194 t .insert (10 )
145195 t .insert (14 )
146196 t .insert (13 )
197+ t .insert (4 )
198+ t .insert (7 )
147199
148200 t .preShow (t .getRoot ())
149201
@@ -160,6 +212,12 @@ def testBinarySearchTree():
160212 if (not t .empty ()):
161213 print ("Max Value: " , t .getMax ().getLabel ())
162214 print ("Min Value: " , t .getMin ().getLabel ())
215+
216+ t .delete (13 )
217+ t .delete (10 )
218+ t .delete (8 )
219+
220+ t .preShow (t .getRoot ())
163221
164222if __name__ == "__main__" :
165223 testBinarySearchTree ()
0 commit comments