(Please help me with Coding in Python3)
AVLTree
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 += '\n'
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)
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):
n = self.right
self.val, n.val = n.val, self.val
self.right, n.right, self.left, n.left = n.right, n.left, n,
self.left
@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):
if
AVLTree.Node.height(t.left) >
AVLTree.Node.height(t.right):
if AVLTree.Node.height(t.left.left) >=
AVLTree.Node.height(t.left.right): # LL
t.rotate_right()
else:
t.left.rotate_left()
t.rotate_right()
else:
if AVLTree.Node.height(t.right.right) >=
AVLTree.Node.height(t.right.left): # RR
t.rotate_left()
else:
t.right.rotate_right()
t.rotate_left()
def add(self, val):
assert (val not in
self)
def
add_rec(node):
if not node:
return AVLTree.Node(val)
elif val < node.val:
node.left = add_rec(node.left)
elif val > node.val:
node.right = add_rec(node.right)
if abs(AVLTree.Node.height(node.left) -
AVLTree.Node.height(node.right)) >= 2:
AVLTree.rebalance(node)
return node
self.root =
add_rec(self.root)
self.size += 1
def __delitem__(self, val):
assert (val in
self)
rebal = []
def
delitem_rec(node):
if val < node.val:
node.left = delitem_rec(node.left)
elif val > node.val:
node.right = delitem_rec(node.right)
else:
if not node.left and not node.right:
return None
elif node.left and not node.right:
return node.left
elif node.right and not node.left:
return node.right
else:
# remove the largest value from the left subtree (t) as a
replacement
# for the root value of this tree
t = node.left
rebal.append(t)
if not t.right:
node.val = t.val
node.left = t.left
else:
n = t
while n.right.right:
n = n.right
rebal.append(n)
rebal.append(n)
t = n.right
n.right = t.left
node.val = t.val
while rebal:
s = rebal.pop()
if abs(AVLTree.Node.height(s.left) - AVLTree.Node.height(s.right))
>= 2:
AVLTree.rebalance(s)
if abs(AVLTree.Node.height(node.left) -
AVLTree.Node.height(node.right)) >= 2:
AVLTree.rebalance(node)
return node
self.root =
delitem_rec(self.root)
self.size -= 1
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 += '\n'
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)
(Please help me with Coding in Python3) AVLTree complete the following implementation of the balanced (AVL)...
Java help! Please help complete the min method below in bold. import java.util.Arrays; import java.util.ArrayList; import java.util.Collections; import java.util.Iterator; import java.util.List; /** * Provides an implementation of a binary search tree * with no balance constraints, implemented with linked nodes. * * * */ public class Bst<T extends Comparable<T>> implements Iterable<T> { ////////////////////////////////////////////////////////////////// // I M P L E M E N T T H E M I N M E T H O D B E L O W...
I need to complete the code by implementing the min function and the alpha betta pruning in order to complete the tic tac toe game using pything. code: # -*- coding: utf-8 -*- """ Created on: @author: """ import random from collections import namedtuple GameState = namedtuple('GameState', 'to_move, utility, board, moves') infinity = float('inf') game_result = { 1:"Player 1 Wins", -1:"Player 2 Wins", 0:"It is a Tie" } class Game: """To create a game, subclass this class and implement actions,...
9p This is for Python I need help. Pet #pet.py mName mAge class Pet: + __init__(name, age) + getName + getAge0 def init (self, name, age): self.mName = name self.mAge = age Dog Cat def getName(self): return self.mName mSize mColor + __init__(name, age,size) + getSize() + momCommento + getDog Years() +_init__(name, age,color) + getColor + pretty Factor + getCatYears def getAge(self): return self.mAge #dog.py import pet #cat.py import pet class Dog (pet. Pet): class Cat (pet. Pet): def init (self,...
PYTHON QUESTION... Building a Binary Tree with extended Binary Search Tree and AVL tree. Create a class called MyTree with the methods __init__(x), getLeft(), getRight(), getData(), insert(x) and getHeight(). Each child should itself be a MyTree object. The height of a leaf node should be zero. The insert(x) method should return the node that occupies the original node's position in the tree. Create a class called MyBST that extends MyTree. Override the method insert(x) to meet the definitions of a...
Here is my code for minesweeper in python and it has something wrong. Could you please help me to fix it? import tkinter as tk import random class Minesweeper: def __init__(self): self.main = tk.Tk() self.main.title("mine sweeper") self.define_widgets() self.mines = random.sample( [(i,j) for i in range(25) for j in range(50) ],self.CustomizeNumberOfMines()) print(self.mines) self.main.mainloop() self.CustomizeNumberOfMines() def define_widgets(self): """ Define a canvas object, populate it with squares and possible texts """ self.canvas = tk.Canvas(self.main, width = 1002, height=502, bg="#f0f0f0") self.canvas.grid(row=0, column=0) self.boxes =...
In Python, starting with the 8x8 board solution that will be appended here add the following functionality: 1) Add code to create a list, containing 8 lists, with each of the 8 lists containing 8 null strings as values. Call the list of lists board. code provided by prof: import turtle validMovesList=['A0','A2','A4','A6','B1','B3','B5','B7', 'C0','C2','C4','C6','D1','D3','D5','D7', 'E0','E2','E4','E6','F1','F3','F5','F7', 'G0','G2','G4','G6','H1','H3','H5','H7','quit'] def drawSquare(t,length,color): t.fillcolor(color) t.begin_fill() for num in range(4): t.forward(length) t.left(90) t.end_fill() def drawRow(t,length,color1,color2): for i in range(4): drawSquare(t,length,color1) t.forward(length) drawSquare(t,length,color2) t.forward(length) def drawCircleFilled(t,size,color): t.fillcolor(color) t.begin_fill()...
Write a function, swapSubtrees, that swaps all of the left and right subtrees of a binary tree. Add this function to the class binaryTreeType and create a program to test this function. #include <iostream> using namespace std; //Definition of the Node template <class elemType> struct nodeType { elemType info; nodeType<elemType> *lLink; nodeType<elemType> *rLink; }; //Definition of the class template <class elemType> class binaryTreeType { public: //Overload the assignment operator. const binaryTreeType<elemType>& operator=(const binaryTreeType<elemType>&) { if (this != &otherTree) //avoid self-copy...
please help me answer this c programing question Q2: Complete the given program by implementing the following functionality: Calculate the number of fully-grown plants: It takes 4 months for one seed to grow into one fully- grown plant and generate the first seed, then the fully- grown plant will produce one seed every month. Every time there is a seed generated, the seed will immediately start to grow into a plant. Starting from one seed, calculate how many fully- grown...
could you please help me with this problem, also I need a little text so I can understand how you solved the problem? import java.io.File; import java.util.Scanner; /** * This program lists the files in a directory specified by * the user. The user is asked to type in a directory name. * If the name entered by the user is not a directory, a * message is printed and the program ends. */ public class DirectoryList { public static...
My Python file will not work below and I am not sure why, please help me debug! ********************************* Instructions for program: You’ll use these functions to put together a program that does the following: Gives the user sentences to type, until they type DONE and then the test is over. Counts the number of seconds from when the user begins to when the test is over. Counts and reports: The total number of words the user typed, and how many...