Skip to content

Enabled root deletion for zero and one child roots #2

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
Dec 26, 2014
Merged

Enabled root deletion for zero and one child roots #2

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
c6cbff8
Enabled root deletion for zero and one child roots
Dec 11, 2014
eaf6bf7
Oops. Getting rid of pycs
Dec 11, 2014
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
42 changes: 26 additions & 16 deletions algorithms/binary_tree.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -18,16 +18,19 @@ def insert(self, data):

@param data node data object to insert
"""
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data

def lookup(self, data, parent=None):
"""
Expand Down Expand Up @@ -60,11 +63,14 @@ def delete(self, data):
children_count = node.children_count()
if children_count == 0:
# if node has no children, just remove it
if parent.left is node:
parent.left = None
if parent:
if parent.left is node:
parent.left = None
else:
parent.right = None
del node
else:
parent.right = None
del node
self.data = None
elif children_count == 1:
# if node has 1 child
# replace node by its child
Expand All @@ -77,7 +83,11 @@ def delete(self, data):
parent.left = n
else:
parent.right = n
del node
del node
else:
self.left = n.left
self.right = n.right
self.data = n.data
else:
# if node has 2 children
# find its successor
Expand Down Expand Up @@ -157,4 +167,4 @@ def children_count(self):
cnt += 1
if self.right:
cnt += 1
return cnt
return cnt
16 changes: 16 additions & 0 deletions algorithms/tests/test_binary_tree.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -64,6 +64,22 @@ def test_binary_tree(self):
t.append(d)
self.assertEquals(t, [7, 10, 11, 14, 17])

# check for root deletion
root = binary_tree.Node(1)
root.insert(2)
root.insert(0)
root.delete(1)
self.assertEquals(root.data, 2)
root.delete(2)
self.assertEquals(root.data, 0)
root.delete(0)
self.assertEquals(root.data, None)
root.insert(1)
self.assertEquals(root.data, 1)
self.assertEquals(root.left, None)
self.assertEquals(root.right, None)


if __name__ == '__main__':
unittest.main()