Do you want BuboFlash to help you learning these things? Or do you want to add or correct something? Click here to log in or create user.

Question

In algorithms, for **BinarySearchTree**, the delete method (**def delete(self, data): **) has these **5 steps**: **1)** use helper function to get pointers to node to delete and its parent **2)** get children count of node to delete** 3)** If node to delete has no children, see if its right or left child of parent and act accordingly (cover root case where node is root so set root to None!)** 4)** If node to delete has one child, get pointer to that child (next_node), and if parent exists (i.e. not root case!), make parent point correctly (via left/right pointer) to that child, then cover root case (i.e. make root the next_node) **5)** If node to delete has 2 children, create **[...]** , and iterate left on the leftmost_node till you find left most, then swap the current node.data with the leftmost_node.data, and delete the leftmost_node via its parent by pointing its left child to leftmost_node right child (which could be None, if no child), making sure to cover the basecase where the parent_of_leftmost_node is the root node (which causes right_child pointer of parent to point to leftmost_node right_child):

```
class Node:
def __init__(self, data):
self.data = data
self.left_child = None
self.right_child = None
class Tree:
def __init__(self):
self.root_node = None
def get_node_with_parent(self, data):
parent = None
current = self.root_node
if current == None:
return (parent, None)
while current:
if data == current.data:
return (parent, current)
elif data <= current.data:
parent = current
current = current.left_child
else:
parent = current
current = current.right_child
return (parent, current)
def remove(self, data):
# 1. User helper function to get pointers to node to delete and its parent
parent, node = self.get_node_with_parent(data)
if node == None:
return False
# 2. Get children count of node to delete
children_count = 0
if node.left_child and node.right_child:
children_count = 2
elif (node.left_child is None) and (node.right_child is None):
children_count = 0
else:
children_count = 1
# 3. If node to delete has no children, see if its right or left child of parent and act accordingly (cover case of root/
# no parent!)
if children_count == 0:
if parent:
if parent.right_child is node:
parent.right_child = None
else:
parent.left_child = None
else:
self.root_node = None
# 4. If node to delete has one child, get pointer to that child (next_node), and if parent exists (i.e. not root case!),
# make parent point correctly (via left/right pointer) to that child, then cover root case (i.e. make root the
# next_node)
elif children_count == 1:
next_node = None
if node.left_child:
next_node = node.left_child
else:
next_node = node.right_child
if parent:
if parent.left_child is node:
parent.left_child = next_node
else:
parent.right_child = next_node
else:
self.root_node = next_node
# 5. If node to delete has 2 children
else:
????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????
while leftmost_node.left_child:
parent_of_leftmost_node = leftmost_node
leftmost_node = leftmost_node.left_child
node.data = leftmost_node.data
if parent_of_leftmost_node.left_child == leftmost_node:
parent_of_leftmost_node.left_child = leftmost_node.right_child
else: ############ parent_of_leftmost_node is root!!
parent_of_leftmost_node.right_child = leftmost_node.right_child
```

Answer

two new pointers, **parent_of_leftmost_node (inititialized to node)**, and** leftmost_node (initialized to node.right_child):**

```
else:
parent_of_leftmost_node = node
leftmost_node = node.right_child
while leftmost_node.left_child:
parent_of_leftmost_node = leftmost_node
leftmost_node = leftmost_node.left_child
node.data = leftmost_node.data
if parent_of_leftmost_node.left_child == leftmost_node:
parent_of_leftmost_node.left_child = leftmost_node.right_child
else: ############ parent_of_leftmost_node is root!!
parent_of_leftmost_node.right_child = leftmost_node.right_child
```

Question

In algorithms, for **BinarySearchTree**, the delete method (**def delete(self, data): **) has these **5 steps**: **1)** use helper function to get pointers to node to delete and its parent **2)** get children count of node to delete** 3)** If node to delete has no children, see if its right or left child of parent and act accordingly (cover root case where node is root so set root to None!)** 4)** If node to delete has one child, get pointer to that child (next_node), and if parent exists (i.e. not root case!), make parent point correctly (via left/right pointer) to that child, then cover root case (i.e. make root the next_node) **5)** If node to delete has 2 children, create **[...]** , and iterate left on the leftmost_node till you find left most, then swap the current node.data with the leftmost_node.data, and delete the leftmost_node via its parent by pointing its left child to leftmost_node right child (which could be None, if no child), making sure to cover the basecase where the parent_of_leftmost_node is the root node (which causes right_child pointer of parent to point to leftmost_node right_child):

