Can someone help me with this PYTHON code Overview In this notebook you will com

Question

Can someone help me with this PYTHON code

Overview

In this notebook you will complete the following implementation of the balanced (AVL) binary search tree. Note that you should not be implementing the map-based API described in the plain (unbalanced) BSTree notebook — i.e., nodes in the AVLTree will only contain a single value.

class AVLTree:
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right

def rotate_right(self):
n = self.left
self.val, n.val = n.val, self.val
self.left, n.left, self.right, n.right = n.left, n.right, n, self.right
  
def rotate_left(self):
# YOUR CODE HERE
raise NotImplementedError()
  
@staticmethod
def height(n):
if not n:
return 0
else:
return max(1+AVLTree.Node.height(n.left), 1+AVLTree.Node.height(n.right))

def __init__(self):
self.size = 0
self.root = None
  
@staticmethod
def rebalance(t):
# YOUR CODE HERE
raise NotImplementedError()
  
def add(self, val):
assert(val not in self)
# YOUR CODE HERE
raise NotImplementedError()
  
def __delitem__(self, val):
assert(val in self)
# YOUR CODE HERE
raise NotImplementedError()
  
def __contains__(self, val):
def contains_rec(node):
if not node:
return False
elif val < node.val:
return contains_rec(node.left)
elif val > node.val:
return contains_rec(node.right)
else:
return True
return contains_rec(self.root)
  
def __len__(self):
return self.size
  
def __iter__(self):
def iter_rec(node):
if node:
yield from iter_rec(node.left)
yield node.val
yield from iter_rec(node.right)
yield from iter_rec(self.root)
  
def pprint(self, width=64):
"""Attempts to pretty-print this tree's contents."""
height = self.height()
nodes = [(self.root, 0)]
prev_level = 0
repr_str = ''
while nodes:
n,level = nodes.pop(0)
if prev_level != level:
prev_level = level
repr_str += ' '
if not n:
if level < height-1:
nodes.extend([(None, level+1), (None, level+1)])
repr_str += '{val:^{width}}'.format(val='-', width=width//2**level)
elif n:
if n.left or level < height-1:
nodes.append((n.left, level+1))
if n.right or level < height-1:
nodes.append((n.right, level+1))
repr_str += '{val:^{width}}'.format(val=n.val, width=width//2**level)
print(repr_str)
  
def height(self):
"""Returns the height of the longest branch of the tree."""
def height_rec(t):
if not t:
return 0
else:
return max(1+height_rec(t.left), 1+height_rec(t.right))
return height_rec(self.root)

# LL-fix (simple) test
# 3 points

from unittest import TestCase

def height(t):
if not t:
return 0
else:
return max(1+height(t.left), 1+height(t.right))

tc = TestCase()
t = AVLTree()

for x in [3, 2, 1]:
t.add(x)
  
tc.assertEqual(height(t.root), 2)
tc.assertEqual([t.root.left.val, t.root.val, t.root.right.val], [1, 2, 3])

# RR-fix (simple) test
# 3 points

from unittest import TestCase

def height(t):
if not t:
return 0
else:
return max(1+height(t.left), 1+height(t.right))

tc = TestCase()
t = AVLTree()

for x in [1, 2, 3]:
t.add(x)
  
tc.assertEqual(height(t.root), 2)
tc.assertEqual([t.root.left.val, t.root.val, t.root.right.val], [1, 2, 3])

# LR-fix (simple) test
# 3 points

from unittest import TestCase

def height(t):
if not t:
return 0
else:
return max(1+height(t.left), 1+height(t.right))

tc = TestCase()
t = AVLTree()

for x in [3, 1, 2]:
t.add(x)
  
tc.assertEqual(height(t.root), 2)
tc.assertEqual([t.root.left.val, t.root.val, t.root.right.val], [1, 2, 3])

# RL-fix (simple) test
# 3 points

from unittest import TestCase

def height(t):
if not t:
return 0
else:
return max(1+height(t.left), 1+height(t.right))

tc = TestCase()
t = AVLTree()

for x in [1, 3, 2]:
t.add(x)
  
tc.assertEqual(height(t.root), 2)
tc.assertEqual([t.root.left.val, t.root.val, t.root.right.val], [1, 2, 3])

# ensure key order is maintained after insertions and removals
# 15 points

from unittest import TestCase
import random

tc = TestCase()
vals = list(range(0, 100000000, 333333))
random.shuffle(vals)

t = AVLTree()
for x in vals:
t.add(x)

for _ in range(len(vals) // 3):
to_rem = vals.pop(random.randrange(len(vals)))
del t[to_rem]

vals.sort()

for i,val in enumerate(t):
tc.assertEqual(val, vals[i])

# stress testing
# 15 points

from unittest import TestCase
import random

tc = TestCase()

def traverse(t, fn):
if t:
fn(t)
traverse(t.left, fn)
traverse(t.right, fn)

def height(t):
if not t:
return 0
else:
return max(1+height(t.left), 1+height(t.right))
  
def check_balance(t):
tc.assertLess(abs(height(t.left) - height(t.right)), 2, 'Tree is out of balance')

t = AVLTree()
vals = list(range(1000))
random.shuffle(vals)
for i in range(len(vals)):
t.add(vals[i])
for x in vals[:i+1]:
tc.assertIn(x, t, 'Element added not in tree')
traverse(t.root, check_balance)

random.shuffle(vals)
for i in range(len(vals)):
del t[vals[i]]
for x in vals[i+1:]:
tc.assertIn(x, t, 'Incorrect element removed from tree')
for x in vals[:i+1]:
tc.assertNotIn(x, t, 'Element removed still in tree')
traverse(t.root, check_balance)

Explanation / Answer

========================================================================================

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.