Question

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 Binary Search Tree. Create a method called __contains__(x) that returns true if x is in the tree.

Create a class called MyAVL that extends MyBST.

Template:

class MyTree():

def __init__(self, data):

# Initialize this node, and store data in it

self.data = data

self.left = None

self.right = None

self.height = 0

self.descendents = 0

def getLeft(self):

# Return the left child of this node, or None

return self.left

def getRight(self):

# Return the right child of this node, or None

return self.right

def getData(self):

# Return the data contained in this node

return self.data

def insert(self, data):

# Insert data into the tree, descending from this node

# Ensure the tree remains complete - every level is filled save for the last, and each node is as far left as possible

# Return this node after data has been inserted

pass

def getHeight(self):

# Return the height of this node

pass

class MyBST(MyTree):

def __init__(self, data):

# Initialize this node, and store data in it

super().__init__(data)

pass

def insert(self, data):

# Insert data into the tree, descending from this node

# Ensure that the tree remains a valid Binary Search Tree

# Return this node after data has been inserted

pass

def __contains__(self, data):

# Returns true if data is in this node or a node descending from it

pass

class MyAVL(MyBST):

def __init__(self, data):

# Initialize this node, and store data in it

super().__init__(data)

pass

def getBalanceFactor(self):

# Return the balance factor of this node

pass

def insert(self, data):

# Insert data into the tree, descending from this node

# Ensure that the tree remains a valid AVL tree

# Return the node in this node's position after data has been inserted

pass

def leftRotate(self):

# Perform a left rotation on this node and return the new node in its spot

pass

def rightRotate(self):

# Perform a right rotation on this node and return the new node in its spot

pass

Override the method insert(x) to meet the definitions of an AVL Tree. Create a method called getBalanceFactor() that returns the balance factor of the node. You will need to implement the methods leftRotate() and rightRotate().

Tester:

import random

#Module Imports

import sys

from importlib import import_module

def CheckHeight(tree):

if tree is None:

return -1

else:

return max(CheckHeight(tree.getLeft())+1,CheckHeight(tree.getRight())+1)

def CheckAVL(tree):

if CheckHeight(tree) > 0:

l = 0 if tree.getLeft() is None else CheckHeight(tree.getLeft())+1

r = 0 if tree.getRight() is None else CheckHeight(tree.getRight())+1

b = l-r

if abs(b) >= 2 or b != tree.getBalanceFactor():

print(f"balance factor is {b} and tree claims it is {tree.getBalanceFactor()}")

printTree(tree)

return False

else:

return CheckAVL(tree.getLeft()) and CheckAVL(tree.getRight())

else:

return True

def printTree_(tree, prefix):

print(f"{prefix}{tree.data}")

if tree.getLeft() is not None:

printTree_(tree.getLeft(),prefix+"-")

if tree.getRight() is not None:

printTree_(tree.getRight(),prefix+"-")

def printTree(tree):

printTree_(tree,"")

def Test(lib, seed=0, size=10, rounds=10, verbose=False):

random.seed(a=seed)

# Test MyTree

n = random.randint(0, size)

try:

tree = lib.MyTree(n)

except:

if verbose:

print("Error: MyTree not creatable")

return False

h=1

c=2

for i in range(1,size):

n = random.randint(n,n*2)

try:

tree = tree.insert(n)

except:

print(c)

if verbose:

print("Error: Tree not insertable")

return False

tH = tree.getHeight()

if CheckHeight(tree) != tH:

if verbose:

print("Error: Tree height calculation incorrect")

return False

if tH != h:

if verbose:

print("Error: Tree height incorrect: Should be {h} but is {tH}")

return False

if i == c:

h+=1

c+=(2**h)

del(tree)

if verbose:

print("Tree test complete.")

# Tree works

yield True

m = size*3

n = random.randint(size, size*2)

try:

bst = lib.MyBST(n)

except:

if verbose:

print("Error: MyBST not creatable")

return False

try:

bst=bst.insert(n+1)

except:

if verbose:

print("Error: BST not insertable")

return False

try:

bst=bst.insert(n-1)

except:

if verbose:

print("Error: BST not insertable")

return False

if bst.getHeight() != 1 or bst.getHeight() != CheckHeight(bst):

if verbose:

print("Error: BST height incorrect")

return False

try:

bst=bst.insert(n+2)

bst=bst.insert(n+3)

except:

if verbose:

print("Error: BST not insertable")

return False

if bst.getHeight() != 3 or bst.getHeight() != CheckHeight(bst):

if verbose:

print("Error: BST height incorrect.")

return False

del(bst)

bst= lib.MyBST(n)

a = []

for i in range(size):

v = random.randint(0,m)

bst= bst.insert(v)

