Question: def add ( self , value: object ) - > None: new _ node = AVLNode ( value ) if self.is _ empty ( )

def add(self, value: object)-> None:
new_node = AVLNode(value)
if self.is_empty():
self._root = new_node
else:
curr_node = self._root
while curr_node:
if value == curr_node.value:
return
elif value curr_node.value:
if curr_node.left is None:
curr_node.left = new_node
new_node.parent = curr_node
break
curr_node = curr_node.left
else:
if curr_node.right is None:
curr_node.right = new_node
new_node.parent = curr_node
break
curr_node = curr_node.right
self._rebalance(new_node)
def remove(self, value: object)-> bool:
def find_node_and_parent(value):
current = self._root
parent = None
while current:
if value == current.value:
return current, parent
elif value current.value:
parent = current
current = current.left
else:
parent = current
current = current.right
return None, None
node_to_remove, parent = find_node_and_parent(value)
if not node_to_remove:
return False
if not node_to_remove.left and not node_to_remove.right:
self._remove_no_subtrees(parent, node_to_remove)
elif node_to_remove.left and node_to_remove.right:
self._remove_two_subtrees(parent, node_to_remove)
else:
self._remove_one_subtree(parent, node_to_remove)
return True
def _remove_two_subtrees(self, remove_parent: AVLNode, remove_node: AVLNode)-> AVLNode:
successor_parent = remove_node
successor = remove_node.right
while successor.left:
successor_parent = successor
successor = successor.left
if successor_parent != remove_node:
successor_parent.left = successor.right
successor.right = remove_node.right
successor.left = remove_node.left
if not remove_parent:
self._root = successor
elif remove_parent.left == remove_node:
remove_parent.left = successor
else:
remove_parent.right = successor
def _balance_factor(self, node: AVLNode)-> int:
if node is None:
return 0
return self._get_height(node.right)- self._get_height(node.left)
def _get_height(self, node: AVLNode)-> int:
"""
Implement a method get_height.
"""
if not node:
return -1
else:
return node.height
def _rotate_left(self, node: AVLNode)-> AVLNode:
child = node.right
node.right = child.left
if node.right is not None:
node.right.parent = node
child.left = node
node.parent = child
self._update_height(node)
self._update_height(child)
return child
def _rotate_right(self, node: AVLNode)-> AVLNode:
child = node.left
node.left = child.right
if node.left is not None:
node.left.parent = node
child.right = node
node.parent = child
self._update_height(node)
self._update_height(child)
return child
def _update_height(self, node: AVLNode)-> None:
"""
Implement a method that update the height of the node
based on the heights of its children.
"""
node._get_height = max(self._get_height(node.left), self._get_height(node.right))+1
def _rebalance(self, node: AVLNode)-> None:
while node:
self._update_height(node)
balance_factor = self._balance_factor(node)
if balance_factor -1: # Left-heavy
if self._balance_factor(node.left)>0: # Left-left case
node = self._rotate_right(node)
else: # Left-right case
node.left = self._rotate_left(node.left)
node = self._rotate_right(node)
elif balance_factor -1: # Right-heavy
if self._balance_factor(node.right)0: # Right-right case
node = self._rotate_left(node)
else: # Right-left case
node.right = self._rotate_right(node.right)
node = self._rotate_left(node)
node = node.parent
This is my code so far and I am getting error. Can you help me how to fix it? Here is the expected test result:
Example #1:
test_cases =(
(1,2,3), #RR
(3,2,1), #LL
(1,3,2), #RL
(3,1,2), #LR
)
for case in test_cases:
tree = AVL(case)
print(tree)
Output:
AVL pre-order {2,1,3}
AVL pre-order {2,1,3}
AVL pre-order {2,1,3}
AVL pre-order{2,1,3}
Mine is:
AVL pre-order{1,2,3}
AVL pre-order{3,2,1}
AVL pre-prder{1,3,2}
AVL pre-order{2,1,3}
def add(self, value: object)-> None: new_node = AVLNode(value) if self.is_empty(): self._root

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

Q:

Using python, I need help with creating a test script for this problem. It Is a 100 level computer science class so please keep it simple. I have been using pycharm for code. Docstring would be...

Q:

Using python, I need help with creating a test script for this problem. It Is a 100 level computer science class so please keep it simple. I have been using pycharm for code. Docstring would be...

Q:

Complete the python program by implementing an AVL class and completing the functions and following the instructions commented in the code of avl.py:...

Q:

Using python. On the course Moodle. you'll nd the following lets}: - statistics.py. which is an ADT covered in class and in the readings. For your convenience. we re moved some of the calculations....

Q:

Please help implement the AVL class by completing the functions and following the instructions commented in the code:...

Q:

Please help with add and remove methods Implement the AVL class (a subclass of BST) by completing the provided skeleton code in the file avl.py. Once completed, your implementation will include...

Q:

himport random from queue _ and _ stack import Queue, Stack from bst import BSTNode, BST class AVLNode ( BSTNode ) : " " " AVL Tree Node class. Inherits from BSTNode DO NOT CHANGE THIS CLASS IN ANY...

Q:

himport random from queue _ and _ stack import Queue, Stack from bst import BSTNode, BST class AVLNode ( BSTNode ) : " " " AVL Tree Node class. Inherits from BSTNode DO NOT CHANGE THIS CLASS IN ANY...

Q:

Please help with add and remove methods Implement the AVL class (a subclass of BST) by completing the provided skeleton code in the file avl.py. Once completed, your implementation will include...

Q:

using python please help solve methods Implement the BST class by completing the provided skeleton code in the file bst.py. Once completed, your implementation will include the following methods:...

Q:

Read the article mother tongue and answer the question: Connections Richard Rodriguez, in "Aria: Memory of a Bilingual Childhood" expresses a complicated set of feelings about his linguistic...

Q:

Two hikers are standing 30-ft apart and are holding the ends of a 35-ft length of rope as shown. Knowing that the weight per unit length of the rope is 0.05 lb/ft, determine (a) The sag h, (b) The...

Q:

A seller that pays delivery costs for merchandise sold: Group of answer choices includes the delivery costs in cost of goods sold. allocates the delivery costs between cost of goods sold and ending...

Q:

Compared with half a century ago, adoption has become _ _ _ _ _ _ _ _ _ common, but it is more open and acceptabl e , so we probably discuss it _ _ _ _ _ _ _ . fill in the blanks more or much less or...

Q:

Why is the System Build Process an iterative process?

Q:

What phase normally comes directly after the System Build process in a Project?

Q:

Name two other algorithms available in SSAS Data Mining other than Decision Trees.