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 two new pointers, parent_of_leftmost_node (inititialized to node), and leftmost_node (initialized to node.right_child), **[...]** , and delete the leftmost_node via its parent by pointing its left child to leftmost_node right child (which could be None, if no right 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, create two new pointers, parent_of_leftmost_node (inititialized to node),
# and leftmost_node (initialized to node.right_child), 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 children), making sure to cover the case where the
# parent_of_leftmost_node is the root node (which causes orientation change of it pointing to the leftmost_node (left vs # right child
else:
parent_of_leftmost_node = node
leftmost_node = node.right_child
??????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????
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

and **iterate left on the leftmost_node** till you **find left most, then swap the current node.data with the leftmost_node.data:**

```
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 two new pointers, parent_of_leftmost_node (inititialized to node), and leftmost_node (initialized to node.right_child), **[...]** , and delete the leftmost_node via its parent by pointing its left child to leftmost_node right child (which could be None, if no right 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, create two new pointers, parent_of_leftmost_node (inititialized to node),
# and leftmost_node (initialized to node.right_child), 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 children), making sure to cover the case where the
# parent_of_leftmost_node is the root node (which causes orientation change of it pointing to the leftmost_node (left vs # right child
else:
parent_of_leftmost_node = node
leftmost_node = node.right_child
??????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????
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 two new pointers, parent_of_leftmost_node (inititialized to node), and leftmost_node (initialized to node.right_child), **[...]** , and delete the leftmost_node via its parent by pointing its left child to leftmost_node right child (which could be None, if no right 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, create two new pointers, parent_of_leftmost_node (inititialized to node),
# and leftmost_node (initialized to node.right_child), 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 children), making sure to cover the case where the
# parent_of_leftmost_node is the root node (which causes orientation change of it pointing to the leftmost_node (left vs # right child
else:
parent_of_leftmost_node = node
leftmost_node = node.right_child
??????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????
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

and **iterate left on the leftmost_node** till you **find left most, then swap the current node.data with the leftmost_node.data:**

```
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.