```
class Node:
def __init__(self, data):
self.data = data
self.left_child = None
self.right_child = None
class Tree:
def __init__(self):
self.root_node = None
def get_node_with_parent(self, data):
parent = None
current = self.root_node
if current == None:
return (parent, None)
while current:
if data == current.data:
return (parent, current)
elif data <= current.data:
parent = current
current = current.left_child
else:
parent = current
current = current.right_child
return (parent, current)
def remove(self, data):
# 1. User helper function to get pointers to node to delete and its parent
parent, node = self.get_node_with_parent(data)
if node == None:
return False
# 2. Get children count of node to delete
children_count = 0
if node.left_child and node.right_child:
children_count = 2
elif (node.left_child is None) and (node.right_child is None):
children_count = 0
else:
children_count = 1
# 3. If node to delete has no children, see if its right or left child of parent and act accordingly (cover case of root/
# no parent!)
if children_count == 0:
if parent:
if parent.right_child is node:
parent.right_child = None
else:
parent.left_child = None
else:
self.root_node = None
# 4. If node to delete has one child, get pointer to that child (next_node), and if parent exists (i.e. not root case!),
# make parent point correctly (via left/right pointer) to that child, then cover root case (i.e. make root the
# next_node)
elif children_count == 1:
next_node = None
if node.left_child:
next_node = node.left_child
else:
next_node = node.right_child
if parent:
if parent.left_child is node:
parent.left_child = next_node
else:
parent.right_child = next_node
else:
self.root_node = next_node
# 5. If node to delete has 2 children
else:
????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????
while leftmost_node.left_child:
parent_of_leftmost_node = leftmost_node
leftmost_node = leftmost_node.left_child
node.data = leftmost_node.data
if parent_of_leftmost_node.left_child == leftmost_node:
parent_of_leftmost_node.left_child = leftmost_node.right_child
else: ############ parent_of_leftmost_node is root!!
parent_of_leftmost_node.right_child = leftmost_node.right_child
```

Answer

?

Question

In algorithms, for **BinarySearchTree**, the delete method (**def delete(self, data): **) has these **5 steps**: **1)** use helper function to get pointers to node to delete and its parent **2)** get children count of node to delete** 3)** If node to delete has no children, see if its right or left child of parent and act accordingly (cover root case where node is root so set root to None!)** 4)** If node to delete has one child, get pointer to that child (next_node), and if parent exists (i.e. not root case!), make parent point correctly (via left/right pointer) to that child, then cover root case (i.e. make root the next_node) **5)** If node to delete has 2 children, create **[...]** , and iterate left on the leftmost_node till you find left most, then swap the current node.data with the leftmost_node.data, and delete the leftmost_node via its parent by pointing its left child to leftmost_node right child (which could be None, if no child), making sure to cover the basecase where the parent_of_leftmost_node is the root node (which causes right_child pointer of parent to point to leftmost_node right_child):

```
class Node:
def __init__(self, data):
self.data = data
self.left_child = None
self.right_child = None
class Tree:
def __init__(self):
self.root_node = None
def get_node_with_parent(self, data):
parent = None
current = self.root_node
if current == None:
return (parent, None)
while current:
if data == current.data:
return (parent, current)
elif data <= current.data:
parent = current
current = current.left_child
else:
parent = current
current = current.right_child
return (parent, current)
def remove(self, data):
# 1. User helper function to get pointers to node to delete and its parent
parent, node = self.get_node_with_parent(data)
if node == None:
return False
# 2. Get children count of node to delete
children_count = 0
if node.left_child and node.right_child:
children_count = 2
elif (node.left_child is None) and (node.right_child is None):
children_count = 0
else:
children_count = 1
# 3. If node to delete has no children, see if its right or left child of parent and act accordingly (cover case of root/
# no parent!)
if children_count == 0:
if parent:
if parent.right_child is node:
parent.right_child = None
else:
parent.left_child = None
else:
self.root_node = None
# 4. If node to delete has one child, get pointer to that child (next_node), and if parent exists (i.e. not root case!),
# make parent point correctly (via left/right pointer) to that child, then cover root case (i.e. make root the
# next_node)
elif children_count == 1:
next_node = None
if node.left_child:
next_node = node.left_child
else:
next_node = node.right_child
if parent:
if parent.left_child is node:
parent.left_child = next_node
else:
parent.right_child = next_node
else:
self.root_node = next_node
# 5. If node to delete has 2 children
else:
????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????
while leftmost_node.left_child:
parent_of_leftmost_node = leftmost_node
leftmost_node = leftmost_node.left_child
node.data = leftmost_node.data
if parent_of_leftmost_node.left_child == leftmost_node:
parent_of_leftmost_node.left_child = leftmost_node.right_child
else: ############ parent_of_leftmost_node is root!!
parent_of_leftmost_node.right_child = leftmost_node.right_child
```

Answer

two new pointers, **parent_of_leftmost_node (inititialized to node)**, and** leftmost_node (initialized to node.right_child):**

```
else:
parent_of_leftmost_node = node
leftmost_node = node.right_child
while leftmost_node.left_child:
parent_of_leftmost_node = leftmost_node
leftmost_node = leftmost_node.left_child
node.data = leftmost_node.data
if parent_of_leftmost_node.left_child == leftmost_node:
parent_of_leftmost_node.left_child = leftmost_node.right_child
else: ############ parent_of_leftmost_node is root!!
parent_of_leftmost_node.right_child = leftmost_node.right_child
```

If you want to change selection, open document below and click on "Move attachment"

status | not learned | measured difficulty | 37% [default] | last interval [days] | |||
---|---|---|---|---|---|---|---|

repetition number in this series | 0 | memorised on | scheduled repetition | ||||

scheduled repetition interval | last repetition or drill |

Do you want to join discussion? Click here to log in or create user.