For task 1, you will need to write a RedBlackTree class. The class is detailed as follows:

____(self)

o Complexity: O(1)

o This is the constructor for the class. You will need to store the following here:

+ A variable _root

+ Any other instance variables you want.

(self,)

o Complexity: O(lg(n))

o Valid Input: An object of type: MealTicket. Return False on invalid input.

o Description: The insert method will insert a MealTicket into the tree. Very similar to BST insert, except you will also need to check to see if the tree breaks any of the Red-Black Properties. If so, preform the appropriate rotations and/or re-colorings.

(self,)

o Complexity: O(lg(n))

o Valid Input: A positive integer in the range (0, ]. Return False on invalid input.

o Description: The delete method will remove a MealTicket from the tree. Very similar to BST delete, except you will also need to check to see if the tree breaks any of the Red-Black Properties. If so, preform the appropriate rotations and/or re-colorings.

(self,) |

o Complexity: O(lg(n))

o Valid Input: A positive integer in the range (0, ]. Return False on invalid input.

o Description: Find takes an int ticketID and returns the ticket in the tree whose ID matches that value. If no such ticket exists in the tree, return False. Its the same as in BST

Note 1: The methods listed above are the only methods that will be tested. However, you may add additional methods as you please. After the lab, I will post some skeleton code for this assignment. Feel free to use the methods provided in your code. Just copy-paste them into your class. The skeleton code provides the methods for find, traverse, an RB-node class, and some helpful extras you may use if you want. To be specific you should implement the following:

1. _leftRotate()

2. _rightRotate()

Meal Ticket

"""

Author: Jared Hall

Description: A simple meal ticket program.

Date: 01/14/2020

Notes:

1. This program contains the meal ticket class.

"""

#------------------------------ Classes ----------------------------------------

class MealTicket():

""" A simple meal ticket class. """

ID = 1

def __init__(self, ticketName):

""" Constructor for the meal ticket class """

self.TicketName = ticketName

self.ticketID = MealTicket.ID

self.totalCost = 0

self.items = []

MealTicket.ID += 1

def addItem(self, item):

""" Add an Item to the MealTicket """

self.items.append(item)

self.totalCost += item[1]

return True

def display(self):

"""Print out the MealTicket """

print("=== Displaying Ticket ===")

print("Ticket Name: ", self.TicketName)

print("Ticket ID: ", self.ticketID)

print("Total Cost: ", round(self.totalCost, 2))

print("Ticket Items: ")

for i in range(0, len(self.items)):

msg = " Item name: " + str(self.items[i][0])

msg += " -- Item cost: " + str(self.items[i][1])

print(msg)

print("========== End ========== ")

#-------------------------------------------------------------------------------

#------------------------- Pre-Made Tickets ------------------------------------

#Feel free to add your own interesting meals here! (f^.^) f

ticket1 = MealTicket("Jared's Breakfast")

ticket1.addItem(("Eggs", 4.50))

ticket1.addItem(("Bacon", 2.50))

ticket1.addItem(("OJ", 1.00))

ticket2 = MealTicket("Jared's Lunch")

ticket2.addItem(("Steak", 14.99))

ticket2.addItem(("Salad", 3.00))

ticket2.addItem(("Lychee", 0.50))

ticket3 = MealTicket("Jared's Dinner")

ticket3.addItem(("Noodles", 11.50))

ticket3.addItem(("Dumplings", 5.99))

ticket3.addItem(("Whiskey", 19.99))

ticket4 = MealTicket("Jared's Snacks")

ticket4.addItem(("Dragon Fruit", 8.50))

ticket4.addItem(("Strawberry", 3.25))

ticket4.addItem(("Passion Fruit", 4.50))

#-------------------------------------------------------------------------------

#---------------------------- Simple Testing main ------------------------------

if(__name__ == "__main__"):

def main():

print(" === Testing MealTicket class ===")

#Step-03: Display tickets

ticket1.display()

ticket2.display()

ticket3.display()

ticket4.display()

return True

main()

#-------------------------------------------------------------------------------