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, [...] 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 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 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

# ????????????????????????????????????????????????????????????????????????????????????????
# ????????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????
# 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
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.right_child = leftmost_node.right_child
see if its right or left child of parent and point the left or right pointer of parent to None accordintly, and don't forget to cover root case where node is root so set root to None!

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

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, [...] 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 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 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

# ????????????????????????????????????????????????????????????????????????????????????????
# ????????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????
# 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
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.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, [...] 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 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 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

# ????????????????????????????????????????????????????????????????????????????????????????
# ????????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????
# 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
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.right_child = leftmost_node.right_child
see if its right or left child of parent and point the left or right pointer of parent to None accordintly, and don't forget to cover root case where node is root so set root to None!

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
If you want to change selection, open document below and click on "Move attachment"

#### pdf

owner: kkhosravi - (no access) - PYTHON_DATA_STRUCTURES_AND_ALGORITHMS.pdf, p158

#### Summary

status measured difficulty not learned 37% [default] 0

No repetitions