if not(v in a):

a.append(v)

for i in range(size):

if len(a) >= size:

m*=2

v = random.randint(0,m)

if (v in a) != (v in bst):

if verbose:

print("Error: BST Search incorrect")

return False

del(bst)

if verbose:

print("BST test complete.")

yield True #BST works

n=10

try:

avl = lib.MyAVL(n)

except:

if verbose:

print("Error: MyAVL not creatable")

return False

first = avl

try:

avl = avl.insert(n+6)

except:

if verbose:

print("Error: AVL not insertable #1")

return False

try:

avl = avl.insert(n+12)

except:

if verbose:

print("Error: AVL not insertable #2")

return False

if not(first is avl.getLeft()):

if verbose:

print("Error: AVL Rotation incorrect #1")

return False

try:

second = avl.getRight()

second

except:

if verbose:

print("Error: AVL Node lost during rotation")

return False

try:

avl=avl.insert(8)

avl=avl.insert(6)

except:

if verbose:

print("Error: AVL Node not insertable")

return False

if not(first is avl.getLeft().getRight()):

if verbose:

print("Error: AVL Rotation incorrect #2")

return False

if verbose:

print("AVL Double Rotation test complete")

yield True # Simple rotation correct

try:

avl=avl.insert(n-3)

except:

if verbose:

print("Error: AVL Node not insertable")

return False

# Force rotations

avl = avl.insert(n-2)

avl = avl.insert(n-1)

avl = avl.insert(n*2+4)

avl = avl.insert(n*2+3)

if not (first is avl.getRight().getLeft().getRight()):

if verbose:

print("Error: AVL Rotation incorrect #3")

return False

if verbose:

print("AVL Double Rotation test complete")

yield True # Rotation test complete

for i in range(0, size):

avl = avl.insert(random.randint(0,size))

if not CheckAVL(avl):

if verbose:

print("Error: AVL Property not maintained across inserts")

return False

if verbose:

print("AVL Property test complete")

yield True # Big test complete

if __name__ == "__main__":

if len(sys.argv) < 2:

print("Include at least a library name as an argument.")

exit()

name = sys.argv[1]

if name.endswith(".py"):

name = name[:-3]

print(f"Testing module {name}")

module=import_module(name,package=__name__)

score=0

for i in Test(module,seed=123456, size=1000, rounds=200, verbose=True):

if i:

score+=1

else:

break

print(f"Test result: {score}/5")

Answer 1

class MyTree():

def __init__(self, data):
  
# Initialize this node, and store data in it
  
self.data = data
  
self.left = None
  
self.right = None
  
self.height = 0
  
self.descendents = 0
  
def getLeft(self):
  
# Return the left child of this node, or None
  
return self.left
  
def getRight(self):
  
# Return the right child of this node, or None
  
return self.right
  
def getData(self):
  
# Return the data contained in this node
  
return self.data
  
def insert(self, data):
  
q = []
q.append(self)
while (len(q)):
temp = q[0]
q.pop(0)
if (not temp.left):
temp.left = MyTree(key)
break
else:
q.append(temp.left)
  
if (not temp.right):
temp.right = MyTree(key)
break
else:
q.append(temp.right)
return temp
  
def getHeight(self):
if self is None:
return 0 ;
else :
lDepth = getHeight(self.left)
rDepth = getHeight(self.right)
if (lDepth > rDepth):
return lDepth+1
else:
return rDepth+1

class MyBST(MyTree):
def __init__(self, data):
super().__init__(data)
def insert(self, data):
if self is None:
temp=MyBST(data)
return temp
if(data<self.data):
self.left=insert(self.left,data)
else:
self.right=insert(self.right,data)
return self
def __contains__(self, data):
if(self.data==data):
return True
temp
if(data<self.data):
temp=__contains__(self.left,data)
if(temp==True):
return True
temp=__contains__(self.right,data)
return temp

class MyAVL(MyBST):

def __init__(self, data):
super().__init__(data)
def getBalanceFactor(self,root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
  
def insert(self,root,data):
if not root:
return TreeNode(key)
elif key < root.key:
root.left = self.insertNode(root.left, key)
else:
root.right = self.insertNode(root.right, key)
root.height = 1 + max(self.getHeight(root.left),self.getHeight(root.right))

balanceFactor = self.getBalance(root)
if balanceFactor > 1:
if key < root.left.key:
return self.rightRotate(root)
else:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
  
if balanceFactor < -1:
if key > root.right.key:
return self.leftRotate(root)
else:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
  
return root
  
def leftRotate(self,z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.getHeight(z.left),self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left),self.getHeight(y.right))
return y
  
def rightRotate(self,z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self.getHeight(z.left),
self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left),
self.getHeight(y.right))
return y