Implement algorithms for sea4ch (Python)

1. sequential search
2. binary search
3. binary search tree
4. red-black binary search tree

Plot your running time for searching 10^i objects for i= 1, 2, 3, 4, 5, 6.

What about plotting for i = 7, 8, 9?

Fill in the given code below:

import time

import random

class Array_Search:

def __init__(self, array):

self.array = array

def init_array_search(self, val_array):

self.array = Array_Search(val_array)

def squential_search(self, key):

idx = 0

for num in self.array:

if num == key:

return idx

idx = idx+1

return False

def bsearch(self, val):

return False

class BST_Node:

def __init__(self, val):

self.val = val

self.left = None

self.right = None

class BST:

def __init__(self):

self.root = None

def init_bst(self, val):

self.root = BST_Node(val)

def insert(self, val):

if (self.root is None):

self.init_bst(val)

else:

self.insertNode(self.root, val)

def insertNode(self, current, val):

return False

def bsearch(self, val):

return False

def searchNode(self, current, val):

return False

def delete(self, val):

return False

class RBBST_Node:

def __init__(self, val, color):

self.val = val

self.left = None

self.right = None

self.color = color

RED = True

BLACK = False

class RBBST:

def __init__(self):

self.root = None

def init_rbbst(self, val, color):

self.root = RBBST_Node(val, color)

def is_red(self, current):

return False

def rotate_left(self, current):

return False

def rotate_right(self, current):

return False

def flip_colors(self, current):

return False

def insert(self, val):

if (self.root is None):

self.init_rbbst(val, RED)

else:

self.insertNode(self.root, val)

def insertNode(self, current, val):

return False

def bsearch(self, val):

return False

def searchNode(self, current, val):

return False

if __name__ == "__main__":

set_sz = 10

tut = BST()

vals = random.sample(range(1, 100), set_sz)

for idx in range(set_sz - 1):

tut.insert(vals[idx])

print (tut.bsearch(vals[1]))

print(tut.bsearch(11))

tut_rb = RBBST()

for idx in range(set_sz - 1):

tut_rb.insert(vals[idx])

print (tut.bsearch(vals[1]))

print(tut.bsearch(11))